C - Kill/Death 問題概略 1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。N,M sum 解法 昇順について考えなければ、桁DPとして解ける。 dp[i][rem] := iまで見ていて、残り使える合計がrem 昇順になっていないといけ…

B - 最短路問題問題概略 頂点1とiの距離がAiになるようなグラフの総数を数えよ。制約 10^5解法 全体を一気に考えると難しくなってしまう。例えば上を満たすような最小限のグラフを全通り作ってやり、そこに辺をどれだけ追加できるかのように考えると駄目。元…

D - Remainder Reminder問題概略N以下の整数a,bで、a % bがK以上になる組み合わせを数え上げ 制約 1≤N≤1051≤N≤105 0≤K≤N−10≤K≤N−1 入力は全て整数である 解法 ２つの組み合わせの数え上げは、片方を固定するのが鉄板。 bを固定すると、0~Nの全てのaに対して…

C - String Coloring 問題概略 長さ2Nの文字列が与えられる。各文字を青と赤に塗り分けた時、左から青を読んだときと右から赤を読んだ時の文字列が同じ組み合わせはいくつあるか 制約 1≤N≤181≤N≤18 SS の長さは 2N2N である SS は英小文字のみからなる 解法 …

C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder 問題概略 N個の整数A1~ANが与えられる。i<jとなるAi,Ajを選んだ時、２つの積がKの倍数となる組み合わせを求めよ 制約 1≦N≦200,000 1≦Ai≦109(1≦i≦N) 1≦K≦109 Ai, K はいずれも整数 解法 N^2では間に合わない。組み合わせ問題でよくあるまとめ上げを使う。 ２つの積がKの倍数になる -> Kの約数でないものは考えなくていいため、Aたちの中からKの約数だけを取り出し、それぞれ何個あるかを持っておく。 あと</jとなるai,ajを選んだ時、２つの積がkの倍数となる組み合わせを求めよ>…

C - すぬけそだて――ごはん―― 問題概略 A以上B以下の数から0個以上選ぶ時、それらが互いに素になる組み合わせはいくつか 制約 1≤A≤B≤10181≤A≤B≤1018 B−A≤35 解法 高々35個しかないので、偶数の中から0個か1つ選び、奇数の中から選ぶ数を全探索できる(18 * 2^1…

B - Minimum Sum 解法5 1 4 8 2 6 7 3 たとえば2がminで選ばれる回数は、Lが4,8,2の時でかつRが2,6,7の時なので9回ある。つまり、自分より大きくて左右で地続きになっているものの個数が分かれば解ける。初めは数を大きい順に見ていき、union-find木に入れて…