JOI 2023/2024 2次予選 問題１ 解答解説
この解説は、予選Aランク（本戦出場）を目指す人むけの解説になります。
（対象外：プログラムを習い始めたばかりの人、すでにAランクに到達している人）
そのため、説明をあえて省略した部分や、プログラムに冗長な部分があります。あらかじめご了承ください。
（万が一、記載内容に誤りや不備がありましたら、ご一報いただけますと幸いです）
A – カードゲーム 2 (Card Game 2)
問題 https://www2.ioi-jp.org/joi/2023/2024-yo2/2024-yo2-t1.html
AtCoder https://atcoder.jp/contests/joi2024yo2/tasks/joi2024_yo2_a
まずは、問題文を理解する（50点解答）
リストが与えられ、条件を満たすような組み合わせが存在するかを調べる問題です。
この手の問題は、まず全探索することを検討してください。
今回は３枚のカードの組み合わせが条件を満たすかを調べたいので、３重ループを行います。
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
for j in range(n):
for k in range(n):
if a[i] + 3 == a[j] and a[i] + 6 == a[k]:
print("Yes")
exit()
print("No")このプログラムは、小課題１と小課題３で得点でき、50点が得られます。
3重ループなので、計算量はO(N^3)となり、N=200,000のケースで8×10^15となりTLEになります。
誤った解法
forループの入れ子（ネスト）を取り除くため、以下のようなプログラムを書いている人が見受けられましたが、
listに対してinを使って検索するのは、内部的にはforループを使って前から順番に探す処理が行われるので、in句１つあたりの計算量がO(n)となり全体としてO(n^2)で高速化できません。
n = int(input())
a = list(map(int, input().split()))
for v in a:
if v + 3 in a and v + 6 in a:
print("Yes")
exit()
print("No")二分探索を用いた満点解法
N=200,000ということは、逆に考えるとO(n log n)であるソートは間に合います。
ソートができれば二分探索ができるので、以下のプログラムで満点回答が狙えます。
（このプログラムの二分探索は実装が甘いので、他で二分探索をしっかり理解することをおすすめします）
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
# x + 3を探す
ok = -1
ng = n
while ng - ok > 1:
mid = (ok + ng) // 2
if a[mid] <= a[i] + 3:
ok = mid
else:
ng = mid
if a[ok] != a[i] + 3:
continue
# x + 6を探す
ok = -1
ng = n
while ng - ok > 1:
mid = (ok + ng) // 2
if a[mid] <= a[i] + 6:
ok = mid
else:
ng = mid
if a[ok] != a[i] + 6:
continue
print("Yes")
exit()
print("No")二分探索は慣れるまでが大変ですが、コツをつかむと色々な問題で使えますのでぜひ習得してください。
setを用いた満点解法
そして、今回の問題ですがもっと簡単な解法があります。
setを使う方法です。
n = int(input())
a = set(map(int, input().split()))
for v in a:
if v + 3 in a and v + 6 in a:
print("Yes")
exit()
print("No")2つ目のプログラムのlistにしていたところ（2行目）をsetに変えるだけで満点回答になります。
setでは、要素の順番や重複した要素を管理できない代わりに、「指定した要素があるかないか」を基本的にO(1)で調べることができます。
n個の要素それぞれにO(1)で調べれば良いので、プログラム全体の計算量はO(n)となります。
今回の問題のように、カードに書かれた数字の順番の情報や同じ番号のカードの情報が必要ないときは積極的にsetを使ってください。
