Educational Codeforces Round 84 (Rated for Div. 2)

　Dより簡単なはずのEが解けず、DもHackされたという失敗回。Rateが付かなくて助かった。
　こういうことを何度もやっているため、Educational Codeforcesには苦手意識がある。

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

D. Infinite Path

　（ツイッターに書いた通りだけど）あるindex iからi→P[i]→P[P[i]]→……と変化するものが、どういう風にループするかを調べる。

　このループ上で同じ色が無限に続く可能性があるのは、このループの長さの約数のみ。なので、約数個飛ばしで同じ色が続いているものがあるかどうかを調べる。

E. Count The Blocks

たとえば、n=1の長さ1と、n=2の長さ2で答えは同じになる。
　一般に、n=kの長さlとn=k+1の長さl+1で答えが同じになることは、長さlのブロックに一つ数字を加えて長さl+1のブロックにすることで、全単射が構成できることから分かる。

　なので、各nについて、長さ1のブロックの個数を求めれば良い。

　余事象を使って漸化式を立てる方針が分かりやすいと思う（が、自分はコンテスト中この方針でやろうとして立式を失敗した）。
　が、端かそうでないかで場合分けすれば、そのまま立式することもできる。

F. AND Segments

　解説AC。アルメリアさんの解説記事、けんちょんさんの解説記事に分かりやすく解説されている。

・各桁ごとに独立に考えて良い

・DP[i]を、index iが0の（iまでの条件は満たしているような）個数とおく

　の二点に気付ければ、その後の累積和を用いたDP高速化はそれほど難しくないと思う。

　前者については、bitのandを考えるので、各桁ごとに考えようと思うのは自然。そう考えていれば各桁ごと独立というのも見えるはず（気付く前に解説を見てしまったけど……）。

　後者に気付くのは難しそう。

　ただ、「l～rのうち少なくとも一つが0」という条件を満たす個数を求めたいので、0が入る位置に着目するのはまあ自然か。

　その後の発想は、アルメリアさんのこの記事の方法と似ていると思う。与えられた条件を左から順番に見ていこう！　というのはCodeforcesでは典型といって良いと思うし、自然にできるようになりたいね。

　なお、解法を理解した後、実装にも苦労してしまいました。添え字はどうするのが分かりやすいのかな……。