結果

問題 No.3299 K-th MMA String
ユーザー hotate29
提出日時 2025-10-05 15:09:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 162 ms / 2,000 ms
コード長 1,434 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 76,628 KB
最終ジャッジ日時 2025-10-05 15:10:34
合計ジャッジ時間 3,507 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, k = map(int, input().split())

# 長さNで一番小さいMMA文字列は？
# A...AMMA
# 素直な辞書順では、この次はA...AMMMだけど、これはMMA文字列ではない
# - AAAMMA
# - AAAMMM
# - AAMAAA
# - AAMAAM
# - AAMAMA
# - AAMAMM
# - AAMMAA !!! ←MMA文字列 MMAが上の"桁"に移動した
# - AAMMAM !!!
# - AAMMMA !!! MMAAの、AA部分が全てMになるまでMMA文字列
# - AAMMMM
# - AMAAAA
# - AMAAAM
# - AMAAMA
# - AMAAMM
# - AMAMAA
# - AMAMAM
# - AMAMMA !!! Mが繰り上がって、また下の桁にMMAが出現した

# A...AMMAから開始
# MMA~を適当に動かす
# 問題は生成がめんどくさいということで...

# MMAが連続する区間は
# - 2^1 - 1
# - 2^2 - 1
#
# - 2^1 - 1
# - 2^3 - 1
#
# - 2^1 - 1
# - 2^2 - 1
# - 2^4 - 1
#
# -

# 一番左のMMAを決め打ちして、周りをガチャガチャ？
# AAAAMMA
# AAAMMAA
# AAMAMMA
# AAMMAAA

# そうでもないな MMA文字列はかなり多い
# 列挙する範囲は狭くてよさそう

cnt = 0

bits = min(n, 17)
for i in range(1 << bits):
    s = "".join("AM"[(i >> j) & 1] for j in range(bits))[::-1]
    if "MMA" in s:
        cnt += 1

    if cnt == k:
        if bits < n:
            print("A" * (n - bits) + s)
        else:
            print(s)
        break
    # print(s, "!!!" if "MMA" in s else "", cnt)
    # print("!!!" if "MMA" in s else "", cnt)
    # if cnt >= 10**5:
    # print(s)
    # break
0