九月

　八月はこのブログをサボってしまった（その間に、AtCoderでは青に落ちてしまった……）のですが、九月になったしぼちぼち復活させていくつもりです。

　今までのように、「復習が終わったら記事を書く」としていると、どんどん書くコンテストが溜まってしまうので、すぐに書けるものはすぐに書くなど、ちょっと変えていきたい。

yukicoder contest 242

　maspyさんの回ということでやる気はあったのに、不出来で残念。

コンテストへのリンク
コンテスト後のツイート

No.1017 Reiwa Sequence

　解説AC。
　鳩の巣原理を使うんだろうと思っても、使い方が意外と難しい。n個の要素を-1か+1を選ぶのは$2^n$通りなので早く発散しそう……と思えば、それらの和の値で抑えるのは自然なのだけれど。鳩の巣原理を使いなれていると思いつきやすいんだろうなぁ。

　その後の実装をどうするかも悩んだ。
　単純な$3^N$では間に合わないけど、半分全列挙するのは面倒だし……と。結局、解説の「計算方法（１）」の方法で実装したけど、この実装もちょっと思いつきにくい気がする。
　たとえば、indexの集合　S={1,2,4}, T={2,4,6,7}とで和が一致するとき、2,4という重複要素はどうするんだろう……と思ってしまった。この場合、同じ要素を足しても打ち消し合うのでそこは0にして、$A_1, -A_6,-A_7$が0になる。冷静に考えれば分かるけど……。

April Fools Day Contest 2020

　Codeforcesのエイプリルフールコンテストは、去年出たけど全然分からなくて辛かった記憶があった。それを考えれば今年は健闘したと思う。

コンテストへのリンク
コンテスト後のツイート

C. ...And after happily lived ever they

　題名の文法がおかしくて、"... and they lived happily ever after"の並び替えになっているというところに気付かなくちゃいけない。英語力の問題だけど、これが分からなかったのは情けない。

　その後、二進数にしたものを並び替えるパートも難しい気がするけど……。そこまで気付いてればできるものなのかな。たどり着いていないので何とも言えない。

D. Again?

　今解説読んだら、OEISはミスディレクションだったのですね。

E. Jordan Smiley

　ペイントに画像をコピーし、内側を黒で塗りつぶした後、Pythonで処理した。

　そのコードはこんな感じ。x=13.5というのは、切り取ったときの一マスの幅です。

from PIL import Image
import numpy as np

im = np.array(Image.open('jor.png'))

x=13.5
ANS=[[0]*64 for i in range(64)]

for i in range(64):
    for j in range(64):
        if (im[int(i*x+x/2)][int(j*x+x/2)]==[0,0,0]).all():
            ANS[i][j]=0
        else:
            ANS[i][j]=1

yukicoder April Fool Contest 2020

　エイプリルフールコンテストらしい問題と、普通の問題があった……くらいの感想しかないなぁ、と問題を見直していたらとんでもないことに気付いた。

コンテストへのリンク

No.3063 幅優先探索

　壁を通っても良かったらしいです。

　コンテスト中、このことに気付いてなかったのに一発で（一回TLEは出してるけど）ACしている！

　ということは実装を間違っていて、「壁はいけない」という条件を書かずにBFSしたということで……えーっと。

　かなり恥ずかしいミスですが、それでACになってしまうと気付かないですね。

　全然普通の問題じゃなかった！

No.3070 ソラニン

　これが解けなかったのは悔しい。

　検索して片方は見つけていたのだけど、fとg二つがあるということは、片方が「イイネ」で片方が「RT」だと思い込んで分からなくなってしまった。

　思い込みはよくない。

Codeforces Round #630 (Div. 2)

　Eまで解いた。Fはあまり考えなかったよう。

コンテストへのリンク
コンテスト後のツイート

D. Walk on Matrix

　 "bitwise AND"の演算では、0を作るのは簡単だし、桁が定まっているなら二進数表示で1111111という形の数とかけても値が変わらない。

　それを考えれば、0とkを作ろう、とするのは自然だと思う。

E. Height All the Same

　偶奇だけ考えれば良い問題であることは、実験すれば分かる。

　n*mが奇数のときはどのような場合でも構成できるが、n*mが偶数のときは、最初に置かれた個数が偶数個でなければ上手くいかない。その場合の数は大体半分に思えるけど、筋の良い証明方法が分からなかった。

　うーん、ただ、公式解説も結構技巧的だった。

　$k=R-L$として、（座標を適切に順序つけて）k個積み重なっていない最初の座標を xor 1する。そうすると、偶奇が変わるので、条件を満たすものと条件を満たさないもののペアができる。ただし、kが偶数のときは、条件を満たす方が一つ余る。だから、答えは、全体の半分か、半分+1になる、というもの。

　技巧的ではあるけれど、「ペアを作る」という考え方も、「xor 1を取ってペアにする」という考え方も重要なものではある。

　この問題についていえば、「直感的に半分になりそう」で答えを導ければ良いと思うけど、この証明方法も扱えるようになりたい。

F. Independent Set

　公式解説を読んで方針を理解してAC。

　木DP……と言われて木DPが何かをすぐ思い出せなかったのはまずい。根から葉の方向にDPを更新していく気がして、分岐でどうするんだろう……と思ってしまった。最近、全方位木DPの問題は何度か見たけど、木DPの問題を見ていなかった。

　葉から根に向けてDPを更新していくのですね。

　今回は、nodeと、そのnodeから根に向かうedgeの組について、「色を塗るかどうか」「誘導部分グラフを構成するときに使うかどうか」で場合分けして、この四通りのDPテーブルを埋めていけばOK。

　図を描いて落ち着いて考えれば遷移が分かりました。

G. No Monotone Triples

　アルメリアさんの解説記事を読んで解説AC。

　解かれている人数も少ないし公式解説も長いしで、普段なら手を出さないのですが、アルメリアさんが記事を書いている問題はACしないと！　と思って頑張りました。

　解説を理解するのはそれほど難しくない（これは、アルメリアさんの記事が図も入っていて丁寧だ、ということも大きいですが）けれど、自力で思いつくのは難しいタイプの問題だと思います。そして、実装が大変……。

　解説記事を読んで方針は分かったのですが、二分探索が必要なのか？　BITが必要なのか？　あたりで戸惑いました。

　そのあたりは今の自分の力だと実際に実装してみないと分からないですね。使わないで書けるのでは？　と思って実装してみたら上手く書けず、解説記事のやり方に落ち着く、というのを繰り返しました。

　厳密には、「長さ3の場合」は二分探索もBITもなしでやれますが、「長さ4の場合」は二分探索やBITとBIT上の二分探索が（自分の考えた限りでは）必要そうです。長さ3の場合での二分探索を使うなくしたらTLEが取れ、PyPyでもACできました。

　アルメリアさんの記事では長さ3の場合でもBIT等を使っていますが、長さ4での説明をスムーズにするためにそういう書き方にしているんだと思います。

　問題への理解が深まるにつれ、解説記事（とその実装方法）の評価が高くなっていった……というのは良い解説だという証拠ですね。

JOI 感謝祭 2020

　二完で部分点もほとんど取れない悲しい結果。
　双子のコンテストは解説がしっかりしてることもあって好きなのだけど、最近は良い結果が出せていませんね。

コンテストへのリンク
解説PDF
コンテスト後のツイート

鏡のような分割（Mirror-like Division）

　公式解説を参考に実装したら80点は取れました。

　再帰を使っていて、あまり良い実装ではないと思うので、上手く実装すればPython/PyPyでも100点取れるのかもしれないけど……。

　Nが47以下ということで、半分全列挙や、bit全探索がまず思いつくと思う。

　で、結局、半分全列挙でこそないものの、「半分に分けてbit全探索」（の高速化）が正しい解法。自然で思いつきやすい方針だと思うのに、なんで考え付かなかったんだろう……。

　解説スライドの最後、bit全探索をDFSで実装した方が速くなる、というのは意外でした。

塗り箸2（Chopsticks 2）

　問題文を理解するのに苦労しました。やること自体は分かりやすいんだけど、読み解くのが難しい……。特に、クエリについて、区間L～Rが変化するという設定は必要あったんだろうか？　一点変更クエリだけじゃ何かまずいことがあったのかな。

　解説を読んで46点は取りました。そこまでやればBIT＋座標圧縮は思いつけると思うので、そこから90点までは実装問題に見えます。

　一番の本質は、「中央値を求めればOK」というところだと思います。

　そう言われてもなぜそうなるのかすぐには分からなかったのですが、図を描くと分かりました。

　「大きくしたい値」（今回であれば奇数個目）と「小さくしたい値」（偶数個目）がそれぞれ何個かずつあるとします。

　このとき、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数が同じだけあれば、そこを境界にするのが最適です。（図を描いて考えると、そこからずれたらもっとコストがかかることが言えます）

　で、今回は、「大きくしたい値」と「小さくしたい値」の個数が同じなので、中央値を境界にすると、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数は同じになり、条件を満たします。

　こういうタイプの問題で中央値を考えるのは一つの定石だと思うので、思いつけるようになりたい。

AtCoder Beginner Contest 160

　Eまでは結構順調だったのに、一時間以上かけてFが解けず。全方位木DPだということは分かっていたのですが。

コンテストへのリンク
コンテスト後のツイート

F - Distributing Integers

　部分木のノード数と、答えをもって全方位木DP（rerooting）。
　この問題でも全方位木DPの実装にかなりの時間を取られている。

　コンテスト中TLEしてしまったのは、全方位木DPをしようとしているのに、前計算を利用できていないところがあり、二乗の計算量になってしまったためでした。
　これに気付けないのはまずい。


　復習のためと思ってもう一度書き直してみたのだけど、やはりかなり時間がかかってしまった上、また二乗で提出して一回TLEしてしまった……。

　全方位木DPは辺に関するDPとして理解している（一回目は葉から根の方向に、二回目は根から葉の方向に値を決める）のだけど、DPテーブルとしてはDP[node]=valueとするため、一回目と二回目で見る部分が違ってしまうのが混乱のもとだと思う。
　（一回目では、DP[x]でnode x→P[x]の辺に関する値を求めるため、xの子供たちを見れば良いけど、二回目では、DP[x]でnode P[x]→xの辺に関する値を求めるので、P[x]に繋がる辺たちを調べることになる。それが紛らわしい）

　これでいつも戸惑ってしまうのだけど、どうにかできないだろうか……。ちゃんとライブラリ化しなくちゃいけないのかな。