全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder

1 年ぶりに rated に参加したの書いてみる。

結果は下の通りだった。 遅かったので決勝進出はできないけどギリギリ 500 位には入ったので自腹で遊びにいく権利はゲットした。

なんとレート変動 ±0。

A Subscribers

A にしては自頭要素多くない？

int main() {
    int n;
    int x, y;
    while (cin >> n >> x >> y) {
        int ma = min(x, y);
        int mi = max(0, x + y - n);
        cout << ma << ' ' << mi << endl;
    }
}

B Touitsu

i 番目の文字ごとに一番多いものに揃える。

int main() {
    int n;
    string a, b, c;
    while (cin >> n >> a >> b >> c) {
        int ans = 0;
        rep(i, n) {
            int cnt[256] = {};
            cnt[a[i]]++;
            cnt[b[i]]++;
            cnt[c[i]]++;
            int ma = *max_element(cnt, cnt + 256);
            ans += 3 - ma;
        }
        cout << ans << endl;
    }
}

C Different Strokes

D より難しかった。 先手は

• 残っている料理の中で A+B が最大
• 複数ある場合は A が最大

の料理を選ぶのが最適。後手も同様にする。

 
// score, a, b, id
using Tup = tuple<int, int, int, int>;
 
signed main() {
    int n;
    while (cin >> n) {
        priority_queue<Tup> ab[2];
        rep(i, n) {
            int a, b;
            cin >> a >> b;
            ab[0].emplace(a + b, a, b, i);
            ab[1].emplace(a + b, b, a, i);
        }
 
        vector<int> used(n, false);
        int score[2] = {};
        rep(i, n) {
            auto &que = ab[i&1];
            while (true) {
                int id = get<3>(que.top());
                if (used[id]) que.pop(); else break;
            }
 
            int ab, a, b, id;
            tie(ab, a, b, id) = que.top();
            que.pop();
            used[id] = true;
            score[i&1] += a;
            // dump(id);
            // dump(a);
            // dump(b);
        }
 
        cout << score[0] - score[1] << endl;
    }
}

ボドゲとか弱い人なのでこの問題を解くのに 40 分くらいかかった。

D Restore the Tree

この問題は言い換えると、各頂点について自身を終点とする辺が複数ある場合に、どれを元の根付き木の辺として使うか (どの始点が本当の親か) 選べという問題になる。

追加される辺は親から子孫の方向だけなので入力のグラフは DAG になる。DAG はトポソできる。 親と繋がっている辺はトポソしたときに一番後ろになるはずなのでそうする。

vector<vector<int>> g, rg;
int E;
 
vector<int> vis, arr, par, ord;

void tsort(int v) {
    vis[v] = true;
    for (auto &c : g[v]) {
        if (!vis[c]) tsort(c);
    }
    arr.push_back(v);
}
 
int main() {
    int n, m;
    while (cin >> n >> m) {
        E = n + m - 1;
        g.assign(n, {});
        rg.assign(n, {});
        rep(i, E) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            g[a].push_back(b);
            rg[b].push_back(a);
        }
 
        vis.assign(n, false);
        par.assign(n, -1);
        arr.clear();
        rep(i, n) if (!vis[i]) tsort(i);
        reverse(all(arr));
 
        ord.resize(n);
        rep(i, n) ord[arr[i]] = i;
        rep(v, n) {
            int par = -1;
            for (auto &src : rg[v]) {
                if (par == -1 || ord[par] < ord[src]) {
                    par = src;
                }
            }
            cout << par + 1 << '\n';
        }
        // puts("aaa");
    }
}

E 以降

元気があったら復習します。