yukicoder contest 409

　Aを解いた後AHCをやろうと思っていたのに、AHCもやらずに眠ってしまった。

コンテストへのリンク

No.2509 Beam Shateki

　自力AC。

　x行とy列にビームを打つならば、x行目とy列目の和を前計算しておいて、その和からA[x][y]を引く。

　……この方針で実装したが、実装量が多くなってしまった。

　今回は、ビームの位置を全探索し、毎回愚直しても間に合う。その方が実装が簡単だったか？　でもあまり変わらない気もする。

No.2510 Six Cube Sum (Count)

　自力AC。

　半分全列挙は思いついたけど、メモリ制限が厳しく実装に苦労した。

No.2512 Mountain Sequences

　苦労したが自力AC。

　最大値を固定して考えると、Σ(二項係数)*（二項係数）の形になる。多分、Σの中が高速化できるんだろうな～、とWolfram alphaで実験を繰り返したら、なんとか求められる式がでてきてACできた。

　公式解説を読むと、あっさりもっと簡単な形に変形していた。とはいえ、こういうのはどうやって思いつけば良いのか。

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) Fまでは結構順調だったがGが分からず終了。
B 乱択して一致するか調べた。
C 斜め四方向#の場所から左上だけ調べればOK
D 枝狩り全探索
E DP。1/5で遷移。
F 1～N文字目から何文字までいけるか二分探索。

— titia (@titia_til) April 29, 2023

G - P-smooth number

　半分全列挙という情報を得てAC。

　最大でsample2の個数なら、上手く枝狩りすれば列挙できそうな気がして、どこかまとめて（メモ化再帰を使って）計算できるところがあるのでは？　という方向性で考えてしまった。

　言われてみれば半分全列挙も、劇的に計算量を改善するというよりは、全探索でも通りそうなものの計算量を減らす手段でしたね。ケアしないといけない。

yukicoder contest 379

　Cまで三完。 Aに苦戦したのは反省。

コンテストへのリンク

No.2235 Line Up Colored Balls

　解説AC。

　期待値の線形性は考えたのだが、その後の考察がおかしかった。色が同じボールの間に他のボールが挟まる確率は……などと考えていたが、これでは線形性は使えない。

　（tester解の通りだが）ボールを順番に並べていくと考えて、

・（i番目と$i+1$番目が異なる確率）の総和と考える

　すると、

・色iのボールが最後以外で取り出される確率は$(S-1)/S$

・次のボールが色iでない確率は$(S-x_i)/(S-1)$

　から求めることができる。

No.2236 Lights Out On Simple Graph

　解説AC。

　半分全列挙と言われても頂点を半分にすることしか思い浮かばず、辺で半分全列挙すると思いつかなかった。

Educational Codeforces Round 113 (Rated for Div. 2)

　Dまで四完でした。

コンテストへのリンク

コンテスト後のツイート

E. Playoff Restoration

　半分全列挙。

　半分全列挙は疑ったのに、半分に分けても混ぜることができない気がしてしまった。

　実際は、$\sum{ i \cdot A^{p_i}}$　がハッシュなので、各$A^{p_i}$ごとにindexの総和さえ分かればよく、それならぐっと数が減るので半分全列挙が機能します。

　……と、納得してツイートしたらmaspyさんに不要だと指摘されました。（指摘ありがとうございます）

　Sample1で考えてみます。

　決勝で勝つか負けるかは考えずに半分全列挙をし、勝った場合負けた場合、それぞれについてハッシュ値を求めると、前半については、

・[5, 3, 5, 2]のときのハッシュ値

・[5, 3, 5, 1]のときのハッシュ値

　が分かっています。（こうやって列挙する数は$k=5$のとき、$2^15$個）

　この、[5, 3, 5, 2]に対応する後半のハッシュがあるかを調べるためには、

・h（問題文で与えられたハッシュ値）- [5, 3, 5, 2]のときのハッシュ値

　なるハッシュ値を取るものが後半の列挙した中で、かつ二位ではなく一位を使うものの中に存在すれば良いです。

　これ、ハッシュが和として定義されているから、半分のハッシュの和が分かれば残り半分は全体から引くことで求められる……と、当たり前なのだけれど、半分全列挙で上手くできるのはこの性質のおかげで、私が躓いたのはこの部分だったかと思う。

　そして、前半と同じように後半も列挙・調査しておけば、これが[1, 5, 5, 3]に対応しているということが分かります。

　シンプルな半分全列挙で、ナップザック問題の半分全列挙のように、ソートして二分探索（もしくは尺取り）というようなことも必要ない。

　半分全列挙というキーワードを思い付いたのなら、解けなくてはいけない問題でした。反省。

Codeforces Round #612

　Aで時間がかかってしまって混乱したので飛ばし、B、Cを考えていたけれど分からずの0完……。

Div. 2　B. Hyperset

　$O(n^3)$だと厳しいので、どうやって計算量を落とすか、という問題（C++で枝狩りすれば$O(n^3)$で通るようですが）

・半分全列挙で$O(n^2)$に。

→本当に半分だと半分全列挙は思いつきやすいけど、$O(n^3)$を$O(n^2)$に落とすとき思いつきにくくなるので注意。

コンテストへのリンク

A. Garland

・（上手く貪欲すれば解けるらしいけど）制約を見るとDPが自然

→偶奇のどちらを使ったか、偶数・奇数それぞれを何個使ったかを持ってDP。これで$O(n^3)$

・コンテスト中は、i番目を見るとき、今まで使った偶数の個数＋奇数の個数がiになることを使えば$O(n^2)$になるし、DP配列を使い回せばメモリ節約できる……とか混乱してハマった。

→この問題は制約が甘いので、$O(n^3)$で簡単に書けば良い。まあ$O(n^2)$にするだけなら良いと思うけど、後半のDP配列の使い回しは混乱を招くので避けるべきだった。

B. Numbers on Tree

・制約を確認！！

→これも制約が甘いので、単純な$O(n^2)$でOK。葉から貪欲にnodeの値を決め、今まで使った数字の間の値にしたくなったなら、それより大きい数字を一個ずつずらせば良い。

C1. Madhouse (Easy version)

・「全ての部分列」にはかなりの情報量が含まれるので、簡単に決まるのでは？

→1:nと2:nだけで決定できる！