問題 codeforces.com半径rの円の中心のx座標がN個与えられる。 i = 0,1,2,3...N-1の順に円はy=10^100からy = 0に向かって進む。 他の円に接した時、y = 0に円が接した時に円は止まる。 最終的なN個の円のy座標を求める。 考察 i番目の円aをy=0に向かって進め…

問題 codeforces.com整数k_i(1 x_i,x_i + k_i,x_i + 2*k_i,x_i + 3*k_i...の値を選択できる。 整数x_1,x_2,x_3の値を定めた時、max(x_1,x_2,x_3)以上の整数すべてを選択できるかを判定する。 考察 ・k_i = 1が1つ以上存在するのならYES 値の差が1なので整数…

問題 D - FT Robot 解法 x座標、y座標に分けてDP 文字列Sを連続する'T','F'で分割して考えると、x座標だけ変化する、y座標だけ変化する区間が存在することが分かる。 よって、x座標、y座標の変化は独立して考えることが出来る。 あとはdp[i個目の連続する'F'…

問題 C - Not so Diverse 解法 整数がK種類以下になるまで、個数の少ない整数から書き換えていく(整数を消していくと考えても良い)。まず、各整数ごとに個数をまとめて、次に個数で整数の種類数をまとめていく。 あとはK種類以下の整数になるまで、整数を書…

問題 colopl2018-qual.contest.atcoder.jp 解法 A～Bまでの整数が書かれた各カードを購入するか購入しないで全探索する。制約等から時間計算量がO(2^35)と思ってしまうが 「...これまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカ…