【競技プログラミング】AtCoder Beginner Contest 061_C問題

問題

要約

1. 空の配列が1つある。
2. この配列に対して、N回の挿入操作を行う。
3. i回目の操作（1 ≦ i ≦ N）では、整数aiをbi個配列に挿入する。
4. N回の挿入操作が終わった後、配列の中でK番目に小さい数を求める。

変数情報：

• N: 挿入操作の回数
• ai: i回目の操作で挿入する整数
• bi: i回目の操作でaiを挿入する個数
• K: 求めるべき小さい順の位置

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

挿入操作を実際に行わず、各整数とその出現回数を記録し、ソートを利用してK番目に小さい数見つける。

解法手順

1. 入力からN（操作回数）とK（求める順位）を読み取る。
2. N回の挿入操作を読み取り、各操作で[ai, bi]のペアを配列に格納する。
3. 格納した配列をaiの値でソートする。これにより、小さい数から順に処理できるようになる。
4. ソートされた配列を先頭から順に走査し、以下の処理を行う：
   • 現在の要素のbi（出現回数）をKから引く。
   • Kが0以下になった場合、その要素のai（整数値）がK番目に小さい数となる。
5. K番目に小さい数が見つかったら、その値を出力して終了する。

ACコード

ac.py

# 1. 入力からN（操作回数）とK（求める順位）を読み取る
a = input().split()  # 入力を空白で分割
a = list(map(int, a))  # 文字列のリストを整数のリストに変換

# 2. N回の挿入操作を読み取り、各操作で[ai, bi]のペアを配列に格納する
l = []  # 挿入操作を格納するリストを初期化
k = a[1]  # K（求める順位）を取得
for c in range(a[0]):  # N回のループ
    b = input().split()  # 各挿入操作を読み取り
    b = list(map(int, b))  # 文字列のリストを整数のリストに変換
    l.append(b)  # [ai, bi]のペアをリストに追加

# 3. 格納した配列をaiの値でソートする
l.sort()  # リストをaiの値でソート

# 4. ソートされた配列を先頭から順に走査し、処理を行う
st = True  # ループ継続フラグ
c = 0  # インデックスカウンタ
while st == True:
    k -= l[c][1]  # 現在の要素のbi（出現回数）をKから引く
    if k <= 0:  # Kが0以下になった場合
        st = False  # ループを終了
        print(l[c][0])  # 5. K番目に小さい数（ai）を出力
    c += 1  # 次の要素へ

机上トレース

n = 7
k = 13
ab = [[4, 3], [1, 3], [8, 5], [9, 1], [11, 4], [11, 2], [11, 3]]

N回の挿入操作を読み取り、各操作で[ai, bi]のペアを配列に格納する。

[[4, 3], [1, 3], [8, 5], [9, 1], [11, 4], [11, 2], [11, 3]]

格納した配列をaiの値でソートする。これにより、小さい数から順に処理できるようになる。

[[1, 3], [4, 3], [8, 5], [9, 1], [11, 2], [11, 3], [11, 4]]

ソートされた配列を先頭から順に走査し、以下の処理を行う：

現在の要素のbi（出現回数）をKから引く。

k = 13-3 = 10 # [1, 3]
k = 10-3 = 7 # [4, 3]
k = 7-5 = 2 # [8, 5]
k = 2-1 = 1 # [9, 1]
k = 1-2 = -1 # [11, 2]

Kが0以下になった場合、その要素のai（整数値）がK番目に小さい数となる。

ans = 11