結果

問題 No.335 門松宝くじ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:11:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,862 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 111,272 KB
最終ジャッジ日時 2025-06-12 16:11:42
合計ジャッジ時間 7,127 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    tickets = []
    for _ in range(M):
        E = list(map(int, input[idx:idx+N]))
        idx += N
        tickets.append(E)
    
    best_idx = 0
    max_expected = -1
    
    for ticket_idx, E in enumerate(tickets):
        pos = [0] * (N + 1)  # pos[value] = index
        for i, val in enumerate(E):
            pos[val] = i
        
        # Precompute left_max, right_max, between_max
        left_max = [0] * N
        current_max = 0
        for j in range(N):
            left_max[j] = current_max
            if j < N - 1:
                current_max = max(current_max, E[j])
        
        right_max = [0] * N
        current_max = 0
        for j in range(N-1, -1, -1):
            right_max[j] = current_max
            if j > 0:
                current_max = max(current_max, E[j])
        
        between_max = [[0] * N for _ in range(N)]
        for i in range(N):
            current_max = 0
            for j in range(i+1, N):
                if j > i + 1:
                    current_max = max(current_max, E[j-1])
                between_max[i][j] = current_max
        
        max_val = [[0] * (N + 1) for _ in range(N + 1)]
        
        for x in range(1, N+1):
            for y in range(1, N+1):
                if x == y:
                    continue
                i = pos[x]
                j = pos[y]
                if i > j:
                    i, j = j, i
                max_z_after = right_max[j]
                max_z_between = between_max[i][j]
                max_z_before = left_max[i]
                
                candidates = []
                
                # Check after region (x, y, max_z_after)
                if max_z_after != 0 and max_z_after not in (x, y):
                    a, b, c = x, y, max_z_after
                    s1 = min(a, b, c)
                    s3 = max(a, b, c)
                    s2 = a + b + c - s1 - s3
                    if s2 == a or s2 == c:
                        candidates.append(s3)
                
                # Check between region (x, max_z_between, y)
                if max_z_between != 0 and max_z_between not in (x, y):
                    a, b, c = x, max_z_between, y
                    s1 = min(a, b, c)
                    s3 = max(a, b, c)
                    s2 = a + b + c - s1 - s3
                    if s2 == a or s2 == c:
                        candidates.append(s3)
                
                # Check before region (max_z_before, x, y)
                if max_z_before != 0 and max_z_before not in (x, y):
                    a, b, c = max_z_before, x, y
                    s1 = min(a, b, c)
                    s3 = max(a, b, c)
                    s2 = a + b + c - s1 - s3
                    if s2 == a or s2 == c:
                        candidates.append(s3)
                
                current_max_candidate = max(candidates) if candidates else 0
                if x < y:
                    if current_max_candidate > max_val[x][y]:
                        max_val[x][y] = current_max_candidate
                else:
                    if current_max_candidate > max_val[y][x]:
                        max_val[y][x] = current_max_candidate
        
        total = 0
        count = 0
        for x in range(1, N+1):
            for y in range(x+1, N+1):
                total += max_val[x][y]
                count += 1
        
        if count == 0:
            expected = 0.0
        else:
            expected = total / count
        
        if expected > max_expected or (expected == max_expected and ticket_idx < best_idx):
            max_expected = expected
            best_idx = ticket_idx
    
    print(best_idx)

if __name__ == '__main__':
    main()
0