結果

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

ソースコード

diff # 

import sys

def solve():
    try:
        N, M = map(int, sys.stdin.readline().split())
        A = []
        for _ in range(N):
            A.append(list(map(int, sys.stdin.readline().split())))
    except ValueError:
        print("入力エラー")
        return

    # 判定問題: O(N M^2) に高速化
    def check(X):
        valid = [[A[i][j] >= X for j in range(M)] for i in range(N)]
        can_be_adj = [[A[i][j] >= X + 1 for j in range(M)] for i in range(N)]

        for k_start in range(M):
            if not valid[0][k_start]:
                continue

            dp = [[False] * M for _ in range(N)]
            count_true_dp = [0] * N # 各行の True の数をカウントする配列

            # --- DP初期化 (i = 0) ---
            dp[0][k_start] = True
            count_true_dp[0] = 1

            # --- DP遷移 (i = 1 から N-1) ---
            for i in range(1, N):
                count_prev = count_true_dp[i-1]
                if count_prev == 0:
                    # 前の行に True が 0 個なら、それ以上進めない
                    break
                
                for j in range(M): # i番目に置く種類 j
                    if not valid[i][j]:
                        continue
                    
                    # --- 高速化した遷移判定 (O(1)) ---
                    
                    # 1. k_prev != j (隣が違う) からの遷移
                    transition_other = False
                    if count_prev > 1:
                        transition_other = True
                    elif count_prev == 1 and not dp[i-1][j]:
                        transition_other = True
                    
                    # 2. k_prev == j (隣が同じ) からの遷移
                    transition_same = False
                    if dp[i-1][j] and can_be_adj[i-1][j] and can_be_adj[i][j]:
                        transition_same = True

                    # どちらかで遷移できれば OK
                    if transition_other or transition_same:
                        dp[i][j] = True
                        count_true_dp[i] += 1
            
            # --- 最終チェック (つなぎ目: N-1 と 0) ---
            if count_true_dp[N-1] == 0:
                continue # この k_start では N-1 まで到達できなかった

            for j_final in range(M): 
                if not dp[N-1][j_final]:
                    continue

                if k_start == j_final:
                    if can_be_adj[0][k_start] and can_be_adj[N-1][j_final]:
                        return True
                else:
                    return True

        return False

    # --- 二分探索 ---
    low = 0
    high = 10**9 + 7
    ans = 0

    while low <= high:
        mid = (low + high) // 2
        if check(mid):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1

    print(ans)

# 実行
solve()
0