結果

問題 No.3623 2-Letter Shiritori 2
コンテスト
ユーザー 👑 loop0919
提出日時 2026-08-11 00:17:50
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 61 ms / 2,000 ms
+ 322µs
コード長 1,265 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 813 ms
コンパイル使用メモリ 95,472 KB
実行使用メモリ 82,704 KB
最終ジャッジ日時 2026-08-14 20:52:47
合計ジャッジ時間 1,237 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def hierholzer(N, M, E):
    G = [[] for i in range(N)]
    deg = [0] * N
    rdeg = [0] * N
    for a, b in E:
        deg[a] += 1
        rdeg[b] += 1
        G[a].append(b)

    # find starting and ending vertices
    s = t = u = -1
    for i in range(N):
        if deg[i] == rdeg[i] == 0:
            continue
        df = deg[i] - rdeg[i]
        if not -1 <= df <= 1:
            return None
        if df == 1:
            if s != -1:
                return None
            s = i
        elif df == -1:
            if t != -1:
                return None
            t = i
        else:
            u = i
    v0 = s if s != -1 else u

    # find an Eulerian path (or circuit)
    res = []
    it = [0] * N
    st = [v0]
    (*it,) = map(iter, G)
    while st:
        v = st[-1]
        w = next(it[v], -1)
        if w == -1:
            res.append(v)
            st.pop()
            continue
        st.append(w)
    res.reverse()
    if len(res) != M + 1:
        return None
    return res


sigma = 26
cand = []
for i in range(sigma):
    for j in range(sigma):
        cand.append((i, j))

res = hierholzer(sigma, sigma**2, cand)

for i in range(sigma**2):
    x, y = res[i], res[(i + 1) % sigma**2]
    print(chr(x + ord("A")) + chr(y + ord("A")))
0