問題文 http://codeforces.com/contest/547/problem/C 解法 与えられた値を素因数分解して出てくる素数の数は高々6個しかない． gcd を考えるときはこれだけで十分である． 今回は直接答えを求めず，gcd(a, b) != 1 となる個数を求めて最後にトータルから引…

問題文 解法1 値の大きい方から追加していって，区間やその幅をset, multiset で管理して頑張るだけ． 実装が悲しい感じになる． ソースコード1 #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int inf = 1e9; int main() { int n; cin >> n; </int,></bits/stdc++.h>…

問題文 http://codeforces.com/contest/547/problem/A 解法 mod を取っているので，それぞれ高々 m 回でループするのはすぐわかる． とりあえずそれぞれについて目的の高さになるまで愚直にシミュレートする． この時到達できないならそもそも不可能なので -…

問題文 http://codeforces.com/contest/543/problem/C 解法 n それは，a-z の26文字より小さいので，各文字は1箇所変更するだけで easy to remember にできるということ． つまり，ある文字列 i を easy to remember にするには，以下のどちらかしかない． …

問題文 http://codeforces.com/contest/542/problem/F 解法 DPで解ける． dp[i][j] := 高さ i に存在するノードが j 個であるようなときの，価値の最大値 とする． ある高さ i のときに考えるべきタスクは，実はコストが T - i であるものだけでよい． なぜ…

はじめに 7/6 に行われた ACM-ICPC 2018 国内予選の参加記です． 忘れないうちに書こうと思います． 今年は大雨で関西勢は大変でしたね．自分の大学もリモート参加推奨，という形になってしまいかなりバタバタしていました． 結果 チーム Zerokan_Sunshine …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2702 解法 後退解析で解く． ゲームの探索なので，最初は始点からDFSしたくなるかもしれないが，普通に状態が自分に戻ってくるような遷移があるので困る． こういうときは確定しているとこ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く． 与えられるグラフはDAGになっていて，この上で2回違う条件で最短経路を求めたい．しかし依存関係にあるので独立にはできない． こういうときは1回目と2回…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける． 左が欠けているやつを考えるときは末尾から比べたいので，各文字を反転した文字列集合も別に持っておく． 与えられた石版に ? がある場合は26文字全通り試す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽？ union find の各集合がどのクラブに属するかを別に vector で持っておく． a と b が同じ部活に所属している場合，マージするのだが違うクラブに属し…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2693 解法 いかにもな bitDP 感がある． しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える． うまくやれば状態に順列持てたりしないかな～と制約を読むと N -…

問題文 http://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか，という問題． まず，n * m （n, m はただの自然数）のような表現は完全に不利． 例えば 99 * 99 を考えてみるとわかりやすいが，そのまま出力したほうが短い…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390 解法 感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう． そして投げたら通った（終了）…だと困るので厳密じゃないけど一応それっぽいのだけ．木なので基地…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1342 解法 3次元幾何に見せかけた2次元幾何． 球の半径Rを決めた時，上から見て中心をどこにおけるかをイメージする． すると針と球の条件は，ある円があってその外側に中心を置く，という…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2558 解法 最小点被覆は多項式時間で解けない． この時点で，グラフにある良い性質を用いるか，頑張って枝刈りしかない． しかし与えられたグラフは単純グラフであるだけで他にいい感じの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2541 解法 特別な辺のコストを定めた時，それぞれの最短経路長がすぐに求まってくれないと困る． そこで特別な辺は100個しか無いことを利用し，とりあえず以下のダイクストラをやる．d[i][…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434 解法 他のそれぞれのアイドルの得点の期待値は，3種類の要素の得点の確率変数をX, Y, Z とすると E[X + Y + Z] だが，これは期待値の線形性から E[X] + E[Y] + E[Z] と等しい． した…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 解法 最短経路（それはそう）． 同じ高さの街が高々10しかないので，どの街に行ったか 2 ^ 10 で表現したい． どの街に行ったかを保存しつつ最短経路をやりたいね，となる． それには…

問題文 http://codeforces.com/problemset/problem/286/E 解法 FFT． まず，答えの集合から生成できる任意の重さは，ある2個以下のカバンを使って（同じカバンを2つでもいい）作ることができる． なぜなら，もしある重さを p1 + p2 + p3 で生成したとする．…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703 解法 明らかに全てのサイコロを使うのが最適． あとは，後ろから見るbitDPで解く． これは，最後に使うサイコロから決めていくと，その直前に使うサイコロによる得点が，今まで使った…

問題文 Venn Diagram | Aizu Online Judge 解法 頑張って実装するだけ． 円の半径は入力からすぐわかる． 2つの円の距離を二分探索で求めたら，でかい方を左下隅に配置． 小さいほうは [0, pi/2] でどの角度に置くとよいかを判定．計算したくないので二分探…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1252 解法 以下の4パターン全部試すだけ． swap しない（単に編集距離の問題） 1回swapしたあと編集距離 2回swap 消した後 swap 最悪 200(200-1)/2 * 16 * (16 * 16) なので，まあ適当にや…

問題文 http://codeforces.com/contest/958/problem/E2 解説 わからなかったので上位陣のコードから解法を得た． とりあえずソートして隣接項の差を作ると，以下の問題になる．n - 1 要素からなる数列から，k 個えらんでその和を最小化せよ．ただし，隣接2要…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1371 解法 現れうる文字は高々8種類しかない． なので各文字に対して何を割り当てるか全探索して構文解析するだけ． ソースコード #include <bits/stdc++.h> using namespace std; using ret_type = doubl</bits/stdc++.h>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351 解法 StarrySkyTree + 二分探索で通した．( を +1, ) を -1 として累積和をStarrySkyTree上で管理する． 文字列が balanced であることと，累積和上の最小値が 0 以上であり，かつ末…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 解法 二分探索＋しゃくとり法． 二分探索は，普通に「スペースの隙間を X にして条件をクリアできるか」でやる．次にしゃくとり部分．二分探索の過程で与えられた，空けていい間隔を …

問題文 http://codeforces.com/gym/100459 解法 Standing -> 重心をおろした位置が底面の内部 Unstable -> 重心をおろした位置が底面の周上にある Falling -> 重心をおろした位置が底面の外部重心の座標は (a + b + c + d) / 4 なので，あとは底面の三角形と…

問題文 http://codeforces.com/gym/100459 解法 しゃくとり法で解いた． 条件を満たさないようなペアの数を数えて，全体から引くことで求める． しゃくとりの過程で，今現在の区間が overlap しうるので，その分は足すことで重複して引かないようにしている…

問題文 http://codeforces.com/gym/100459 解法1 行列累乗で解く． 左から順番に見ていった時，状態としては k + 3 種類ある． 最初の second type が来た状態，途中の first type （k個の状態がある），最後の second type が来た状態（受理状態），それ以…

問題文 http://codeforces.com/gym/100453 解法 X, Y, Z のそれぞれについて，巡回するいくつかのグループに分けることができる． 周期 a で巡回する列と，周期 b で巡回する列と，周期 c で巡回する列を考える．これらはそれぞれ X, Y, Z から持ってくると…