第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313） Eまで。
C x=sum(A)/Nとすると、x-1とxにするか、xとx+1にするか
D xor基底。要素K個でN個の線形独立なものを作るのに苦戦した。
E A[i]は後何回で消えるか？　を後ろからDP。

— titia (@titia_til) August 5, 2023

F - Flip Machines

　解説を読み、bit DPのところが分からず解説放送を見てAC。

　X_jとY_jが異なるようなマシンを起動すると、それらのカードにおいて期待値は表裏の平均になる……というのは言われれば分かるがパッと思いつくのは難しい。

　だが、その後の方がもっと難しい。マシーン全探索で答えが求まるのは分かるが、それでは計算量が無理。

　Nが40以下というのを利用するだろうと予想できるが、「裏が表より大きいもの」と「裏が表より小さいもの」と分けて、

・「裏が表より小さいもの」につながるいくつかのマシーンを起動したとき、いくら儲かるか?　を考えると貪欲に取れる

　ということにまず気付かなくてはいけない。これで、「裏が表より小さいもの」がNの半分より少ないときは間に合う。

　あとは、「裏が表より大きいもの」が少ないときを考えれば良い。（と、二つに分けて考えるのがまず難しいのだが）

　こちらの場合は、bit DPを使う。「裏が表より大きいもの」の集合Sを考え、そのときの損の最小値はいくらか？　というのをDP[S]でもつ。そのDPテーブルを、「裏が表より小さいもの」一つずつを見て更新していけば良い。

　解説を見て理解する分には難しくないのだが、実際に解くのは大変に感じる。

G - Redistribution of Piles

　自力AC。

　できることが、何回か減らしてから増やす、しかないので、ある減らした状態から何回増やせるかを考えれば良い。

　そうするとfloor sumを使いそうな式になるので、この公式（？）が使える形に変形するとACできた。

　ただ、自力ACとは書いたけど、最近のコンテストでfloor sumを使う問題が出たという記憶に残っていたから解けただけかもしれない……。