概要

AtCoder Beginner Contest 333 の Implement 問題を解説します。難易度は A-D が初心者〜中級者向け、E はGreedy + スタック操作の基礎知识点が必要です。

A - Three Threes

入力された整数 \(n\) を \(n\) 回連続して出力する問題です。

制約が \(1 \le n \le 9\) と非常に小さいため、ループで単に出力すればOKです。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cout << n;
    cout << endl;
    return 0;
}

B - Pentagon

正五角形 \(ABCDE\) の顶点を等间隔に並べた circular order 上で、二本の線分の長さが等しいかどうかを判定します。

頂点名のアルファベット順（例: A=0, B=1…）とみなすと、両端の差の絶対値の少なくとも一方が等しい（または complement をとると等しくなる）ときに長さが一致します。

つまり、文字コード差 d = |c₂ - c₁| mod 5 で、長さは \min(d, 5-d)\) として識別できます。

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

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int d1 = abs(int(s1[1] - s1[0]));
    int d2 = abs(int(s2[1] - s2[0]));
    d1 = min(d1, 5 - d1);
    d2 = min(d2, 5 - d2);
    cout << (d1 == d2 ? "Yes" : "No") << endl;
    return 0;
}

C - Repunit Trio

「レピュニット数」とは 1, 11, 111, \dots\) のように、すべての桁が 1 である数です。

3つのレピュニット数の和として表せる数を小さい順に並べたときの n 番目を求めます。

n \le 333 と制約が小さいので、全探索で十分です。

ここで、レピュニット数 R_k = (10^k - 1)/9 であるため、k \le 12 程度まで計算すれば R_k > 10^{12} となり、十分大きな範囲をカバーできます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> reps;
    long long val = 0;
    for (int i = 0; i <= 13; i++) {
        val = val * 10 + 1;
        reps.push_back(val);
    }
    vector<long long> sums;
    for (int i = 0; i < reps.size(); i++)
        for (int j = i; j < reps.size(); j++)
            for (int k = j; k < reps.size(); k++)
                sums.push_back(reps[i] + reps[j] + reps[k]);
    sort(sums.begin(), sums.end());
    sums.erase(unique(sums.begin(), sums.end()), sums.end());
    cout << sums[n - 1] << endl;
    return 0;
}

D - Erase Leaves

無向木に対して、葉を葉削除操作（-degree-1の頂点削除）を繰り返して頂点 1 を削除するのに必要な最小回数を求めます。

頂点 1 を根と見立てると、它が削除されるには子孫のサブツリーのうち最大一つだけ残し、それ以外をすべて削除すれば最小回数になります。

つまり、頂点 1 の隣接点ごとのサブツリーのサイズをDFSで求め、最大のもの以外をすべて削除すればよく、答えは n - \max\_{\text{subtree}} size\) です。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector graph;
vector<bool> visited;

int dfs(int u) {
    visited[u] = true;
    int cnt = 1;
    for (int v : graph[u]) {
        if (!visited[v]) {
            cnt += dfs(v);
        }
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    graph.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int maxSub = 0;
    for (int child : graph[1]) {
        fill(visited.begin(), visited.end(), false);
        visited[1] = true;
        int sz = dfs(child);
        maxSub = max(maxSub, sz);
    }
    cout << n - maxSub << endl;
    return 0;
}

E - Takahashi Quest

nạn走順に処理されるイベント列があります。

• t_i = 1：属性 x_i の魔法の potion 袋を取得可能。
• t_i = 2：属性 x_i の敵出現。手持ちにその属性の potion があれば1つ消費して倒す。

すべての敵を倒す条件下で、「手持ち potion 数の最大値」を最小化してください。またそのときの各 potion の取得・使用状況を出力します。

Greedy: 尽量「]:

• 同じ属性 potion は「後勝先」discard（stack lifo）するのが最適。
• これにより、手持ちを濃密に保ち、最大数を抑える。

手順:

1. 各属性 x に遭遇した時間（index）を stack に格納。
2. 敵出現時、対応 stack が空なら不可（-1 出力）。
3. 非空なら栈顶 timestep を「使用済み」と标记。
4. もう一度シミュレートして、未使用 potion 時にカウントアップ、敵時にカウントダウンし、最大値を記録。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> type(n + 1), val(n + 1);
    vector posStacks(200005);
    vector<int> used(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> type[i] >> val[i];
        if (type[i] == 1) {
            posStacks[val[i]].push(i);
        } else {
            if (posStacks[val[i]].empty()) {
                cout << -1 << endl;
                return 0;
            }
            used[posStacks[val[i]].top()] = 1;
            posStacks[val[i]].pop();
        }
    }
    int cur = 0, mx = 0;
    vector<int> res(n + 1);
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            cur++;
            mx = max(mx, cur);
        } else if (type[i] == 2) {
            cur--;
        }
        if (type[i] == 1) res[i] = used[i];
    }
    cout << mx << endl;
    for (int i = 1; i <= n; i++) {
        if (type[i] == 1) cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}