AtCoder Beginner Contest 079 参加ログ

結果

　0WA、56:02で全完の374位だった。C,D問題でしっかり時間かかってしまうのでまだまだ実力不足だ。

A問題

　stringで受けて判定するだけ。まぁしかし2分かかった。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    if (s[1] != s[2]) {
        cout << "No" << endl;
    } else {
        if (s[0] == s[1] || s[2] == s[3]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

B問題

　なんか無駄に再帰を書いて、時間がかかるのでメモ化するという遠回りをした。普通にforループで良かったじゃん……。4分くらいかかった。

#include <bits/stdc++.h>
using namespace std;

vector<long long> memo;

long long ans(int n) {
    if (n == 0) {
        return 2;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    return memo[n] = ans(n - 1) + ans(n - 2);
}

int main()
{
    int N;
    cin >> N;
    memo.resize(N + 1);
    for (int i = 0; i <= N; i++) {
        memo[i] = -1;
    }
    cout << ans(N) << endl;
}

C問題

　わざわざdfsなる関数を書いて全探索しにいく。8通りくらいならif文全列挙でいいっていうの、気が付かないんだよなぁ。dfs書くのに手間取って13分くらいかかった。

#include <bits/stdc++.h>
using namespace std;
string ans;
int a[4];

void dfs(int pos, string str, int sum) {
    if (pos == 4) {
        if (sum == 7) {
            ans = str;
        }
        return;
    }
    dfs(pos + 1, str + '+', sum + a[pos]);
    dfs(pos + 1, str + '-', sum - a[pos]);
};

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < 4; i++) {
        a[i] = s[i] - '0';
    }
    dfs(1, "", a[0]);

    for (int i = 0; i < 3; ++i) {
        cout << s[i] << ans[i];
    }
    cout << s[3] << "=7" << endl;
}

D問題

　ダイクストラ法っぽくやっていくことしか頭に浮かばなくて、しかし普通とは逆向き？なのでかなり手こずる。35分以上かかってしまった。Nが小さいからワーシャルフロイドで一瞬なのになぁ。ただアルゴリズムを知っているだけで適切なタイミングで使えていない。もっと修行を積まないと。

　終わった番号を詰めていくvectorのendも使ってないので不要だろうし、ダイクストラ法っぽいものとして見たとしても出来がいいコードではない。最近まともに競技プログラミングやっていなかった分がそのまま表れているという感じ。電王トーナメントも終わったので、ちょっとは頑張っていきたい。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<int> > c(10, vector<int>(10, 0)), a(H, vector<int>(W, 0));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> c[i][j];
        }
    }
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            cin >> a[h][w];
        }
    }

    vector<int> min_cost(10, INT_MAX);
    vector<int> start, end;
    min_cost[1] = 0;
    for (int i = 0; i <= 9; i++) {
        if (i != 1) { 
            start.push_back(i);
        }
        min_cost[i] = c[i][1];
    }
    while (end.size() != 9) {
        int min_index = -1, min_value = INT_MAX;
        for (int i : start) {
            if (min_cost[i] < min_value) {
                min_value = min_cost[i];
                min_index = i;
            }
        }

        start.erase(find(start.begin(), start.end(), min_index));
        end.push_back(min_index);
        for (int i : start) {
            min_cost[i] = min(min_cost[i], min_cost[min_index] + c[i][min_index]);
        }
    }

    long long ans = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (a[h][w] == -1) {
                continue;
            }
            ans += min_cost[a[h][w]];
        }
    }
    cout << ans << endl;
}