#1169015 (PyPy3) No.3588 Already Ready

• 問題: No.3588 Already Ready
• ユーザー: marc2825
• 提出日時: 2026-06-13 16:55:58
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 5,188 bytes
• コンパイル時間: 234 ms
• コンパイル使用メモリ: 96,112 KB
• 実行使用メモリ: 115,200 KB
• 最終ジャッジ日時: 2026-07-10 21:02:21
• 合計ジャッジ時間: 6,025 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1 WA * 2
other	AC * 3 WA * 4 TLE * 1 -- * 61

ソースコード

import sys

def solve():
    # 入力の高速読み込み
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    A = [int(x) for x in data[3:]]
    
    # 1. 総試合数 T の計算と矛盾チェック
    sum_A = sum(A)
    if sum_A % (N + 1) != 0:
        print("-1")
        return
    
    T = sum_A // (N + 1)
    
    # 2. 各チームの必要勝利数 C の計算
    C = [0] * N
    for i in range(N):
        C[i] = A[i] - T
        if C[i] < 0:
            print("-1")
            return
            
    # 3. 最後の試合（T試合目）の整合性チェック
    # 最後の試合はチーム M が勝者。その直前に M は ready (スコア >= K) でなければならない
    # 最終スコア A[M-1] から逆算すると、直前のスコアは A[M-1] - 2
    if A[M-1] - 2 < K:
        print("-1")
        return
    # 最後の試合で M は勝つ必要があるので、C[M-1] は 1 以上であるはず
    if C[M-1] < 1:
        print("-1")
        return
    
    # 最後の試合の分をあらかじめ引いておく
    C[M-1] -= 1
    
    # 4. 1試合目から T-1 試合目までを貪欲にシミュレーション
    current_scores = [0] * N
    ans = []
    
    for t in range(1, T):
        chosen = -1
        
        # 辞書順最小にするため、1からN（インデックス 0からN-1）の順に試す
        for i in range(N):
            if C[i] == 0:
                continue
            
            # 条件①: この試合の開始直前に ready でないこと (S_i < K)
            if current_scores[i] >= K:
                continue
                
            # 仮にチーム i を勝者とした場合のシミュレーション
            # 次のステップへ進めるかどうかのチェック
            
            # チーム i を選んだと仮定して、一時的に更新
            C[i] -= 1
            
            # 残りの試合数
            rem_matches = T - 1 - t
            
            # 残りの試合で、全チームが「ready にならずに残りの勝利数 C を消化できるか」を判定
            # チーム i が勝った後のスコアを想定
            possible = True
            for j in range(N):
                if C[j] == 0:
                    continue
                
                # チーム j の現在の（この試合終了後の）スコア
                # 自分が勝者なら +2、それ以外なら +1
                next_score = current_scores[j] + (2 if j == i else 1)
                
                # チーム j が ready になるまでにあと何回勝てるか（勝利ボーナスを貰えるか）
                # スコアが K に達する直前、つまり max_score = K - 1 まで。
                # 1回勝つごとにスコアは全体への+1に加えてさらに+1されるので、
                # 「勝てる回数」の上限は (K - 1 - next_score) となる
                # ただし、最後の試合で勝つ M だけは、この制限の後にさらに1回勝てる（既に織り込み済み）
                if j != M - 1:
                    if next_score >= K:
                        # 既に ready なのにまだ勝利数が残っているのはアウト
                        possible = False
                        break
                    max_wins = K - 1 - next_score
                    if C[j] > max_wins:
                        possible = False
                        break
                else:
                    # チーム M の場合、最終戦(T試合目)で ready になっていれば良い
                    # T-1試合目終了時（rem_matches == 0 の時）に next_score >= K である必要がある
                    if rem_matches == 0 and next_score < K:
                        possible = False
                        break
                    
                    # M が残りの通常試合で勝てる上限
                    # 途中で ready になってはいけないので、やはり K-1-next_score が上限
                    if next_score < K:
                        max_wins = K - 1 - next_score
                        if C[j] > max_wins:
                            possible = False
                            break
                        
            if possible:
                chosen = i
                # 採用が決定したので、実際のスコアを更新
                for j in range(N):
                    current_scores[j] += 2 if j == chosen else 1
                ans.append(chosen + 1) # 1-indexed に戻す
                break
            else:
                # 不可だった場合は予定勝利数を元に戻して次のチームを試す
                C[i] += 1
                
        # どのチームも選べなかった場合は構成不可能
        if chosen == -1:
            print("-1")
            return

    # 最後に固定されている M を追加
    ans.append(M)
    
    # 結果を出力
    print(T)
    print(*(ans))

if __name__ == '__main__':
    solve()