* 問題文 http://codeforces.com/contest/578/problem/C 解法 max 取ってるし、x についての weakness を f(x) とすると、下に凸な関数になりそう。 なので3分探索する。 x を決めたときの a[i] - x 列の区間和最大、最小は線形で解ける。 左から累積和を見…

問題文 http://codeforces.com/contest/576/problem/B 解法 自分は直感で、どうせ p に周期3以上のサイクルがあると困るんじゃないの、みたいに考えた。 周期3以上のサイクル内部で辺を張るとループができて困るので、そういう意味では正しい。 また、2つの…

問題文 http://codeforces.com/contest/575/problem/G 解法 1ステップごとにコストが10倍になり、かつ辺のコストは高々9であることから、通った道を前から見て10進表記したものがコストなので、できるだけ短いほうがいいことにはすぐ気がつく。同じ長さなら…

問題文 http://codeforces.com/contest/581/problem/F 解法 （知っていれば）二乗の木DPっぽいな～となり、実際そうである。 ひとまず普通に木DPをする。 dp[v][cnt][c] := v の部分木だけ考えて、その中の葉を cnt だけ黒く塗り、v の色が c であるときの最…

問題文 http://codeforces.com/contest/573/problem/B 解法 1ステップ後の h[i] の高さは min(h[i - 1], h[i] - 1, h[i + 1]) になる。 一般化して、k ステップ後の h[i] の高さは min(h[i - k], h[i - k + 1] - 1, ..., h[i] - k, ..., h[i + k]) になる。 …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2850 解法 01BFSで解いた。 まず、2部グラフだと永遠に終わらないことはわかる。 2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2847 解法 まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。 一行目が埋まると、下の行の数は一…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858 解法 区間篩の要領で解ける。 [1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。 今回の場合は、素数 p が検出できたら、[L, R] …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2593 解法 辺の長さをまず決め打つと、それぞれの円と交わる部分が区間として求まる。 得られた区間の連結な部分の総長さで、決めうった値よりも長い所があれば、そのような正方形を配置す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1620 解法 前もってすべての式を生成してしまえばOK。 真理値表は 16bit 分の情報があればよく、bitDP 的な要領で生成していけば良い。 つまり、キーが真理値表で、値がその最小長さである…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 解法 自分は数式で捉えて、ラグランジュの未定乗数法で解いた。 ラグランジュの未定乗数法については以下のサイトがわかりやすい（ただし厳密な証明はない）。 mathtrain.jp与えられ…

問題文 http://codeforces.com/contest/566/problem/A 問題概要 n 個の名前と、n 個のペンネームが与えられる。これらを1対1対応させることを考える。 名前 a とペンネーム b をペアにした時の満足度を lcp(a, b) と定義する。 lcp(a, b) の総和が最大となる…