コンテストページ: https://atcoder.jp/contests/abc291
コンテスト中AC:A〜E
Fは大方の解法まではコンテスト中に辿りついたが、最後の詰めと実装が間に合わず。コンテスト後に自力AC。

D - Flip Cards

カードの状態は表か裏かの2通りしかなく、状態数が少ないです。また、先頭(または末尾)から順に表裏を決めていくことができます。これより、DPが使えます。

$dp[i][j]:=$ $i$ 番目のカードの状態が $j$ の時の、 $i$ 番目までのカードの表裏の状態の総数。但し、 $j=\{0,1\}$ であり、 $j=0$ の時はカードは表向き、 $j=1$ の時はカードは裏向き

イメージとしては後述する数列 $T$ の個数を数え上げる問題とみなすと良いです。

数列 $T$ について、 $T_i=0$ なら $i$ 番目のカードは表向き、 $T_i=1$ なら裏向きとします。例えば、1〜4番目のカードについて、表、裏、裏、表なら $T=\{0,1,1,0\}$ です。

この状態で、5枚目のカードを表向きにしたとすると、 $T=\{0,1,1,0,0\}$ となり、裏向きにしたとすると、 $T=\{0,1,1,0,1\}$ となります。

この考え方で遷移を考えると、例えば、 $A_{i-1}\neq A_i$ なら、 $i-1$ 番目が表の全ての数列について、数列の末尾に $0$ を追加(すなわち、 $A_i$ を表向きに)して新たな数列ができるので、
dp[i][0] += dp[i-1][0]
という感じで遷移できます。

初期値は、 $i=1$ の時、 $\{0\}$ と $\{1\}$ の2つの数列があるので、 $dp[1][0]\leftarrow 1,\ dp[1][1]\leftarrow 1$ とし、あとは0にします。

答えは、 $dp[N][0]+dp[N][1]$ です。

E - Find Permutation

小さい順に数列の値を決定していくことを考えると、問題で与えられる大小関係に従って、決定順序を規定できます。そこで、この順序関係を有向辺とみなし、 $X_i \rightarrow Y_i$ という有向辺がある有向グラフを考えます。

まず、閉路を含む場合は矛盾が生じるため解なしとなりますが、制約上このケースはありません。(余談:この記事を書いているときに制約に気づきました。)

次に、順序が同列のものが存在すると、どちらから先に値を決定してもよくなるので、 $A$ を一意に特定できなくなり、Noとなります。
順序が同列のものが存在する例として、最もシンプルな形が入力例2です。

順序が同列のものが存在することの判定方法ですが、トポロジカルソートが利用できます。トポロジカルソートの詳細な説明はWebなどで検索すると出てくるため、ここでは割愛します。

トポロジカルソートで入次数0の頂点をキューに追加する際、同時に2つ以上の頂点がキューに入った場合、それらの順序を規定できません。従って、トポロジカルソートにおけるキューのサイズが2以上となったら、その時点で答えをNoにすれば良いです。

自分より番号が大きい頂点にしか辺が無く、更に辺が各頂点で最大でも10本しかないことを利用します。

頂点 $k$ を通らないことにした場合、 $k$ を飛び越えるような移動は、大雑把に考えても $max(k-10,1) \leq u \lt k$ の範囲の頂点 $u$ から、 $v\gt k$ となるような頂点 $v$ への移動に限定されます。つまり、

$1$ → $u$ → $v$ → $N$

という移動経路を考えれば良いです。この際の $1$ から $N$ への最短距離を

$1$ から $u$ への最短距離+ $u$ から $v$ への移動距離+ $v$ から $N$ への最短距離

と分解すれば、

を予め求めておくことで、

求めたい最短距離を $d^1_u + 1+d^N_v$ として、 $O(1)$ で計算できます。

$d^1$ は元のグラフをBFSする事で求められ、 $d^N$ は元のグラフの有向辺を全て逆向きにしてからBFSすることで求められます。

$k$ を固定した時の最短距離は $u$ と $u$ から出る辺を全探索すればよいです。
この計算量は $M=10$ のときがワーストケースですが、それでも $10^2$ であり、 $2\leq k \leq N-1$ の全てについて調べても $10^7$ くらいなので、間に合います。

コンテスト中は大雑把に考えていましたが、正確には $u$ の範囲は $max(k-M-1,1) \leq u \lt k$ だと思います。辺数も $M$ なので、計算量は $O(NM^2)$ になると思います。