AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 061 C- Big Array
一見簡単に見えるので、つい言われるがままの操作をして引っかかる人もいるだろう。制約が厳しい場合には、同じものはまとめたまま取り扱うという考え方をする必要がある。
# AtCoder Beginner Contest 061 C- Big Array
# https://atcoder.jp/contests/abc061/tasks/abc061_c
# tag: 考察
# 制約が大きいので、馬鹿正直に配列に数字を一個一個入れていくのはよくない。
# 下手すると 10^5 個の数字を 10^5 回入れた上で、ソートする羽目になる。
# 入れた数字の種類と個数だけを保存しておくのがいいだろう。
# 最終的に種類だけでソートし、後はそれぞれの数字が入っている個数を
# 確認しながら、上から K 番目の数字を確認すればいい。
def main():
N, K = map(int, input().split())
inserts = [list(map(int, input().split())) for _ in range(N)]
# カウント用の辞書を用意
counter = {}
# 順に見ていき、最終的に何がいくつ入っているのかをカウントしておく
for num, volume in inserts:
if num not in counter:
counter[num] = 0
counter[num] += volume
checked = 0
# 入っている数字をソートしつつ順に取り出していく
for num in sorted(counter.keys()):
# 求める順位が次の数字の個数で達成できるなら、その数字を回答
if checked <= K <= checked + counter[num]:
print(num)
return
# 足りないなら、数字の個数をチェック済みとして、次の数字を見る
checked += counter[num]
main()
関連
