結果

問題 No.335 門松宝くじ
ユーザー lam6er
提出日時 2025-04-15 23:07:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,341 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 92,748 KB
最終ジャッジ日時 2025-04-15 23:10:10
合計ジャッジ時間 4,727 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    tickets = []
    for _ in range(M):
        E = list(map(int, input[ptr:ptr+N]))
        ptr += N
        tickets.append(E)

    max_expected = -1
    best_idx = 0

    for idx in range(M):
        E = tickets[idx]
        pos = [0] * (N + 1)  # pos[x] gives the index in E where x is found
        for i in range(N):
            pos[E[i]] = i

        # Precompute max_range[i][j] which is the maximum in E[i..j] inclusive
        max_range = [[0]*N for _ in range(N)]
        for i in range(N):
            max_val = E[i]
            max_range[i][i] = max_val
            for j in range(i+1, N):
                if E[j] > max_val:
                    max_val = E[j]
                max_range[i][j] = max_val

        total = 0
        total_pairs = N * (N-1)

        for a in range(1, N+1):
            for b in range(1, N+1):
                if a == b:
                    continue
                i_a = pos[a]
                i_b = pos[b]
                if i_a > i_b:
                    i_a, i_b = i_b, i_a
                    a, b = b, a

                # Now i_a < i_b
                # Case 1: after i_b
                if i_b + 1 < N:
                    start = i_b + 1
                    end = N - 1
                    c1 = max_range[start][end]
                else:
                    c1 = None

                # Case 2: between i_a and i_b
                if i_a + 1 <= i_b - 1:
                    start = i_a + 1
                    end = i_b - 1
                    c2 = max_range[start][end]
                else:
                    c2 = None

                # Case 3: before i_a
                if i_a - 1 >= 0:
                    start = 0
                    end = i_a - 1
                    c3 = max_range[start][end]
                else:
                    c3 = None

                max_prize = 0

                # Check case 1: a, b, c1
                if c1 is not None:
                    sorted_trio = sorted([a, b, c1])
                    if sorted_trio[1] == a or sorted_trio[1] == c1:
                        current_max = max(a, b, c1)
                        if current_max > max_prize:
                            max_prize = current_max

                # Check case 2: a, c2, b
                if c2 is not None:
                    sorted_trio = sorted([a, c2, b])
                    if sorted_trio[1] == a or sorted_trio[1] == b:
                        current_max = max(a, b, c2)
                        if current_max > max_prize:
                            max_prize = current_max

                # Check case 3: c3, a, b
                if c3 is not None:
                    sorted_trio = sorted([c3, a, b])
                    if sorted_trio[1] == c3 or sorted_trio[1] == b:
                        current_max = max(a, b, c3)
                        if current_max > max_prize:
                            max_prize = current_max

                total += max_prize

        expected = total / (N * (N - 1) // 2)

        if expected > max_expected or (expected == max_expected and idx < best_idx):
            max_expected = expected
            best_idx = idx

    print(best_idx)

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