−目次

ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）F,G問題メモ
- F - ABCBA
  - 問題文
  - 制約
  - 解法
  - 解法2
- G - Not Only Tree Game
  - 問題文
  - 制約
  - 解法

ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）F,G問題メモ

ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）

コンテストのトップページの背景をクリックすると反応がある。ちょっとおしゃれ。

F - ABCBA

問題文

$S$ を接頭辞に持つ最短の回文を $1$ つ求めてください。

制約

$S$ は英大文字からなる長さ $1$ 以上 $500000$ 以下の文字列

解法

回文ということで、Manacherアルゴリズムを知っていれば割と自然にこれを使えばよいことに気づける。

「 $S$ の接尾辞で、最長の回文」がわかればよい。

S   ABCABC ABCDEEDCBA
           ~~~~~~~~~~    接尾辞で最長の回文
               ↓
    ABCABC ABCDEEDCBA CBACBA    回文以外の部分を反転させて後ろに付けるとできあがり

Manacherは、文字列 $S$ が与えられると各文字について「その文字を中心とする最長の回文の半径」を $O(|S|)$ で求められる。

ただし奇数長の回文しか見つけられないので、 $S$ に出てこない文字を各文字の間に挟み込むと、偶数長の回文も見つけられる。

S'  $A$B$C$A$B$C$A$B$C$D$E$E$D$C$B$A$
                ~~~~~~~~~~^~~~~~~~~~~

0-indexで $S'$ の $i$ 文字目を中心とする回文の半径が $r$ として、 $i+r = |S'|$ なら、 $i$ 文字目を中心とした回文は接尾辞である。
最も早く出現するそのような $i$ を見つければよい。

Python3

解法2

ローリングハッシュでもよい。

末尾 $k$ 文字を、→向きに読んだものと←向きに読んだもののローリングハッシュが、 $H_f,H_b$ としてそれぞれ求まっているとする。

ここから、末尾 $k+1$ 文字についてのものに更新したい。
基数を $B$ 、 $S$ の末尾から $k+1$ 文字目の値を $a$ として、

→向き： $H_f + a \times B^{k}$
←向き： $H_b \times B + a$

のように更新できる。最も大きい $k$ で $H_f=H_b$ となったものが、最長の回文接尾辞となる。

Python3

G - Not Only Tree Game

問題文

頂点に $1$ から $N$ の番号が、辺に $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺からなる単純無向グラフが与えられます。
- $i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。
- 最初、 $G$ は奇閉路を持ちません。
このグラフ $G$ を使って、青木君と高橋君がゲームをします。先手の青木君から順に交互に以下の操作を行います。
- $G$ に奇閉路ができないように、まだ辺が無い2頂点間を1つ選び辺を1本追加する。

操作を行えなくなった方が負けであり、負けでない方が勝ちです。
両者が最適に行動したとき、どちらが勝つか判定してください。

制約

$1 \leq N \leq 2\times 10^5$
$0 \leq M \leq 2\times 10^5$
$1 \leq U_i \lt V_i \leq N$
与えられるグラフは奇閉路を持たない
与えられるグラフは多重辺を持たない
入力は全て整数である

解法

理詰めは難しい。基本的な事項を整理した後は、実験した方が速い、かも。

基本的な事項

まず、最終的なグラフは完全二部グラフとなる。
完全二部グラフの辺の数は、2つのグループの頂点集合を $S,T$ として、 $|S| \times |T|$ である。

最終的なこの偶奇と、既にある辺の本数 $M$ をあわせ、あと奇数本追加できるなら先手必勝、偶数本なら後手必勝と決まる。

$N$ が奇数の時、 $|S| \times |T|$ は必ず偶数となるので、試合展開に関わらず先手必勝・後手必勝は決まっている。

$N$ が偶数の時、(偶,偶)に分けるか(奇,奇)に分けるかで最終的な辺の偶奇が変化するので、それを先手・後手それぞれが、狙った形に持っていけるか？が難しい部分となる。

実験

初期状態にある連結成分を、以下のように分類する。

ee: (偶,偶)の二部グラフとなっている連結成分の個数
eo: (偶,奇)の二部グラフとなっている連結成分の個数
si: 単独頂点の個数
oo: (奇,奇)の二部グラフとなっている連結成分の個数

また、“ed” を、「異なる連結成分を結ぶことなく追加できる辺の個数」とする。

辺の偶奇だけに着目した場合、 $(ee,eo,si,oo,ed)$ の5つのパラメータで状態は管理できる。

各プレイヤーは、13通りの選択肢がある。（細かな遷移は省略）

$ed$ を1減らす（ $ed \ge 1$ の場合に可能）
異なる連結成分を結ぶ（個数が足りる場合に可能。10通り）
- うち、「eoとeo」「eoとsi」に関してのみ、結び方により2通りの遷移先を選べる。

勝ちパターンを「その盤面から自分の手番で開始したら勝てる状態」、負けパターンを「どうやっても勝てない状態」とする。
遷移先の中に負けパターンがあれば、その盤面は勝ちパターン。無ければ負けパターン。
最終局面（＝負けパターン）である「 $ee+eo+si+oo=1,ed=0$ 」の状態に辿り着くまで、再帰的に求めていくことができる。

しかし、13通りも遷移があることからも明らかなように、再帰関数による解法をそのまま提出してもTLEとなる。
何らかの法則性を見いだし、計算量を減らさなければならない。

パラメータが多すぎて実験結果を見ても法則性がわかりづらいが、 ~~山勘も駆使して~~ 探っていくと、以下のようにしても答えが変わらないことが分かる。

ee は結果に影響しない
eo は「0, 1, 2, 3以上」の4通りの状態だけが重要
si は4で割った余りのみが重要
oo は偶奇のみが重要
ed は偶奇のみが重要

これでぐっと再帰回数を減らせるので、間に合うようになる。

Python3

        
          
          
              
              def naive(state, memo={}):
    if state in memo:
        return memo[state]
 
    ee, eo, si, oo, edge = state
    if sum((ee, eo, si, oo)) <= 1 and edge == 0:
        return 0
 
    if edge == 1:
        if naive((ee, eo, si, oo, 0)) == 0:
            memo[state] = 1
            return 1
 
    if ee >= 2:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
 
    if ee >= 1 and eo >= 1:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
 
    if ee >= 1 and si >= 1:
        if naive((ee - 1, eo + 1, si - 1, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
 
    if ee >= 1 and oo >= 1:
        if naive((ee - 1, eo, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
 
    if eo >= 2:
        if naive((ee + 1, eo - 2, si, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
        if naive((ee, eo - 2, si, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1
 
    if eo >= 1 and si >= 1:
        if naive((ee + 1, eo - 1, si - 1, oo, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
        if naive((ee, eo - 1, si - 1, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1
 
    if eo >= 1 and oo >= 1:
        if naive((ee, eo, si, oo - 1, edge)) == 0:
            memo[state] = 1
            return 1
 
    if si >= 2:
        if naive((ee, eo, si - 2, oo + 1, edge)) == 0:
            memo[state] = 1
            return 1
 
    if si >= 1 and oo >= 1:
        if naive((ee, eo + 1, si - 1, oo - 1, edge)) == 0:
            memo[state] = 1
            return 1
 
    if oo >= 2:
        if naive((ee + 2, eo, si, oo - 2, edge ^ 1)) == 0:
            memo[state] = 1
            return 1
 
    memo[state] = 0
    return 0
 
 
def solve(n, m, edges):
    # N 奇数の場合、二部グラフの頂点数は(偶,奇)となり、最終的な辺の数は必ず偶数 → 初期にある辺が奇数本なら先手勝ち
    if n % 2 == 1:
        return int(m % 2 == 1)
 
    links = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)
    ee = 0
    eo = 0
    si = 0
    oo = 0
    groups = [-1] * n
    for s in range(n):
        if groups[s] != -1:
            continue
        cur_groups = [1, 0]
        groups[s] = 0
        q = [s]
        while q:
            u = q.pop()
            gu = groups[u]
            for v in links[u]:
                if groups[v] != -1:
                    assert groups[v] == gu ^ 1
                    continue
                groups[v] = gu ^ 1
                q.append(v)
                cur_groups[groups[v]] += 1
        if cur_groups[0] % 2 == cur_groups[1] % 2 == 0:
            ee += 1
        elif cur_groups[0] % 2 == cur_groups[1] % 2 == 1:
            oo += 1
        elif sum(cur_groups) == 1:
            si += 1
        else:
            eo += 1
 
    edge = (oo % 2) ^ (m % 2)
 
    return naive((ee % 1, min(eo, 3), si % 4, oo % 2, edge))
 
 
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
if ans:
    print('Aoki')
else:
    print('Takahashi')

            

        
      