Atcoderの競技プログラミングの鉄則問題A04でのBinary Representation 1の実装方法が分からない

Question

実現したいこと

整数を入力した値に対して二進数に変換をしたい。また桁数10になのであまった位には0を追加する

前提

問題文
整数 N が 10 進法表記で与えられます。N を 2 進法に変換した値を出力するプログラムを作成してください。

制約
N は 1 以上 1000 以下の整数

■■な機能を実装中に以下のエラーメッセージが発生しました。

該当のソースコード

N = int(input())
count = 10
ans = []
while N != 0:
    ad =  N%2
    N = N//2
    ans.insert(0,ad)  
    count -=1
    print(ans)

for i in range(count):
    ans.insert(0,0)
print(ans)
num = ''.join(map(str, ans))
print(num) 

補足情報（FW/ツールのバージョンなど）

OS 名 Microsoft Windows 11 Home

Comments

[hiroki-o]

仕様通り動いているようですが、競技プログラミングとしての改善点を教えてほしいという質問ですか？

[TMYchan]

返信が遅くなり申し訳ございません。おっしゃる通りです。

Answer 1

整数を入力した値に対して二進数に変換をしたい。
また桁数10なのであまった位には0を追加する

桁数が固定（10桁）なら，for ループを使った方がわかり易いかもしれません。
記述例を下記に示します。

（追記）

AtCoder への 提出結果 も参照ください。

N = 1000
digit = 10

n, lst = N, []
for i in range(digit):
    lst.append(n % 2)
    n //= 2

bin_str = ''.join(str(i) for i in reversed(lst))
print(bin_str)
# 1111101000

Comments

[TMYchan]

上記の点で一部N=int(input())をして提出したのですが、Atcoderの結果はREになってしましいました。理由はなぜでしょうか？

[little_street]

参考になると良いのですが，「N = int(input())」に変更して「提出」した結果は下記でした。
-----
コード長: 176 Byte
結果: AC
実行時間: 11 ms
メモリ: 8744 KiB
-----

[YellowGreen]

> 理由はなぜでしょうか？

N = int(input())
の次の行に
digit = 10
の行がないからではないでしょうか

Answer 2

9行目、13行目に、デバッグ出力用のprint(ans)が残っているのが原因ではないでしょうか。これらを削除してみてください。

Comments

[TMYchan]

すみません。こちらのデッバクを変更しても結果はREのままでした。解決策は他にもありますでしょうか？

[actorbug]

REになると言っているのは、こちらの提出結果のことでしょうか。あなたの提出結果で、A04に対しREとなっているのは、こちらしかありませんでした(2025/9/13現在)。
https://atcoder.jp/contests/tessoku-book/submissions/69234512
もしそうなら、元のコードから大幅に修正されており、私の回答を参考に書かれたものとは思えません。

[actorbug]

念のため、私の回答の手順で修正したコードを提出してみましたが、REが発生することはなく、正答となりました。
https://atcoder.jp/contests/tessoku-book/submissions/69250201

Answer 3

Pythonの場合、bin() と int.bit_length() が用意されていますので、それらを利用すると以下の様に書くことができます。

N = int(input())
count = 10
bin_str = '0'*(count - N.bit_length()) + bin(N)[2:]
print(bin_str)

もしくは f-strings を利用します。参考にしてみてください。

N = int(input())
print(f'{N:010b}')

Comments

[hiroki-o]

確かに、f文字列を使用すると2行で終わってしまいますね。
2022年より前からf文字列は使えたような気がするし、出題の意図が謎です。
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_d

[TMYchan]

すみません。今回の問題はなぜ文字列が利用できたのでしょうか？問題のどこかに記載していましたでしょうか？

後メンション機能はどうすればできますでしょうか？

[melian]

問題には記載されていませんが、おそらく出題側は Python に f-strings(フォーマット済み文字列リテラル)があるのを知らないか、もしくは2進数表記用の書式("b")があることを知らなかったのかもしれません。メンション機能に関しては、Teratail には明示的なものはないと思います。(質問者であるTMYchanさんのコメントが付いた旨の通知とメールが届いています)

[TMYchan]

返信遅くなり申し訳ありません。
なるほど f-stringsが二進数に変更することが入っていなかったためコンパイル提出した際にWAの結果になったのですね。理解しました。そうなると私の中に含まれているjoin関数は利用ができないかったということでしょうか？

[melian]

str.join関数はPythonにデフォルトで用意されている関数ですので、利用できないということはないと思います。質問に記載されているコードがACにならないのは、既に他の回答で指摘されている通りにデバッグ用のprint(ans)が入っているためでしょう。

[TMYchan]

print(ans)こちらを外してみたのですが、ＡＣになりませんでした。

[melian]

print(ans) を外したコードを提出してみたところ、AC になりました。以下のコードをコピペして、もう一度試してみてください。
https://www.mycompiler.io/view/GEQ7IyoOhuZ

Answer 4

競技プログラミングをさておいて、一般の問題として考えると、「10進数表記⇒整数値」「整数値⇒2進数表記」のどちらもmelianさんの回答の通り組み込み機能でできるので（他の言語でも組み込みの機能でできる場合が多いと思います）、出題意図は何かと考えると、
ケース１：進数変換の算数的なやり方を理解していてそれをコード化できるかどうかを問う問題
「整数値⇒2進数表記」はロジックで書いているが、「10進数表記⇒整数値」を組み込み機能に任せている質問のコードでは出題意図を満たさない。
ケース２：進数変換のPythonの組み込み機能を知っていてそれを使いこなせるかを問う問題
「整数値⇒2進数表記」を組み込み機能を使ってないので出題意図を満たさない。

普通の問題だと数値入力での文字列から数値への変換は組み込み関数一発でいいと思いますが、今回は進数変換自体が問題のテーマなので問題文でその可否に触れるべきでしょうね。あるいは、触れられてないのであればケース2で確定なのか？

お書きのコードは、前提が『非負の入力で「10進数表記⇒整数値」は組み込み関数int()一発でいいが「整数値⇒2進数表記」は算数的な方法で行え』であればそれでいいと思いますが、私ならansは文字列にします。

count = 10
ans = ""
while N != 0:
	ans = str(N%2)+ans
	N = N//2
	count -=1
ans = "0"*count+ans

Answer 5

この問題に特化した解はMelian氏が提示した解以上のモノは得られないと思う。

値を出力するプログラム

と言われてる以上、Pythonのファンシーな機能を使って、文字列を生成する以上に上手いテはない。
非常に直接的な解だと思う。

そこでここでは、もうちょっと一般化したユーティリティ作成を紹介しようと思う。

#!/usr/bin/env python3

class unfoldr(object):
    def __init__(self, f, seed):
        self.f = f
        self.seed = seed
    def __iter__(self):
        return self
    def __next__(self):
        match self.f(self.seed):
            case a, b:
                self.seed = b
                return a
            case None:
                raise StopIteration

if __name__ == '__main__':
    ans = ''.join(reversed(list(unfoldr(lambda N: None if N == 0 \
                                        else (str(N % 2), N // 2), int(input())))))
    print('0' * (10 - len(ans)) + ans)

ここで作成したイテレータunfoldrは、Python組み込みのイテレータrangeの亜種だ。
と言うより、rangeの上位互換だ。

>>> [i for i in range(3)]
[0, 1, 2]
>>> [i for i in unfoldr(lambda x: None if x == 3 else (x, x + 1), 0)]
[0, 1, 2]

従って、単純には、rangeはunfoldrを利用すると次のように書ける。

def range(*args):
    match args:
        case stop,:
            return unfoldr(lambda x: None if x >= stop else (x, x + 1), 0)
        case start, stop:
            return unfoldr(lambda x: None if x >= stop else (x, x + 1), start)
        case start, stop, step:
            return unfoldr(lambda x: None if x >= stop else (x, x + step), start)

unfoldrはrangeの上位互換な故、unfoldrの機能を制限する事でrangeが書けるわけだ。

unfoldrはHaskellと言うプログラミング言語のunfoldrをPython向けに移植したモノだ。
unfoldrは引数を2つ取り、第一引数は関数、第二引数に「シード」と呼ばれる単一の値(データ)を取る。
ここで第一引数で取る関数のカタチが特徴的だ。ここではラムダ式を使うが、作成すべき関数は次のルールに従う。

lambda x: None if 終了条件 else (取り出す値, 次のシード)

何らかの終了条件を満たせばNoneを返すようにすること。そうじゃなければタプルを返すように書く。
そのタプルは2要素のタプルで、第一要素は生成するリストの要素、第二要素は「シードをどう加工してゆくか」の情報になっている。
結果、unfoldrは初期値として与えられたシードから粛々とリストの要素を生成していって、最終的にリスト(このコードだと正確にはリストを生成するイテラブル)を返すわけだ。

##   2 乗のリスト 1^2 ... 10^2
>>> list(unfoldr(lambda x: None if x > 10 else (x * x, x + 1), 1))
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

見方によっては、unfoldrはリスト内包表記/mapとrangeの合わせ技を一つでやり抜く為のイテレータに見えるだろう。

>>> [i ** 2 for i in range(1, 11)]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> list(map(lambda x: x ** 2, range(1, 11)))
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

いずれにせよ、unfoldrはかなり便利な汎用的なユーティリティとなる。
例えば題意に沿うと、基本的には次のように一行で書いて結果のリストを得る。

>>> list(unfoldr(lambda x: None if x == 0 else (x % 2, x // 2), 13))
[1, 0, 1, 1]
>>> list(unfoldr(lambda x: None if x == 0 else (x % 2, x // 2), 37))
[1, 0, 1, 0, 0, 1]
>>> list(unfoldr(lambda x: None if x == 0 else (x % 2, x // 2), 1000))
[0, 0, 0, 1, 0, 1, 1, 1, 1, 1]

これらは「逆順のリストになる」んで、ちょっとしたデータ変換で文字列を得ることが出来るだろう。

>>> ''.join(reversed(list(unfoldr(lambda x: None if x == 0 else (str(x % 2), x // 2), 13))))
'1101'
>>> ''.join(reversed(list(unfoldr(lambda x: None if x == 0 else (str(x % 2), x // 2), 37))))
'100101'
>>> ''.join(reversed(list(unfoldr(lambda x: None if x == 0 else (str(x % 2), x // 2), 1000))))
'1111101000'

このunfoldrの実装はrangeと同様のイテレータだが、rangeと違って直接reversed出来ない。
結果、list化した上でreversedして更に・・・とひと手間かかる。
人によっては「そもそもunfoldrイテレータに__reversed__特殊メソッドを組み込むべきじゃない?」って言うだろう。
ただし、unfoldrは第一引数に与える関数が終了条件を持たない場合、無限長リスト(要はこれもイテラブル)を返すようになっている。無限長リストが返る可能性があるなら、直接reversedが出来るのは危険だ。
よって、手間でも、キチンと有限長になる事を確認してからlist化してreversedした方が安全だろう。

#!/usr/bin/env python3

import sys
from itertools import islice

class unfoldr(object):
    def __init__(self, f, seed):
        self.f = f
        self.seed = seed
    def __iter__(self):
        return self
    def __next__(self):
        match self.f(self.seed):
            case a, b:
                self.seed = b
                return a
            case None:
                raise StopIteration

# わざと終了条件を与えず、無限長の素数列を得る例
def primes():
    yield 2
    for p in unfoldr(isPrime, 3):
        yield p

def isPrime(n):
    while True:
        for p in primes():
            if p ** 2 > n:
                return n, n + 2
            elif n % p == 0:
                n += 2
                break
    

if __name__ == '__main__':
    print(list(islice(primes(), int(sys.argv[1]))))

いずれにせよ、Pythonにunfoldrと言うユーティリティを備えとけば色々と便利だし、ある種、汎用アルゴリズムらしい抽象的アルゴリズムだ。

そんなカンジかな。
以上。