AtCoder が提供しているABC（AtCoder Beginner Contest）342 のB問題をC++とPythonで解いてみました。ABC342は、2024年2月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Which is ahead?（Difficulty : 57）
問題はリンク先をご覧ください。
制約が大きくないため、クエリ毎に調べました。AtCoder Problems による Difficulty は 57 でした。
解答案
C++ プログラム例（ABC342B）
調べる人数 $N$ が、$1 \leqq N \leqq 100$ と大きくはないため、クエリ毎に $A$ と $B$ のどちらが先に表れるか調べて、先に表れる方を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
for (int j = 0; j < n; ++j) {
if (p[j] == a) {
cout << a << endl;
break;
}
if (p[j] == b) {
cout << b << endl;
break;
}
}
}
return 0;
}あらかじめ、人の位置を記憶して判断すると計算量を減らすことができます。配列 order に位置を格納して、クエリ毎にどちらの位置が前か判断して出力します。計算量は減っていますが、制約が最大100なので、実行時間に差はほとんど見られませんでした。
プログラムは、以下となります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> order(n + 1);
for (int i = 0; i < n; ++i) {
int p;
cin >> p;
order[p] = i;
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
if (order[a] < order[b]) {
cout << a << endl;
} else {
cout << b << endl;
}
}
return 0;
}
どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC342B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 342 B"""
n = int(input())
p = list(map(int, input().split()))
q = int(input())
for i in range(q):
a, b = map(int, input().split())
for j in range(n):
if p[j] == a:
print(a)
break
if p[j] == b:
print(b)
break位置を格納する Pyhon プログラムは以下です。
"""AtCoder Beginner Contest 342 B"""
n = int(input())
p = list(map(int, input().split()))
order = [0] * (n + 1)
for i in range(n):
order[p[i]] = i
q = int(input())
for i in range(q):
a, b = map(int, input().split())
if order[a] < order[b]:
print(a)
else:
print(b)こちらも「AC」と判定されました。
最後に
制約を確認して、クエリを単純に書きました。解いていく速度も上がればと思います。
引き続き ABC の問題を紹介していきます。
