コンテストページ：https://codeforces.com/contest/1194

A - Remove a Progression(00:05)

飛ばされるのは奇数ですから、答えは 2x です。

B - Yet Another Crosses Problem(00:11)

交差点を全探索です。

予め各列と各行の白マスの数を数えておきましょう。それらを足して、真ん中も白マスならばそれは 2 回数えられていますから、1 引いておきましょう。

C - From S To T(00:17)

重複度的に足りていて、かつ部分列になっていればよいです。これらを確かめましょう。

重複度は、m(S)-m(T)+m(P) をして、負になっている成分がなければよいです。部分列パートは、T を先頭から見ていって、マッチするたびに S の上のポインターをずらしていくイメージで実装すると楽です。さらに T に番兵を入れておいて、それに到達したら NO とするともっと楽です。

D - 1-2-K Game(00:27)

K がなければ有名なゲームで、3 の倍数ならば Bob の勝ちです。

K が 3 の倍数ならば、残念なお知らせですが、状況は変わりません。そうでなければ、今度は K+1 で割った余りが、K でなくかつ 3 の倍数のときに Bob の勝ちです。

F - Crossword Expert(01:23)

お知らせ

E は飛ばししてしましました。

解法

i 以上となる確率 P_i を償却 Θ(mod) で求めましょう。すると、期待値は P_i の合計になります。

まず、 $a$ に 0 を挿入して累積和を取っておきましょう。 $P_i$ は、 $i+a_i+T \leq 0$ なうちは何しても OK ですから、 $1$ です。さらに $i+a_i+T \leq i$ なうちままだ可能性があります。こうなると、確率は $2^{-i} * f(i,T - a_i)$ （ただし $f$ は二項係数の累積和 $f(i,j) = \sum_{k=0}^j binom(i,k)$ です。）です。