Arc's blog

競プロなど

Mujin Programming Challenge 2018 を解いてみた

無人コン(参加者800人以上)の解法メモです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの文字と解法中の文字は無関係です

A - コンテスト名

文字列MUJINSを比較するだけ。

ソースコード

int main(void) {
    std::string s;
    std::string ans;
    cin >> s;
    ans = "MUJIN";
    for (int i = 0; i < 5; i++) {
        if (ans[i] != s[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - セキュリティ

一文字ずつ読んでシミュレート、0になったらYesを返して即return 0

一番最初に0人だった(A==0)場合もYesになることに注意。

ソースコード

int main(void) {
    cout << std::fixed << std::setprecision(10);
    int a;
    cin >> a;
    std::string s;
    cin >> s;

    if (a == 0) {
        cout << "Yes" << endl;
        return 0;
    }

    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '+') {
            a++;
        } else {
            a--;
        }
        if (a == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

C - 右折

解けてないです><

あるマスで右折するルートの総数は、

左、上、右、下に(そのマスを除いて).がa,b,c,d個並んでいた場合a*d+b*a+c*b+d*c=(a+c)*(b+d)で求められる

このことを利用していけばO(NM)で解けるはずです(通らないよぅ……)。

D - うほょじご

解法

準備

数の組に対して、

enum status { ns = 0, wj, wa, ac };
//ns(No Submission)は未確認
//wj(Waiting for Judging)は確認中
//wa(Wrong Answer)は無限回操作ができないと確定
//ac(Accepted)は無限回操作ができると確定

を定義する。

status grid[x][y]=(x,y)のstatusとしておく。

初期状態では(0,n)(n,0)(nは任意の整数)のみwa、その他はns

探索

あるnsの数の組(x,y)に対して、とりあえず一回操作をしてみる。

操作後の数の組(a,b)の状態によって、以下のことを行う。

grid[a][b]==nsの場合

grid[a][b]=wjとして、さらにstd::vector<std::pair<int, int>> vecに数の組をpush_back()しておく(後で役に立つ)。 vecは「探索中に通過したwjの状態の記録」として考えてください。

その後、(a,b)をもう一度操作。

grid[a][b]==waの場合

waになっている組になったら、その数の組が向かう先は(0,n)(n,0)しかない。

探索中に通った数の組についても同じことが言える。

vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=waにする。(vecに保存しないでgrid[][]を全探索すると時間が掛かるが、vecに保存すると計算量を落とせる)

grid[a][b]==ac、grid[a][b]==wjの場合

探索中にwjにたどり着いた場合、以降は無限回操作ができる。

また、無限回操作ができると確定した状態にたどり着いた場合、無限回操作ができる(それはそう)。

探索中に通った数の組は無限回操作が可能、と言えるので、vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=acにする。

仕上げ

あとはgrid[x][y]==acになっている場所を数えて終了。

ソースコード

void dp_search()となっていますが、DPと言えるかは人それぞれだと思います。

enum status { ns = 0, wj, wa, ac };

int n, m;
status grid[1000][1000];

int rev(int x) {
    int a, b, c;
    int reverse;
    if (x >= 100) {
        a = x / 100;
        x -= a * 100;
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 100 + b * 10 + a;
    } else if (x <= 9) {
        reverse = x;
    } else {
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 10 + b;
    }
    return reverse;
}

void dp_search(int x, int y, std::vector<std::pair<int, int>> vec) {
    if (grid[x][y] == wa) {
        //終了措置
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = wa;
        }

    } else if (grid[x][y] == ac || grid[x][y] == wj) {
        //成功措置
        grid[x][y] = ac;
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = ac;
        }
        return;
    } else {
        grid[x][y] = wj;
        if (x < y)
            x = rev(x);
        else
            y = rev(y);
        if (x < y)
            y -= x;
        else
            x -= y;
        vec.push_back(std::make_pair(x, y));
        dp_search(x, y, vec);
        return;
    }
}

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin >> n >> m;

    for (int i = 0; i <= 999; i++) {
        for (int j = 0; j <= 999; j++) {
            grid[i][j] = ns;
        }
    }
    for (int i = 0; i <= 999; i++) {
        grid[0][i] = wa;
        grid[i][0] = wa;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ns) {
                std::vector<std::pair<int, int>> vec;
                vec.push_back(std::make_pair(i, j));
                dp_search(i, j, vec);
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ac) {
                answer++;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

これ以降

やってません

まとめ

時間内では2完でした。

腕、落ちてないか?? 青になれるのか???