番目に小さい要素の取得、という2つの典型テクニックが要求される問題だったと思います。引用した記事でも言及されている平衡二分探索木についても、なるべく早く実装してみたいと思います。次に出会ったときはちゃんと倒したいところです。以前コンテストに参加して解けなかったものの復習です。数え上げの方法の典型度合いがものすごく高い気がしたので、別記事として書きました。列からなるグリッドを、黒・白の2色で塗り分けることを考える。塗り方は「辺に関して隣接しているグリッドについて、同じ色の隣接グリッドがたかだか1つまで」とする。割ったあまりで答えよ。複雑だが、「左上から少数のグリッドの色を確定させると、他のグリッドの色は自動的に決まる」というようなことはよくある(と思う)。以下の図のように、同じ色が連続してしまうと、その列を中心として次の行は一意に定まってしまう。1行目で同じ色が連続する場合よって、このようなバターンの総数を数え上げる必要がある(※)。以下の図のように、次の行の1列目の色を決めた時点で、他の列の色が確定してしまう。これは、(※)の部分と同じようにして数え上げることができる。黒・白が2つまで連続して良いという条件のもとでの、1次元グリッドの塗り分けの総数を求めることに集中できる。最初の色を黒として樹形図を書いてみる。DPによる数え上げ以上をもとにコーディングしていく。左上を白とした場合も数えるために2倍する、あたりを忘れないように注意する。自分にはあまり自明には感じられないので、説明がかなり冗長かもしれません。(A〜D解答)青になれました!やったね!思ったより長い戦いだった。「まぁ青ぐらいなら楽勝だろう」と思ったのですが、想像の3倍ぐらいは難しかったです。Codeforcesの1600はAtCoderの1400(水色の真ん中)ぐらいなんだろうなぁと感じています。今後もしばらくはこの調子で頑張りたいところです。ともに合成数になるようにする。