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

問題

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

一覧ページ

解法手順1

1. 入力を受け取り、全員の強さの合計Sを計算する。

2. Sが3で割り切れない場合、-1を出力して終了する。

3. 目標とする各チームの強さTをS/3として計算する。

4. DPテーブルを初期化する。dp[i][j]は、チーム1とチーム2の強さがそれぞれiとjになるために必要な最小の人数移動を表す。

5. 各人について、以下の3つの選択肢を考慮しながらDPテーブルを更新する：

   • 現在のチームにとどまる
   • チーム1に移動する
   • チーム2に移動する

6. すべての人を処理した後、dp[T][T]が最終的な答えとなる。

7. dp[T][T]が初期値（INF）のままの場合、均等化が不可能なため-1を出力する。
   そうでない場合、dp[T][T]を出力する。

ACコード1

ac.py

import sys
import logging

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)
    
    return logger

def io_func():
    # 標準入力から値を読み取る
    N = int(input())
    L = [list(map(int, input().split())) for _ in range(N)]
    return N, L

def solve(N, L, logger):
    logger.debug("処理を開始します")

    # 全員の強さの合計Sを計算
    S = sum(b for _, b in L)
    logger.debug(f"全員の強さの合計: S = {S}")

    # Sが3で割り切れない場合、-1を出力して終了
    if S % 3 != 0:
        logger.debug("Sが3で割り切れないため、均等化は不可能です")
        return -1

    # 目標とする各チームの強さTを計算
    T = S // 3
    logger.debug(f"目標とする各チームの強さ: T = {T}")

    # DPテーブルを初期化
    INF = 10**18
    dp = [[INF] * (T + 1) for _ in range(T + 1)]
    dp[0][0] = 0
    logger.debug("DPテーブルを初期化しました")

    # 各人について処理
    for i in range(N):
        a, b = L[i]
        logger.debug(f"{i+1}人目: チーム:{a}, 強さ: {b}")
        ndp = [[INF] * (T + 1) for _ in range(T + 1)]
        # 目標となる強さになるまで二重ループする
        for j in range(T + 1):
            for k in range(T + 1):
                if a == 1:
                    if j + b <= T:
                        ndp[j+b][k] = min(ndp[j+b][k], dp[j][k])
                        logger.debug(f"チーム1の強さが({j}+{b})、チーム2の強さが({k}) = min(チーム1の強さが({j}+{b})、チーム2の強さが({k}), チーム1の強さが({j})、チーム2の強さが({k}))")
                    if k + b <= T:
                        ndp[j][k+b] = min(ndp[j][k+b], dp[j][k] + 1)
                        logger.debug(f"#チーム2に移動した場合# チーム1の強さが({j})、チーム2の強さが({k}+{b}) = min(チーム1の強さが({j})、チーム2の強さが({k}+{b}), チーム1の強さが({j})、チーム2の強さが({k})+1)")
                    ndp[j][k] = min(ndp[j][k], dp[j][k] + 1)
                elif a == 2:
                    logger.debug(f"チーム:{a}の場合")
                    if j + b <= T:
                        ndp[j+b][k] = min(ndp[j+b][k], dp[j][k] + 1)
                    if k + b <= T:
                        ndp[j][k+b] = min(ndp[j][k+b], dp[j][k])
                    ndp[j][k] = min(ndp[j][k], dp[j][k] + 1)
                else:
                    logger.debug(f"チーム:{a}の場合")
                    if j + b <= T:
                        ndp[j+b][k] = min(ndp[j+b][k], dp[j][k] + 1)
                    if k + b <= T:
                        ndp[j][k+b] = min(ndp[j][k+b], dp[j][k] + 1)
                    ndp[j][k] = min(ndp[j][k], dp[j][k])
        dp = ndp
        logger.debug(f"{i+1}人目の処理が完了しました")

    # 結果の判定
    if dp[T][T] == INF:
        logger.debug("均等化が不可能です")
        return -1
    else:
        logger.debug(f"最小の人数移動: {dp[T][T]}")
        return dp[T][T]

def main():
    logger = setup_logger(debug_mode=False)
    N, L = io_func()
    result = solve(N, L, logger)
    print(result)

if __name__ == "__main__":
    main()

###
# N: 人数
# L: 各人の所属チームと強さのリスト
# S: 全員の強さの合計
# T: 目標とする各チームの強さ
# INF: 無限大を表す値
# dp: DPテーブル（dp[i][j]はチーム1とチーム2の強さがそれぞれiとjになるために必要な最小の人数移動）
# ndp: 更新用のDPテーブル

# 1. io_func関数: 標準入力から値を読み取る
# 2. solve関数: メインの処理を行う
#    - 全員の強さの合計Sを計算
#    - Sが3で割り切れない場合、-1を返す
#    - 目標とする各チームの強さTを計算
#    - DPテーブルを初期化
#    - 各人について処理を行い、DPテーブルを更新
#    - 結果を判定し、返す
# 3. main関数: プログラムのエントリーポイント
#    - ロガーの設定
#    - 入力の読み取り
#    - solve関数の呼び出し
#    - 結果の出力