ABC336をpyhtonで解く

　問題文はAtCoder Beginner Contest 336 - AtCoderを見て下さい。どうやらnoteでは簡単にコードを埋め込めるっぽいので、以後、これを使って書いていきます。前回ABC335の記事はまああれはあれとして取っておくことにします。
　Cまでは簡単だったけど、Dからガクンと難しかったですね。

A

　操作が単純なので+を使って足し算で文字列を作っちゃえばいいです。複雑な操作で文字列を作るときはjoin()を使いましょう。

N=int(input())
print("L"+"o"*N+"ng")

B

　Nを2で割る操作が何回出来るかを確かめればいいです。

N=int(input())
ans=0
while N:
    if N%2==0:
        ans+=1
        N//=2
    else:
        break
print(ans)

C

　大体はN番目の五進数が何かを求める問題。1番目が0なので、初期状態で-1します。N==1(-1した後ならN==0)のときに例外処理が必要です。使う数字は0,2,4,6,8なので、それに合わせます。

N=int(input())-1
if N==0:
    print(0)
    exit()
gosinn=[]
suuji=[0,2,4,6,8]
while N:
    gosinn.append(N%5)
    N//=5
while gosinn:
    at=gosinn.pop()
    print(suuji[at],end="")
print()

D

　難しかったです。AC出来たけどあんまり確信が持てなかった。i番目の場所から左に行くとどこまで行けるのかをh、右に行くとどこまで行けるのかをmとすると、h,mは以下のhidaritiisaとmigitiisaを用いることでO(1)で求められます。これを0<=i<Nまでやることで答えが出ます。

N=int(input())
A=list(map(int,input().split()))
hidari=[]
migi=[]
for i in range (N):
    hidari.append(A[i]-i-1)
    migi.append(A[i]-N+i)
hidaritiisa=list(hidari)
migitiisa=list(migi)
for i in range (N-1):
    hidaritiisa[i+1]=min(hidaritiisa[i],hidaritiisa[i+1])
    migitiisa[-2-i]=min(migitiisa[-1-i],migitiisa[-2-i])
ans=[]
for i in range (N):
    h=max(-hidaritiisa[i],0)
    m=min(N+migitiisa[i]-1,N-1)
    ans.append((m-h)//2+1)
print(max(ans))

E

　解けなかった。今日のセット異様にムズくなかったか？
　解説を見ると桁dpらしい。あーね。桁dp苦手なんですよね。桁和が1になるものから9*(Nの桁数)になるものまでを独立してみていくのがポイントですね。list in listを4重とかにすると重くなりそうなので3重で実装。ちなみに現時点でNと一致しているやつって1通りしかないんで、わざわざdp内に組み込む必要ないと思うんですが、解説が入れてたんで入れて実装しました。別枠で管理すれば2重listで実装できると思います。
　dpは現時点の桁和、現時点のketawaで割った余り、現時点でNより小さいか一致しているかを貯めています。現時点のketawaで割った余りをdpに入れている点が解説のやり方と異なりますが、こっちの方が直感的には分かりやすいと思います。

N=input()
keta=len(N)
lisN=[]
for i in N:
    lisN.append(int(i))
ans=0
for ketawa in range (1,9*keta+1):
    dp=[[[0]*(ketawa+1) for _ in range (ketawa)] for _ in range (2)]
    dp[1][0][0]=1
    juu=[0]*keta
    juu[-1]=1%ketawa
    for i in range (keta-1):
        juu[-2-i]=(juu[-1-i]*10)%ketawa
    for i in range (keta):
        ndp=[[[0]*(ketawa+1) for _ in range (ketawa)] for _ in range (2)]
        for j in range (10):
            for k in range (ketawa):
                for l in range (ketawa+1-j):
                    if j<lisN[i]:
                        ndp[0][(k+j*juu[i])%ketawa][l+j]+=dp[0][k][l]
                        ndp[0][(k+j*juu[i])%ketawa][l+j]+=dp[1][k][l]
                    elif j==lisN[i]:
                        ndp[0][(k+j*juu[i])%ketawa][l+j]+=dp[0][k][l]
                        ndp[1][(k+j*juu[i])%ketawa][l+j]+=dp[1][k][l]
                    else:
                        ndp[0][(k+j*juu[i])%ketawa][l+j]+=dp[0][k][l]
        dp=ndp
    ans+=dp[0][0][-1]
    ans+=dp[1][0][-1]
print(ans)

F

　問題文見てなかったけど、見てても解けなかっただろうな。解法は半分全列挙らしいが、列挙するのが面倒そう。

以下リンク
ABC335/ホーム/ABC337