AtCoder が提供しているABC（AtCoder Beginner Contest）391 C問題をC++とPythonで解いてみました。ABC391は、2025年2月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Pigeonhole Query（Difficulty : 209）
問題の詳細は、リンク先をご覧ください。
巣に何羽いるか、鳩がどの巣にいるか、複数の鳩がいる巣の個数を更新します。AtCoder Problems による Difficulty は 209 でした。
解答案
C++ プログラム例（ABC391C）
クエリ1で以下の値を更新します。
- それぞれの巣にいる鳩の数
c - 鳩がいる巣の番号
position - 複数の鳩がいる巣の個数
result- 鳩の移動元にいる鳩の数が2羽であれば、
resultを減らします。 - 鳩の移動先にいる鳩の数が1羽であれば、
resultを増やします。 - 移動後に、
cとpositionを更新します（28ー30行目）。
- 鳩の移動元にいる鳩の数が2羽であれば、
クエリ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 の問題を紹介していきます。
