AtCoder Grand Contest 034 A - KenKen Rase 解説

パッと見解けなくてビビってしまった
問題リンク : https://atcoder.jp/contests/agc034/tasks/agc034_a

問題概要

一列に並んだ個のマス目があり、左からAマス目とBマス目に駒が置かれている。
各マスには.か#が書かれており、#が書かれている、もしくは他の駒が置かれている場合、そのマスに駒を置くことはできない。 駒を右に1か2マスだけ動かせるとき、Aマス目に置かれていた駒をCマス目に、Bマス目に置かれていた駒をDマス目に移動させることはできるか。

制約

マス目は#でない

考察

をいい感じに使うんだろうなという気がする。
まずの場合について考えてみる。
例: A#B.#..#.#C..#D
このようなマス目を考えると、Bマス目の駒を先にDマス目まで移動させてしまえば、Aマス目からCマス目まで駒を動かす時に他の駒の位置を考える必要はない。 したがって、##のように駒を置けないマスが連続していない限り、題意は達成可能であるとわかる。
次に、の場合について考えてみる。先の例のとを入れ替えてみる。
例: A#B.#..#.#D..#C
実際に動かしてみると、題意が達成不可能なことがわかる。これはなぜかを考えると、
Bマス目の駒ををどのマスに動かしても、Aマス目の駒からみて##のように駒を置けないマスが連続してしまうためであることがわかる。 したがって、...のように駒を置けるマスが3つ以上連続している区間が(B-1)-D間に存在していればいい。

Submission

#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--, B--, C--, D--;
    bool ok = true;
    for(int i = A; i < C; i++){
        if(S[i] == S[i+1] && S[i] == '#') ok = false;
    }
    for(int i = B; i < D; i++){
        if(S[i] == S[i+1] && S[i] == '#') ok = false;
    }
    if(C > D){
        bool pass = false;
        for(int i = B-1; i < D; i++){
            if(S[i] == S[i+1] && S[i] == S[i+2] && S[i] == '.') pass = true;
        }
        if(pass == false) ok = false; 
    }
    
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

けんちょんさんの記事を参考にして書いたらパクリみたいになってしまった。