結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー lam6er
提出日時 2025-03-26 16:00:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,164 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 69,376 KB
最終ジャッジ日時 2025-03-26 16:01:37
合計ジャッジ時間 7,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())

# DPテーブルの初期化
max_n = n
INF = float('inf')
dp = [INF] * (max_n + 1)
dp[0] = 0
prev = [0] * (max_n + 1)  # 各iに対して、どのjを選んだかを記録

for i in range(1, max_n + 1):
    j = 1
    while j * j <= i:
        if dp[i - j*j] + j < dp[i]:
            dp[i] = dp[i - j*j] + j
            prev[i] = j
        j += 1

# 復元
current = n
parts = []
while current > 0:
    j = prev[current]
    parts.append(j)
    current -= j * j

parts.sort()  # 昇順にソート

# バイナリの構築
binary = []
current_char = '0'
for part in parts:
    s = []
    # 現在のcurrent_charから始まる長さpartの01列を生成
    for i in range(part):
        s.append(current_char)
        current_char = '1' if current_char == '0' else '0'
    binary.append(''.join(s))
    # 最後の文字を次の部分の先頭文字に合わせる
    # partが偶数なら最後の文字は元のcurrent_charと逆
    # partが奇数なら最後の文字は元のcurrent_charと同じ
    # ループ内でcurrent_charは切り替わっているので、最後の文字はs[-1]
    current_char = s[-1]

print(''.join(binary))
0