AtCoder Beginner Contest 368

A,B,Cの3完。

レートは876→859の-17となり2週連続レートダウン。

5回ほど前のABCで過去最高の898を記録してから、850から900の間を行ったり来たりしている。

やはり何も対策しなかったらレートが落ちるのは当然だし、一度停滞期が来たからと言って諦めたくない。

今年中の青色へは毎回+50を記録しないといけないので相当気合を入れないといけないが、ちゃんと精進していけばレートが上がっていく余地はまだまだ感じるので、言い訳せずに時間を確保して精進するのみ。

A - Cut

昇順に並んでいる $N$ 枚からなるカードの山札を、山の下から $K$ 枚を取り出して、その順番を保ったまま上に重ねた時、上からどのような番号で並んだ状態になるか出力せよ、という問題。

まず $N - K$番から$N$番までのカードを出力し、その後$1$番から$N - K - 1$番までのカードを出力すればよい。

ll N,K;
ll A[1000009];

int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = N - K ; i < N; i++)
	{
		if (i != N - K) cout << " ";
		cout << A[i];
	}
	for (int i = 0; i < N - K; i++) cout << " " << A[i];
	cout << endl;
	return 0;
}

B - Decrease 2 max elements

長さ$N$の正整数列が与えられるので、降順にして前二つの要素を1引く操作を繰り返して、要素が0でないものが1つ以下になるまでの操作回数を求めよ。

ひたすら該当の操作を繰り返す素直な実装にし、降順に並び替えた時の $A[1]$ 、つまり2つ目に大きな要素が0になったら終了するようにする。

ll N;
vector<ll> A(1000009);

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	ll count = 0;
	while (1)
	{
		sort(A.begin(), A.begin() + N);
		reverse(A.begin(), A.begin() + N);
		if (A[1] == 0) break;
		A[0]--;
		A[1]--;
		count++;
	}
	cout << count << endl;
	return 0;
}

C - Triple Attack

$N$体の敵がいて、それぞれの体力が $A_i$ である。
0でカウントを始め、カウントが3の倍数の時には3ダメージを与え、そうでない時には1ダメージを与える。前の敵から体力が0以下になるように攻撃をする時、最終的なカウントはいくつになるか、という問題。

最初はひたすら該当の操作を繰り返す実装にしていたが、TLEしたので3回の攻撃を1セットと認識し、3回の攻撃の総和である5で何回攻撃できるかを計算するように計算量を改善した。

ll N;
ll A[1000009];

int main()
{
	cin >> N;
	vector<pair<ll, ll>> enemy(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	ll T = 0;
	ll num = 0;
	while (num < N)
	{
		ll tmp = A[num] / 5;
		A[num] = A[num] % 5;
		T += tmp * 3;
		while (A[num] > 0)
		{
			T++;
			if (T % 3 == 0) A[num] -= 3;
			else A[num]--;
		}
		num++;
	}
	cout << T << endl;
	return 0;
	
}

D - Minimum Steiner Tree

公式解説のpythonを見てcppで実装したコード。

考え方をわかりやすく説明すると、Union-Findのような木構造を思い浮かべたときに、葉（木構造の末端、それ以上下位の階層の分岐が存在しない）が条件を満たす頂点でなければ削除してさらに上位階層（親ノード）をチェックする、条件を満たす頂点だった場合はそれ以上上の階層は残す、という操作を繰り返す。それらを下記のプログラムでは幅優先探索で実装している。

int main() {
    int N, K;
    cin >> N >> K;

    vector<set<int>> edge(N);

    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; // 0-indexed に変換
        b--; // 0-indexed に変換
        edge[a].insert(b);
        edge[b].insert(a);
    }

    set<int> V;
    for (int i = 0; i < K; ++i) {
        int v;
        cin >> v;
        V.insert(v - 1); // 0-indexed に変換
    }

    vector<int> deg(N);
    for (int i = 0; i < N; ++i) {
        deg[i] = edge[i].size();
    }

    queue<int> q;
    for (int i = 0; i < N; ++i) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    int ans = N;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (V.find(v) != V.end()) continue;

        int vv = *edge[v].begin();
        edge[vv].erase(v);
        ans--;

        if (edge[vv].size() == 1) {
            q.push(vv);
        }
    }

    cout << ans << endl;

    return 0;
}