コンテストへのリンク
コンテスト後のツイート
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での説明をスムーズにするためにそういう書き方にしているんだと思います。
問題への理解が深まるにつれ、解説記事（とその実装方法）の評価が高くなっていった……というのは良い解説だという証拠ですね。
0 件のコメント:
コメントを投稿