結果

問題 No.3299 K-th MMA String
コンテスト
ユーザー wasd314
提出日時 2025-10-05 15:27:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,141 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 128,008 KB
最終ジャッジ日時 2025-10-05 15:27:58
合計ジャッジ時間 3,597 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, k = map(lambda s_: int(s_), input().split())

dp = [[[0] * 4 for _ in range(2)] for _ in range(n + 1)]
dp[2][0] = [1] * 4
for i in range(2, n):
    dpi = dp[i]
    ndpi = dp[i + 1]
    for e in range(2):
        for h in range(4):
            for t in range(2):
                h3 = (t * 4) | h
                nh = h3 >> 1
                ne = e | (h3 == 6)
                ndpi[ne][nh] += dpi[e][h]
    dp[i + 1] = [[min(e, 2**20) for e in vs] for vs in ndpi]

s = []
for i in range(4):
    if dp[n][1][i] < k:
        k -= dp[n][1][i]
        continue
    # k <= dp[n][i]
    s.append(i >> 1)
    s.append(i & 1)

done = False
for l in range(1, n - 1)[::-1]:
    if done:
        c0 = 2 ** min(l - 1, 20)
        if k <= c0:
            s.append(0)
        else:
            k -= c0
            s.append(1)
        continue
    # try 0
    may = s[-2] == s[-1] == 1
    if may:
        c0 = 2 ** min(l - 1, 20)
    else:
        c0 = dp[l + 1][1][s[-1] * 2 + 0]
    if k <= c0:
        if may:
            done = True
        s.append(0)
    else:
        k -= c0
        s.append(1)

ans = "".join("AM"[si] for si in s)
print(ans)
0