AtCoder

ABC391 C問題(Pigeonhole Query)を解く

AtCoder_ABC391_C

AtCoder が提供しているABC(AtCoder Beginner Contest)391 C問題をC++とPythonで解いてみました。ABC391は、2025年2月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Pigeonhole Query(Difficulty : 209)

問題の詳細は、リンク先をご覧ください。

ABC391 C問題 Pigeonhole Query

巣に何羽いるか、鳩がどの巣にいるか、複数の鳩がいる巣の個数を更新します。AtCoder Problems による Difficulty は 209 でした。

解答案

C++ プログラム例(ABC391C)

クエリ1で以下の値を更新します。

  • それぞれの巣にいる鳩の数 c
  • 鳩がいる巣の番号 position
  • 複数の鳩がいる巣の個数 result
    • 鳩の移動元にいる鳩の数が2羽であれば、result を減らします。
    • 鳩の移動先にいる鳩の数が1羽であれば、result を増やします。
    • 移動後に、cposition を更新します(28ー30行目)。

クエリ2で result の値を出力します。以下が、C++プログラムです。

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

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> c(n, 1);
	vector<int> position(n);
	for (int i = 0; i < n; ++i) {
		position[i] = i;
	}
	int result = 0;
	for (int i = 0; i < q; ++i) {
		int type;
		cin >> type;
		if (type == 1) {
			int p, h;
			cin >> p >> h;
			--p;
			--h;
			if (c[position[p]] == 2) {
				--result;
			}
			if (c[h] == 1) {
				++result;
			}
			--c[position[p]];
			++c[h];
			position[p] = h;
		} else if (type == 2) {
			cout << result << endl;
		}
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC391C)

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 391 C"""
n, q = map(int, input().split())

c = [1] * n
position = [0] * n
for i in range(n):
    position[i] = i
result = 0
for i in range(q):
    query = list(map(int, input().split()))
    t = query[0]
    if t == 1:
        p = query[1] - 1
        h = query[2] - 1
        if c[position[p]] == 2:
            result -= 1
        if c[h] == 1:
            result += 1
        c[position[p]] -= 1
        c[h] += 1
        position[p] = h
    elif t == 2:
        print(result)

こちらも「AC」と判定されました。

最後に

素直に管理すれば解ける問題でした。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA