結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー qwewe
提出日時 2025-04-24 12:28:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,230 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 83,172 KB
最終ジャッジ日時 2025-04-24 12:30:08
合計ジャッジ時間 7,576 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    N = int(input())
    if N == 0:
        print("")
        return

    # Initialize DP and previous arrays
    INF = float('inf')
    dp = [INF] * (N + 1)
    dp[0] = 0
    prev = [0] * (N + 1)

    for i in range(1, N + 1):
        max_j = int(math.isqrt(i))
        # Check j in descending order to prioritize larger j first
        for j in range(max_j, 0, -1):
            j_sq = j * j
            if i >= j_sq and dp[i - j_sq] + j < dp[i]:
                dp[i] = dp[i - j_sq] + j
                prev[i] = j

    # Reconstruct the partition list
    partition = []
    current = N
    while current > 0:
        j = prev[current]
        partition.append(j)
        current -= j * j

    # Reverse the partition to prioritize smaller segments first for lex order
    partition = partition[::-1]

    # Build the binary string
    current_char = '0'
    result = []
    for length in partition:
        segment = []
        char = current_char
        for _ in range(length):
            segment.append(char)
            char = '1' if char == '0' else '0'
        result.append(''.join(segment))
        current_char = segment[-1]

    print(''.join(result))

if __name__ == "__main__":
    main()
0