【6日目】ARC116の復習続き！ - 茶coderが1カ月だけ競プロをガチってみる

まずは昨日の復習の続き。

D - I Wanna Win The Game

(本題とは逸れるが、このタイトルはどういう意味が込められているのだろうか…？深い意味があるのかはたまた何の意味もないのか。)

出ましたXOR。苦手なんだよな、、と思いつつも成り立つ性質というのは

くらいなものなので、単に意識の問題かもしれない。この問題でポイントになるのは、上の二つの法則ではなく

XORは各bitごとに独立して計算できる

という性質。これを使うと、問題を最下位bitとそれ以外に分けた形に帰着できるので、

$dp(k, l) = (\sum A_i = k となるl bitの数列(A_i)の場合の数)$

としたとき

$dp(2k, l) = \sum_{i=0}^{min(k, \frac{N}{2})} dp(k-i, l-1) * \binom{N}{2i}$

という漸化式を立てられ、さらにこのlは不要なので、 $dp(k)$ を計算量 $O(M^{2})$ で求められる…というカラクリ。XORはbitごとに考える、というのは今後も使えそう。

この問題も二項係数使った。昨日のアルゴリズムを転用。今回たまたま多いだけなのか、それともARCレベルになるとしょっちゅう出てくるものなのか。

あとコーナーケースは気をつけよう。そんなに難しくないから提出前に必ず確認しよう(自分への訓戒)。

EとFは今の段階ではレベルが高すぎるのでやっていない。500点問題がある程度解けるようになってきた段階で手を出そうと思う。

さて今後だが、以降練習はABCと併せてARCも取り入れていこうと思う。正直ABCとARCの最大の違いである100点200点問題は問題なく解けるし、今後の課題となってくるのは500点レベルの問題の攻略なので。

夜は少し時間がないので、今夜のABCの結果その他は明日書きます。。