ABC187-Fを解説ACした。これは本当に未知の知識だったから解説ACして正解だった。青diffだから考察次第で自力ACできるかと思ったけど分からんもんだ。

まず、ある集合の部分集合の部分集合の総和が

$\Sigma_{S\subset V} 2^{|S|}=3^{|V|}$

というのを知らなかった。部分集合の部分集合をなめるDP自体は思いついたから「$4^N N$あれば間違いなく解ける、部分集合の部分集合だから$4^N$よりは多少小さくなりそう」というのはちらっと考えたけど、$3^N$になって間に合うのは一切想像してなかった。未知の知識だから仕方なかったと言えば仕方ないけど、実際$4^N$よりどの程度小さくなるのか計算を試みるくらいはしてよかったかも。

それから

for(int i = 0; i < (1 << n); i++)
for(int j = i; j > 0; --j &= i)

というループで$3^N$をなめることができるのも知らなかった。

この2行目の面白いfor、要するに2進数のビット列で表現された部分集合を使ってそれの部分集合を全探索できるということなので、必要分だけ重ねれば任意のp進数の全探索が$O(N p^N)$でなく無駄なく$O(p^N)$で出来るんじゃないのか？例えばこういうコードを書けば$5^N$を全探索できる。

for(int i1 = 0; i1 < (1 << n); i1++)
for(int i2 = i1; i2 > 0; --i2 &= i1)
for(int i3 = i2; i3 > 0; --i3 &= i2)
for(int i4 = i3; i4 > 0; --i4 &= i3)

うおおすげえ！と思ったのだがちょっと注意点として、上記におけるi2,i3,i4が0になるような場合(つまり空集合)はスルーされるので、正確には$5^N$ではないし、5進数には全くならない。それらも探索するにはもう一工夫が必要そうだ。ちょっと色々試してみたけどあまりいい感じのコードは書けなかった。うーーん。

今回は全く知らなかった知識が手に入ったのでなかなか面白かった！名前、名前が欲しいこれ…調べにくい…

---

ABC195に出た。いろいろだめだった。

Bはもうちょっと冷静に考察できてれば混乱しなかったはず。全探索しちゃえる制約に気付いたのにどうして無理に未証明O(1)に走ったんだか。

Eはどうすれば良かったんだか分からない。元々ゲーム問題は苦手だが、それでも「後ろから考える」「DP」「mod7でそれぞれの余りの可能性について考えていく」あたりまでちゃんと考えていたのに、詰めに全く手が付かなかった。解説も読めば一瞬で「まあそうだろうね」みたいに感じたんだけど、それでも解法が書けなかった。

mod7の0~6それぞれへの到達可能性を考える、といった思考のせいで、0の可能性・1の可能性・2の可能性…を分けて思考してしまったのが良くなかったのかもしれない。解説だと2次元DPで計算するのではなく1次元DPに集合を乗せて計算しているので、ひとまとまりのものとして考えやすい。もちろん実装上で大した違いはないかもしれないが、考える上での話として。

今回はゲーム問題がどうこうというよりも実はDPにやられていた可能性もあり。まあどっちも要練習。EDPCとか未だに埋めてないしやろうかな。

Fは直前にやってたABC187-Fの所為でクリークの話題に頭が接続されてしまった。3^72は絶対無理なのは流石に分かったので数学的考察でどうにかするんだろうという気はしたけど、全然頭が働かず終了。そっかあ素数の数でみると少ないのかあ。B-Aが少ないのを生かすんだろうなとは思ったけど、BやAが大きくてもB-Aさえ小さければ素数の数まで少なくなるのか。この論理ちょっとよく分かんないからこれも要復習。

---

出力されない妄想が溜まっていく。頭の中だけで公開されて頭の中だけで盛り上がって頭の中だけで完結する存在しない作品の思い出が次々に溜まっていく。それを見るためにニコ動を開いてもpixivを開いてもTwitterを開いてもどこにもそれが無いんだ。それは確かに深い世界観があって、みんなが感動するお話で、強いメッセージ性があって、俺もそれのファンの１人のはずなんだ。一緒に見た人とSNSで知り合って与太考察をゆるく語り合ったりできたはずなのに、俺以外の誰もそれを見たことが無いんだ。

誰かあれらを現実界に存在せしめてくれ。作品には完成する権利と公開される権利があるのに、俺にはその義務を果たせない…