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 の問題を紹介していきます。