結果

問題 No.335 門松宝くじ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:57:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,013 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 85,308 KB
最終ジャッジ日時 2025-06-12 15:58:34
合計ジャッジ時間 6,793 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def is_valid(a, b, c):
    min_val = min(a, b, c)
    max_val = max(a, b, c)
    med_val = a + b + c - min_val - max_val
    return med_val == a or med_val == c

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):
        ticket = list(map(int, input[ptr:ptr+N]))
        ptr += N
        tickets.append(ticket)
    
    max_expected = -1.0
    best_index = 0
    
    for idx, ticket in enumerate(tickets):
        elements = ticket
        n = len(elements)
        sorted_z = []
        for j in range(n):
            current_z = elements[j+1:] if j+1 < n else []
            current_z_sorted = sorted(current_z, reverse=True)
            sorted_z.append(current_z_sorted)
        
        pos = {elem: i for i, elem in enumerate(elements)}
        sum_prize = 0
        
        for x in range(1, N+1):
            for y in range(1, N+1):
                if x == y:
                    continue
                if x not in pos or y not in pos:
                    continue
                i = pos[x]
                j = pos[y]
                prize = 0
                
                if i < j:
                    for z_val in sorted_z[j]:
                        if is_valid(x, y, z_val):
                            prize = max(x, y, z_val)
                            break
                elif j < i:
                    for z_val in sorted_z[i]:
                        if is_valid(y, x, z_val):
                            prize = max(y, x, z_val)
                            break
                sum_prize += prize
        
        total_pairs = N * (N - 1)
        expected = sum_prize / total_pairs if total_pairs != 0 else 0.0
        
        if expected > max_expected or (expected == max_expected and idx < best_index):
            max_expected = expected
            best_index = idx
    
    print(best_index)

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