ABC409 B問題 Citation
ABC409に参加して、AとB問題のみ正解できた。B問題に手こずったので、問題を振り返る。問題の意図を正しく理解できなかったのと、二重ループを恐れすぎていたことが失敗。
6月7日に開催されたAtCoder Beginners Contest 409に参加しましたが、今回はAとB問題しか正解できませんでした。それもB問題では不正解のコードを何度も提出してしまったので、その問題を振り返ります。
問題 B - Citation
数列が与えられ、条件を満たす\(x\)を答える問題です。問題を正しく理解出来なく誤回答 (WA)を繰り返したので、問題を引用します。
長さ\(N\)の非負整数列 \(A = (A_1, A_2, \cdots , A_N)\) が与えられます。次を満たす最大の非負整数\(x\)を求めてください。
- \(A\)に\(x\)以上の要素が重複を含め\(x\)回以上現れる。
この問題を読んで、与えられた数列の中から条件を満たす\(x\)を選ぶのだと考えてしまいました。しかしそうではなく、 純粋に連続した\(0 \cdots 100\)から条件を満たす\(x\)を選ぶのでした。そのため最大値が\(100\)と決まっています。
方法
コンテスト期間中に正解した方法
- 数列\(A\)の数は最大100なので、まず大きさ順にソートします。
- 小さい方から見ていって、条件を満たさなくなる\(A_i\)を探します。\(x\)より大きい数がいくつあるかは、配列のポインタから計算します。
- 小さい方から見てきて \(A_i\)が条件を満たさないということは、一つ前の\(A_{i-1}\)は条件を満たしていたことになります。そこで\(A_{i-1} \rightarrow A_i\)の間で条件を満たす\(x\)を探します。
n = int(input())
a = list(map(int, input().split()))
a.sort()
prev = -1
for i in range(len(a)):
if a[i] == prev:
continue
if a[i] > (n - i):
for x in range(a[i] - 1, prev, -1):
if x <= (n - i):
print(x)
exit()
print(prev)
exit()
prev = a[i]
# ↓これでACになったのは謎
print(a[-1])解説を読んでの方法
\(x\)は最大\(100\)なので難しく考えなくてよく、\(x\)を\(0, 1, 2, \cdots , 100\)と振って\(x\)以上の数字を数えればよかったのです。二重ループを恐れていましたが、最大でも\(100 \times 100 = 10^4\)でしか無いのです。
技術的工夫
単純に二重ループしてもOKとは言っても、できるだけループ回数を減らしたいです。そこで同じ値を毎回数えなくて良いように、\(A\)に含まれる値をDict型に入れて管理します。この値を登録する時にはkeyが登録されているかを判断する必要がありますが、指定したkeyがない時には自動的に作成されるdefaultdictを使用すると便利です。
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for i in range(len(a)):
d[a[i]] += 1
for x in range(101):
count = 0
for k, v in d.items():
if k >= x:
count += v
if count < x:
# 条件を満たさない。一つ前は満たしていたはず。
print(x-1)
exit()
# x = 100でも条件を満たしている
print(100)