結果

問題 No.3368 トッピング
コンテスト
ユーザー iro_
提出日時 2025-10-29 18:14:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 5,889 bytes
コンパイル時間 108 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 42,824 KB
最終ジャッジ日時 2025-11-17 20:39:59
合計ジャッジ時間 6,682 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # 入力の読み込み
    try:
        N, M, X, C = map(int, sys.stdin.readline().split())
        A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    except ValueError:
        print("入力エラー: N, M, X, C または A の形式が正しくありません。")
        return

    # -----------------------------------------------------------------
    # 判定関数: 満足度の最小値を K 以上にできるか？
    # -----------------------------------------------------------------
    def is_possible(K):
        
        # --- N=1 (エッジケース) ---
        if N == 1:
            if X > 0:
                return False  # ペナルティは発生し得ない
            
            max_score = -1
            for j in range(M):
                max_score = max(max_score, A[0][j])
            return max_score >= K

        # --- N >= 2 (DP) ---
        
        # DPテーブル: dp_curr[j][k]
        # 位置 i-1 がカテゴリ j, 位置 i がカテゴリ k のときの、
        # 位置 1 から i-1 までのペナルティ発生位置の最大総数
        # 到達不能は -1 で初期化
        dp_curr = [[-1] * M for _ in range(M)]

        # --- 初期化 (i=2) ---
        # j = cat[1], k = cat[2]
        for j in range(M):
            for k in range(M):
                is_penalized_1 = (j == k)
                score_1 = A[0][j] - (C if is_penalized_1 else 0)
                
                if score_1 >= K:
                    dp_curr[j][k] = 1 if is_penalized_1 else 0

        # --- DP遷移 (i = 3 to N) ---
        for i in range(3, N + 1):
            dp_prev = dp_curr
            dp_curr = [[-1] * M for _ in range(M)]
            
            # i-1 のスコアインデックス (A[score_idx])
            score_idx = i - 2 

            # DP遷移を高速化するための前計算 O(M^2)
            # precalc_no_penalty[j]:
            #   cat[i-2] != j かつ score[i-1] >= K を満たす j_prev からの
            #   max(dp_prev[j_prev][j] + 0)
            # precalc_with_penalty[j]:
            #   cat[i-2] == j かつ score[i-1] >= K を満たす j_prev からの
            #   max(dp_prev[j_prev][j] + 1)
            
            precalc_no_penalty = [-1] * M
            precalc_with_penalty = [-1] * M
            
            for j in range(M): # cat[i-1]
                val_no_penalty = A[score_idx][j]
                val_with_penalty = A[score_idx][j] - C
                
                max_A = -1 # (j_prev != j)
                max_B = -1 # (j_prev == j)

                for j_prev in range(M): # cat[i-2]
                    prev_count = dp_prev[j_prev][j]
                    if prev_count == -1:
                        continue
                    
                    if j == j_prev:
                        if val_with_penalty >= K:
                            max_B = max(max_B, prev_count + 1)
                    else:
                        if val_no_penalty >= K:
                            max_A = max(max_A, prev_count + 0)
                
                precalc_no_penalty[j] = max_A
                precalc_with_penalty[j] = max_B

            # dp_curr[j][k] の計算 O(M^2)
            for j in range(M): # cat[i-1]
                for k in range(M): # cat[i]
                    res = -1
                    
                    # (j == k) の場合 (位置 i-1 はペナルティ確定)
                    if j == k:
                        # (j_prev == j) からの遷移
                        res = max(res, precalc_with_penalty[j])
                        
                        # (j_prev != j) からの遷移
                        # この場合、i-1 は (j==k) のせいでペナルティを受ける
                        if A[score_idx][j] - C >= K:
                            if precalc_no_penalty[j] != -1:
                                # (dp_prev[j_prev][j] + 0) + 1
                                res = max(res, precalc_no_penalty[j] + 1)

                    # (j != k) の場合
                    else:
                        # (j_prev == j) からの遷移 (i-1 はペナルティ確定)
                        res = max(res, precalc_with_penalty[j])
                        
                        # (j_prev != j) からの遷移 (i-1 はペナルティなし)
                        res = max(res, precalc_no_penalty[j])

                    dp_curr[j][k] = res

        # --- 最終確認 (i = N の後) ---
        # dp_curr[j][k] には 1...N-1 までのペナルティ最大数が入っている
        # 最後に位置 N のスコアとペナルティを考慮する
        max_total_penalty = -1
        
        for j in range(M): # cat[N-1]
            for k in range(M): # cat[N]
                penalties_1_to_N_minus_1 = dp_curr[j][k]
                if penalties_1_to_N_minus_1 == -1:
                    continue
                
                is_penalized_N = (j == k)
                score_N = A[N - 1][k] - (C if is_penalized_N else 0)
                
                if score_N >= K:
                    penalty_N = 1 if is_penalized_N else 0
                    total = penalties_1_to_N_minus_1 + penalty_N
                    max_total_penalty = max(max_total_penalty, total)

        return max_total_penalty >= X

    # -----------------------------------------------------------------
    # 二分探索の実行
    # -----------------------------------------------------------------
    
    # L: 達成可能, R: 達成不可能
    # 答えの範囲 [0, max(A)+1]
    L = 0
    R = 10**15 + 7 # 十分大きな値 (Aijの最大値 + 1)

    while R - L > 1:
        mid = (L + R) // 2
        if is_possible(mid):
            L = mid
        else:
            R = mid

    print(L)

# スクリプトとして実行
if __name__ == "__main__":
    solve()
0