【今日の精進】ARC127C - Binary Strings

毎日格上の問題を倒すやつの84日目です。

問題リンク

atcoder.jp

問題概要

を二進数で書いたものを辞書順に並べたとき、 番目に来るものを答えてね。

解法

上から決めていくと、空文字列か0になるか1になるかを判断する必要がありますが、これは引き算さえできれば容易です。

しかし、多倍長整数は普通に遅いので間に合いません。

ところで、 は二進法で与えられます。

これをうまく扱えば、必要な引き算は素早く行うことができます。

提出コード

from collections import deque
N=int(input())
X=deque(input())
if len(X)==1:
    print(1)
    exit()
cnt=0
while X[-1]=="0":
    X.pop()
    cnt+=1
X[-1]="0"
for i in range(cnt):
    X.append("1")
while len(X)<N:
    X.appendleft("0")
ans=["1"]
for i in range(N):
    if X[0]=="1":
        ans.append("1")
    else:
        cnt=0
        while len(X)>0 and X[-1]=="0":
            X.pop()
            cnt+=1
        if len(X)==0:
            break
        X[-1]="0"
        for i in range(cnt):
            X.append("1")
        ans.append("0")
    X.popleft()
print("".join(ans))

Submission #48462217 - AtCoder Regular Contest 127

感想

気づいた時感動した