結果

問題 No.335 門松宝くじ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:47:49
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,737 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 560,156 KB
最終ジャッジ日時 2025-06-12 20:49:24
合計ジャッジ時間 4,083 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 MLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

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

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

    def is_valid_triple(a, b, c):
        if a == b or b == c or a == c:
            return False
        sorted_nums = sorted([a, b, c])
        second = sorted_nums[1]
        if a == second or c == second:
            return True
        return False

    max_triple = {}
    for i in range(M):
        ticket = tickets[i]
        valid_triples = set()
        for x in range(N):
            for y in range(x+1, N):
                for z in range(y+1, N):
                    a = ticket[x]
                    b = ticket[y]
                    c = ticket[z]
                    if is_valid_triple(a, b, c):
                        max_val = max(a, b, c)
                        valid_triples.add((a, b, c, max_val))
        max_triple[i] = valid_triples

    def get_possible_c(ticket, a, b):
        seen = set()
        for x in range(len(ticket)):
            if ticket[x] == a or ticket[x] == b:
                for y in range(x+1, len(ticket)):
                    if ticket[y] == a or ticket[y] == b:
                        for z in range(y+1, len(ticket)):
                            c = ticket[z]
                            if c == a or c == b:
                                continue
                            if (a in (ticket[x], ticket[z])) or (b in (ticket[x], ticket[z])):
                                if is_valid_triple(ticket[x], ticket[y], ticket[z]):
                                    seen.add(c)
        return seen

    def compute_expected_value(ticket):
        total = 0
        count = 0
        for a in range(1, N+1):
            if a not in ticket:
                continue
            for b in range(a+1, N+1):
                if b not in ticket:
                    continue
                possible_c = get_possible_c(ticket, a, b)
                max_val = 0
                for c in possible_c:
                    current_max = max(a, b, c)
                    if current_max > max_val:
                        max_val = current_max
                total += max_val
                count += 1
        if count == 0:
            return 0.0
        return total / count

    max_expected = -1
    best_ticket = 0
    for i in range(M):
        ev = compute_expected_value(tickets[i])
        if ev > max_expected or (ev == max_expected and i < best_ticket):
            max_expected = ev
            best_ticket = i
    print(best_ticket)

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