結果

問題 No.3137 Non-Intersect Chord Triangle Game
ユーザー navel_tos
提出日時 2025-05-03 19:15:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 1,411 bytes
コンパイル時間 737 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2025-05-03 19:15:25
合計ジャッジ時間 12,999 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3137 Non-Intersect Chord Triangle Game

#面白い
#考察: M = 0のとき、N = 2は先手必勝。6, 10, 14, ･･･ は(0, 3), (4, 7), ･･･ とすれば必勝
#それ以外の場合、再帰的に後手必勝と示せる
#線分をstackとして処理すればいい  まず、頂点0が線分の片方となるように適切にrotate
N, M = map(int, input().split())
lines = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

#コーナーケースを処理 不要かも
if M == 0 and (corner_case_care := False):
    exit( print('Akane' if N & 3 == 2 else 'Aoi') )

P = [-1] * N
for i, (Ai, Bi) in enumerate(lines):
    P[Ai] = P[Bi] = i
for offset in range(N):
    if P[offset] != -1: break
P = [ P[ (i - offset) % N ] for i in range(N) ]

#対となる端点同士を結んだとき、同一の深さの-1は何個あるか数えればよい
#D[d]: 現在の深さ(初期値は深さ0)の-1の個数 とすればよい
A = []
D = [0] * (N + 1)
d = 0
isclose = [0] * M
for i, Pi in enumerate(P):
    if Pi == -1:
        D[d] += 1
    else:
        if isclose[Pi] == 0:
            d += 1
            isclose[Pi] = 1
        else:
            A.append( D[d] )
            D[d] = 0
            d -= 1
A.append(D[0])
    
#先手必勝の条件がひとつ以上あるときのみ、そこを連打して勝ち
print('Akane' if any(Ai & 3 == 2 for Ai in A) else 'Aoi')
0