https://atcoder.jp/contests/abc245/tasks/abc245_c

解説

https://atcoder.jp/contests/abc245/submissions/30483611

やや丁寧めに説明ぞ書いていく。

何から始めていけばいい？

問題への取り組み方として、全列挙してみたり、実験してみたり、色々やってみることが大切である。
条件を満たす数列が存在するかの判定方法の一つとして、数列を列挙してみる方法がある。
以下のサンプルでやってみよう。

5 4  
9 8 7 7 2  
1 6 8 9 5

先頭から数列の数を決めていくとすると、AかBかから数を選択すればいいので、最初は

9  
1

の状態がありえる。ここから2番目の数を確定させるには、このありうる状態から8か6をくっつけていけばいい。
だが、前の数から4より大きくは離れることができないので、

98  
96

が状態として残る。次は78をくっつける。

次は79をくっつけるのだが、このままくっつけると更に倍になって管理が大変である。
倍倍になっていくのは嫌なので、ここで一旦手を止めて考えてみる。
今回は数列が作れるかを判定すればいいので、判定に利用されない最後の数以外はなんでもいい。
よって、「最後に何の数がある候補が残っているか」を管理することで、状態を「圧縮」することができる。

??7  
??8

このように最後がなんであるかという情報さえあれば数列が存在するかの全列挙が続行できることが分かった。
これならば状態は2以上に増えることはないし、手計算でも何とかなりそうである。

状態の圧縮

このように先頭からシミュレーションのように列挙をしていくのだが、ここまで作ることのできる数列について
「末尾が配列Aのものがあるか」「末尾が配列Bのものがあるか」さえ分かっていれば、そこから数列を伸ばすことができる。
自分の実装では

cur[ab] := ここまでのシミュレーションで数列ab (ab=0ならA, ab=1ならB)が末尾となる数列があるか

を持ちながら

nxt[ab] := 1手後のシミュレーションで数列ab (ab=0ならA, ab=1ならB)が末尾となる数列があるか

を作成している。
このように現在状態を圧縮しながらシミュレーションすることで、最終的に条件を満たす数列が存在するかを判定できる。
配列A,Bを合体して2次元配列としているので実装を読み解くのが難しいかもしれないが、頑張ってほしい。

その先へ

このような状態の圧縮は競技プログラミングでは頻出の考え方である。
とても広く適用できるので、意識していこう。
特に動的計画法では必須な考え方である。
今回のような問題でコツをつかんで、動的計画法に取り組んでもいいかもしれない。
（本質的には変わらないですが、この問題はDPでも解けます）

int N, K, AB[2][201010];
void _main() {
    cin >> N >> K;
    rep(ab, 0, 2) rep(i, 0, N) cin >> AB[ab][i];

    bool cur[2] = { true, true };
    bool nxt[2];
    rep(i, 1, N) {
        nxt[0] = nxt[1] = false;
        rep(from, 0, 2) if (cur[from]) rep(to, 0, 2) {
            if (abs(AB[from][i - 1] - AB[to][i]) <= K) nxt[to] = true;
        }
        cur[0] = nxt[0];
        cur[1] = nxt[1];
    }

    if (cur[0] || cur[1]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

Choose Elements [AtCoder Beginner Contest 245 C]

解説

何から始めていけばいい？

状態の圧縮

その先へ