【競技プログラミング】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: 求めるべき小さい順の位置

例として、最終的な配列が {1,2,2,3,3,3} の場合、4番目に小さい数は3となります。

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

一覧ページ
1回目の挑戦(AC)

アプローチ

挿入される数とその個数の組を保持し、ソートして効率的に処理を行う。
実際に配列を作成せずに、K番目の要素を特定する。

解法手順

1. 入力を受け取り、(ai, bi)のペアを配列に格納する。
2. 格納した配列を、aiの値でソートする。
3. ソートされた配列を順に走査し、以下の処理を行う：
   • 現在の要素のbi（個数）をKから引く。
   • Kが0以下になった時点で、その要素のaiがK番目に小さい数となる。
4. K番目に小さい数（ai）を出力する。

ACコード

ac.py

def io_func():
    # 入力を受け取る
    n, k = map(int, input().split())  # nとkを入力から取得
    pairs = []  # (ai, bi)のペアを格納するリスト
    for _ in range(n):
        a, b = map(int, input().split())  # aiとbiを入力から取得
        pairs.append((a, b))  # ペアをリストに追加
    return n, k, pairs

def solve(n, k, pairs):
    # ペアをaiの値でソート
    sorted_pairs = sorted(pairs)  # aiでソート

    # ソートされた配列を走査
    for a, b in sorted_pairs:
        k -= b  # 現在の要素の個数をkから引く
        if k <= 0:  # kが0以下になったら
            return a  # その要素のaiがK番目に小さい数

# メイン処理
n, k, pairs = io_func()  # 入力を受け取る
result = solve(n, k, pairs)  # 解を求める
print(result)  # 結果を出力

###
# 変数の意味:
# n: 入力される数の種類
# k: 求めるK番目の数
# pairs: (ai, bi)のペアを格納するリスト
# sorted_pairs: aiでソートされたpairsのリスト
# a: 現在処理中の数
# b: 現在処理中の数の個数
# result: K番目に小さい数

# 1. io_func関数:
#    - 標準入力からn, k, そして(ai, bi)のペアを読み込む
#    - 読み込んだデータを適切な形式で返す
# 2. solve関数:
#    - 入力されたペアをaiでソートする
#    - ソートされたペアを順に走査し、kから各要素の個数を引いていく
#    - kが0以下になった時点で、その要素のaiを返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して解を求める
#    - 結果を出力する