問題 解法 解答 問題 atcoder.jp 解法 dp(i, a, b) := 1 ~ i までの全ての順列のうち，P_k > k となるような k の個数が a，P_k < k となるような k の個数が b である通り数 を考える．1 ~ i - 1 までの順列に新しく i を追加するとき，1 ~ i - 1 までの順…

結果 A - Darker and Darker B - LRUD Game 結果 6 問中 2 問正解（900 / 6400 点, 22:30），1288 位中 486 位，パフォーマンス 1787，新レート 1567 (+27)．A, B 問題を早解き出来たのはよかったが，C 問題と通せず終わってしまったためパフォーマンスがあ…

問題 解法（嘘） 解答 問題 atcoder.jp 解法（嘘） 上下と左右はそれぞれ独立に考えられる．なので，先手が上下左右のうち 1 方向を決めて，その方向に貪欲に動かしていき，もう一方がその逆の方向に貪欲に動かしていくという操作を各方向シミュレーションす…

問題 解法 解答 問題 atcoder.jp 解法 問題文中の「辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる」は「黒色のマスと辺を共有して隣接する白色のマスが黒色になる」と言い変えられるので，全ての黒色の…

問題 解法 解答 問題 atcoder.jp 解法 各 k ごとに考える． A_1 ~ A_k までの XOR は累積和的に計算できる．この XOR を bit の桁ごとに見ていく．XOR の i bit 目が 1 のとき，A_1 ~ A_k それぞれの i bit 目が反転される．よって，A_1 ~ A_k それぞれの i …

問題 解法 解答 問題 atcoder.jp 解法 "RB" や "GG" と並ぶことはない．また，R は N - 1, N 文字目，G は 1, N 文字目，B は 1, 2 文字目に来ることはない．これらの条件のうち 1 つでも当てはまれば答えは No, すべてクリアしていれば Yes となる．O(N)． …

問題 解法 解答 問題 atcoder.jp 解法 受付しなければいけない人がいる時間帯の区間の数が知りたいので，imos 法を用いて「ある時間 t に受付しなければいけない人がいるか？」を O(1) で知れるように前計算しておく．あとは，受付しなければいけない人が連…

問題 解法 解答 問題 yukicoder.me 解法 P = 1 または N / 2 より大きい素数のとき答えは 1．なぜならば，前者は自明で，後者は 2 * P が N を超えてしまうため，1 ~ N の数の中で 2 と P をかけて合成数を作ることが出来ないから． そうでないとき，家 i（i…