AtCoder Grand Contest 033 - エンジニア。

AtCoder Grand Contest 032はRatingは上がったけれど大した問題は解けなかったので割愛。

Google Code Jamも書かなきゃ。

幅探索だろうとは思いつつ、あまり実装してなかったので、複数のスタート地点をまとめても全く問題がないことに気が付くまで少しかかった。

で思いついたあとも幅探索でさくっと実装、なはずがpythonではTLE

atCoderではたまーにこういうことがあって、練習では飛ばしてたが本番なので、その場でPyCharmからCLionに切り替えて実装スタート。買っててよかったAll in One

まともに動かす環境すら整えてなかったので過去問の解答見つつ、ググって実装完了。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
    int H, W;
    cin >> H >> W;
    int ch[H][W];
    char c;
    queue<int> q1;
    queue<int> q2;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> c;
            if (c == '#') {
                q1.push(i);
                q2.push(j);
                ch[i][j] = 0;
            } else {
                ch[i][j] = 3000;
            }
        }
    }

    int m = 0;
    while (q1.empty() == false && q2.empty() == false) {
        int i = q1.front();
        q1.pop();
        int j = q2.front();
        q2.pop();
        for (int k = 0; k < 4; k++) {
            if (0 <= i + dy[k] && i + dy[k] < H && 0 <= j + dx[k] && j + dx[k] < W) {
                if (ch[i][j] + 1 < ch[i + dy[k]][j + dx[k]]) {
                    ch[i + dy[k]][j + dx[k]] = ch[i][j] + 1;
                    q1.push(i + dy[k]);
                    q2.push(j + dx[k]);
                    m = max(m, ch[i][j] + 1);
                }
            }
        }
    }
    cout << m << endl;
    return 0;
}

atcoder.jp

貪欲でよいか、動的計画にする必要があるか、それにしばらく時間を使う。まぁこれは価値ある時間の使い方だったと思う。結論としては、場合分けを行えば貪欲でよい。

「上下左右どちらに落ちるか」を決めた場合、それぞれ進める方向と戻す方向へ動かせるタイミングであれば、自分の得するほうへ動かせばよい。

ただし、戻しすぎて逆側に落ちないように注意する必要がある。

場合分けは高々4方向しかないため、計算量的にはO(N)で済む。

def solve(H, W, N, sr, sc, S, T):
    # Up
    i = sr
    for s, t in zip(S, T):
        if s == "U":
            i -= 1
        if i < 1:
            return False
        if t == "D" and i + 1 <= H:
            i += 1
    # Down
    i = sr
    for s, t in zip(S, T):
        if s == "D":
            i += 1
        if i > H:
            return False
        if t == "U" and i - 1 >= 1:
            i -= 1

    # Right
    i = sc
    for s, t in zip(S, T):
        if s == "R":
            i += 1
        if i > W:
            return False
        if t == "L" and i - 1 >= 1:
            i -= 1

    # Left
    i = sc
    for s, t in zip(S, T):
        if s == "L":
            i -= 1
        if i < 1:
            return False
        if t == "R" and i + 1 <= W:
            i += 1

    return True

if __name__ == "__main__":
    H, W, N = tuple(map(int, input().split(" ")))
    sr, sc = tuple(map(int, input().split(" ")))
    S = input()
    T = input()
    print("YES" if solve(H, W, N, sr, sc, S, T) else "NO")

水色になったことでBeginnerではRating変更がなく、コンテストががくっと減ってしまったので、最近はLeetcodeとアルゴリズム以外の勉強もしてる。まだまだ精進せな。