【競技プログラミング】AtCoder Beginner Contest 373_E問題

問題

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

一覧ページ

Before

AtCoder Beginner Contest 373_D 問題

Next

AtCoder Beginner Contest 374_C 問題

その他・記事まとめ

Unity関連 / Qiita

解法手順1

解法イメージ

下記のように、当選出来る票数を二分探索で探す問題ね。

問題の概要

N人の候補者がいて、合計K票のうち一部が開票済み（各候補者Ai票）。
残り票をどのように配分してもよいとき、各候補者iが「必ず当選する」ために追加で必要な最小票数Xを求める問題。
当選条件は「最終的に自分より多い票を得る候補者がM人未満であること」です。

解法のステップバイステップ解説

1. 問題の形式化

• 残り票数：$ R = K - \sum_{j=1}^N A_j $
• 各候補者iについて、「追加でX票もらったとき、どんな残り票の配分でも必ず当選できる最小のX」を求める。

2. 必ず当選する条件の定式化

• 候補者iがX票追加でもらったと仮定し、他の候補者に残り票が最悪な形（iの当選を阻害するよう最大限配分）で配られるケースを考える。
• つまり、「i以外のM人がiより多い票を取る」ことが絶対に不可能になる最小Xを求める。

3. 二分探索による最小Xの決定

各候補者iについて、Xを0からRまで二分探索し、以下の判定を行う

• iにX票追加、他の候補者には残り票R-Xを好きなように配れるとき、iより多い票を得る候補者がM人未満にできるか？

判定方法：

1. i以外の候補者の現在の票数を降順にソート
2. iの得票数は$ A_i + X $
3. i以外の候補者のうち、iの得票数以上になるのに必要な追加票数を計算し、上位M人にその分だけ票を与える
4. その合計がR-Xを超えるなら「不可能」→Xを増やす、超えないなら「可能」→Xを減らす

4. 実装の流れ

• 各候補者iについて上記の二分探索を行い、最小のXを求める
• ただし、XがRを超える場合や、どんなXでも達成不可能な場合は-1を出力

5. 特殊ケース

• 既にM人未満しか自分より多い票の候補者がいない場合はX=0
• 残り票を全てもらってもM人以上が自分より多い票になる場合はX=-1

ACコード1(logger設定しているとTLE)

ac.py

import logging
from bisect import bisect_right

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

def io_func():
    # 入力値の取得
    N, M, K = map(int, input().split())
    votes = list(map(int, input().split()))
    return N, M, K, votes

def solve(N, M, K, votes, logger=False):
    # logger.debug(f"入力値 N={N}, M={M}, K={K}, votes={votes}")

    if M == N:
        # logger.debug("全員当選ケース。全員の必要票数は0。")
        print(*([0] * N))
        return

    # 各候補者の票数と元のインデックスを保持
    candidates = [(votes[i], i) for i in range(N)]
    # logger.debug(f"候補者リスト（票数, インデックス）: {candidates}")

    candidates.sort(reverse=True)
    # logger.debug(f"票数降順ソート後: {candidates}")

    rest_votes = K - sum(votes)
    # logger.debug(f"残り票数: {rest_votes}")

    result = [0] * N
    sorted_votes = sorted(votes, reverse=True)
    # logger.debug(f"票数降順リスト: {sorted_votes}")

    prefix_sum = [0] * N
    for i in range(N):
        prefix_sum[i] = prefix_sum[i - 1] + sorted_votes[i] if i > 0 else sorted_votes[0]
    # logger.debug(f"票数の累積和: {prefix_sum}")

    reversed_votes = sorted_votes[::-1]

    for idx in range(N):
        current_vote = candidates[idx][0]
        original_index = candidates[idx][1]
        # logger.debug(f"{idx+1}番目候補者（元インデックス{original_index}）の現在の票数: {current_vote}")

        if current_vote + rest_votes < sorted_votes[M - 1]:
            # logger.debug(f"候補者{original_index+1}: 追加票を全て得ても当選不可。-1を記録。")
            result[original_index] = -1
            continue

        left = max(0, sorted_votes[M - 1] - current_vote)
        right = rest_votes
        # logger.debug(f"候補者{original_index+1}: 二分探索開始 left={left}, right={right}")

        while left < right:
            mid = (left + right) // 2
            target_vote = current_vote + mid
            higher_count = N - bisect_right(reversed_votes, target_vote)
            # logger.debug(f"mid={mid}, target_vote={target_vote}, higher_count={higher_count}")

            total = 0
            if higher_count > 0:
                total += (target_vote + 1) * higher_count
                total += prefix_sum[M - 1] - (prefix_sum[higher_count - 1] if higher_count - 1 >= 0 else 0)
            else:
                total += prefix_sum[M - 1]
            # logger.debug(f"total（上位候補者分）: {total}")

            if idx < M:
                total += sorted_votes[M] if M < N else 0
            else:
                total += sorted_votes[idx]
            # logger.debug(f"total（自身分加算後）: {total}")

            if total + rest_votes >= (target_vote + 1) * M + target_vote:
                left = mid + 1
                # logger.debug(f"条件を満たすためleftを増やす: left={left}")
            else:
                right = mid
                # logger.debug(f"条件を満たさないためrightを減らす: right={right}")

            if left == right:
                break

        # logger.debug(f"候補者{original_index+1}: 必要な追加票数={left}")
        result[original_index] = left

    # logger.debug(f"最終結果: {result}")
    print(*result)

def main():
    logger = setup_logger(debug_mode=False)
    N, M, K, votes = io_func()
    solve(N, M, K, votes, logger)

if __name__ == "__main__":
    main()