AGC033

atcoder.jp
GWもあと少し。switchを少し前に買ったんですが、ちょっと誘惑に負けるとGWが溶けそうでやばいです。

AGCはAの1完。Aは幅優先探索かなーと一度Pythonで書いたんですが、どうしてもTLEで通らなさそうで。。仕方なくC++で書き直したんですが、C++忘れすぎていて30分くらいコンパイルエラーで苦しむことに。queueもx, y別々にしたけどまとめられたよなぁとか（pair<int, int>だった）、色々あったけど何とか通りました。

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main() {
    int W, H;
    cin >> H >> W;

    int dist[H][W];
    deque<int> xvec;
    deque<int> yvec;

    for (int i = 0; i < H; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < W; ++j) {
            if (s[j] == '#') {
                dist[i][j] = 0;
                xvec.push_back(j);
                yvec.push_back(i);
            } else {
                dist[i][j] = -1;
            }
        }
    }

    int max_dist_count = 0;
    while (xvec.size() != 0) {
        int y = yvec.front();
        yvec.pop_front();
        int x = xvec.front();
        xvec.pop_front();
        int dist_count = dist[y][x] + 1;
        if (x < W - 1 && dist[y][x+1] == -1) {
            dist[y][x+1] = dist_count;
            yvec.push_back(y);
            xvec.push_back(x+1);
            max_dist_count = dist_count;
        }
        if (y < H - 1 && dist[y+1][x] == -1) {
            dist[y+1][x] = dist_count;
            yvec.push_back(y+1);
            xvec.push_back(x);
            max_dist_count = dist_count;
        }
        if (0 < x && dist[y][x-1] == -1) {
            dist[y][x-1] = dist_count;
            yvec.push_back(y);
            xvec.push_back(x-1);
            max_dist_count = dist_count;
        }
        if (0 < y && dist[y-1][x] == -1) {
            dist[y-1][x] = dist_count;
            yvec.push_back(y-1);
            xvec.push_back(x);
            max_dist_count = dist_count;
        }
    }

    cout << max_dist_count;
}

Bは時間切れ後にちょっと考えて、先手はひたすら左、後手はひたすら右に動かすみたいなシミュレーションを4方向それぞれスタートから行う方法で通りましたが、解説聞くとどうもそれは真の解答ではないらしいという。。

こういう、最終的な状態(今回は、駒がどこかにいて生存しているかor途中どこかで落とされるか)への辿り着き方が、途中の状態が色々ありえてよくわからない場合は逆から考えるというのがセオリーなようです。グラフ理論的な、状態一つ一つがノードになったものをイメージしてみると、自分の今いるノードがゴールに辿り着くのか、スタートから考えるとわからないまま進むことになるわけですが、ゴールから辿ると確実にゴールに着くノードを全て洗い出すことができます。

今回は、最後の各マス上で生存している状態をゴールとして逆から辿っていって、スタートの状態にすることができれば生存ルートがあるということで後手勝ち、という塩梅のようでした。いやーむずいっす。シミュレーションでの解答も一見良さそうだけどどういう反例があるんだろうか。