AtCoder Beginner Contest 154
はい。
https://atcoder.jp/contests/abc154
oooox- 929(+30) D問題までスムーズに。E問題は適当に場合分けしようとして遊んでました。
A - Remaining Balls
PyPy3
s,t=map(str,input().split()) a,b=map(int,input().split()) u=input() print(a-(s==u),b-(t==u))
問題文を読んで内容を把握するのが面倒でした。内容を把握すればUと一致する方を1減らして出力。
B - I miss you...
PyPy3
s=input() print("x"*len(s))
Sの長さの分だけxを出力。
C - Distinct or Not
PyPy3
n=int(input()) a=[int(i) for i in input().split()] print("YES" if n==len(set(a)) else "NO")
set型で重複排除して最初の個数と比較。
D - Dice in Line
PyPy3
n,k=map(int,input().split()) p=[int(i) for i in input().split()] ans=chk=0 w=[0]*(n+1) for i in range(n): w[i+1]=w[i]+p[i] for i in range(k,n+1): chk=max(chk,w[i]-w[i-k]) print((chk+k)/2)
累積和で長さkで和が最大の箇所を調べる。最大の和にKを足して2で割ると解に。
E - Almost Everywhere Zero
解説をpdf読んでからなんとかACしたのと日を開けて書き直してACのパターンがあります。
(pdf読んでなんとかAC)PyPy3
n="0"+input() x=len(n) k=int(input()) l=[int(i) for i in n] ## dp1:top dp2:under dp1=[[0]*(k+2) for i in range(x)] dp2=[[0]*(k+2) for i in range(x)] dp1[0][0]=1 dp1[0][1]=0 dp2[0][0]=0 dp2[0][1]=0 cnt=0 for i in range(1,x): if l[i]>0: cnt+=1 if cnt<=k: dp1[i][cnt]=1 for i in range(1,x): for j in range(k+1): if j==0: dp2[i][0]=1 #出現回数0は先頭から 000...となっている場合のみで1つしかありません。 else: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+([dp1[i-1][j],0][l[i]==0]) print(dp1[-1][-2]+dp2[-1][-2])
桁DPさっぱり分かりませんけど解けたので追記。なるべく解説pdfに近い形でdp配列を2つ用意しました。
dp1[桁数][出現回数]はnより小さいことが確定していない場合用、dp2[桁数][出現回数]はnより小さいことが確定している用。
nは先頭に0を1つ付けて文字列扱いで考えます。それと各桁をintにキャストした配列lを用意しています(使用する時にキャストしてもいい気がします)。
先にdp1を計算します。
#dp1の計算が終わった時の中身 #サンプル1 n=100 ということで"0100"の場合 [[1, 0, 0], # 0桁目は0でない数の出現回数は0なので [0, 1, 0], # 1桁目は1で出現回数は1 [0, 1, 0], # 2桁目は0で出現回数は1 [0, 1, 0]] # 同上 #サンプル2 n=25 [[1, 0, 0, 0], #0なので [0, 1, 0, 0], #出現回数は1 [0, 0, 1, 0]] #出現回数は2 #サンプル3 n=314159 [[1, 0, 0, 0] #0なので [0, 1, 0, 0], #出現回数1 [0, 0, 1, 0], #出現回数は2 [0, 0, 0, 0], #これ以降の桁でnより小さいことが確定せずに、0でない数が出現回数2回以下の数は存在しません [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
dp1の配列はある桁以降で存在しなくなる場合があるので気をつけました。
dp2の配列はdp1を一部使いながら計算します。
(dp2[i-1][j-1]*9) nより小さいことが確定しているものから出現回数増やすので ×9パターン。
(dp2[i-1][j]) nより小さいことが確定している物から出現回数増やさないので0のみ使える ×1パターン。
(dp1[i-1][j-1]*max(0,l[i]-1)) 確定していないところから取ってくるのでl[i]-1回、または0回。
([dp1[i-1][j],0][l[i]==0]) 確定していないところからとってくるのでl[i]==0だとdp2には使えないので0パターン、または×1パターン。
でn桁目の出現回数k回の和が解になるはずです。多分。
(後日改めてAC)PyPy3
n=int(input()) k=int(input()) l=[int(i) for i in "0"+str(n)] # [0]=n [1]<n dp=[[[0]*5,[0]*5] for i in "ww"] dp[0][0][0]=1 for i,j in enumerate(str(n),start=1): for p in range(k+1): if dp[i%2-1][0][p]: dp[i%2][0][p+[0,1][l[i]>0]]=1 for q in range(l[i]): dp[i%2][1][p+[0,1][q>0]]+=1 if dp[i%2-1][1][p]: dp[i%2][1][p]+=dp[i%2-1][1][p] dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9 for p in range(10): dp[i%2-1][p//5][p%5]=0 print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])
こちらの方が桁DPっぽい雰囲気がある気がします。
メモリ使用量少なくなるかな？と思ってDP用のリストを小さくしたのに提出結果画面で見えるメモリ使用量は特に変化無しでした。そして古い方の情報を0埋めで初期値を設定し直す必要があるのでこの方法はあまりメリットがないような気がしました。
それと桁DPとは別件で enumerate(x,start=1) とかで1始まりを指定出来ることを新たに学びました。
C++14
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define per(i,n) for(int i=n-1;i>=0;--i) #define sc1(a) scanf("%d",&a) #define sc2(a,b) scanf("%d %d",&a,&b) #define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c) #define sl1(a) scanf("%lld",&a) #define sl2(a,b) scanf("%lld %lld",&a,&b) #define sl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define PI 3.1415926535897932 long long dp[105][2][5]; int main(){ int k,x; char n[105]; scanf("%s",n); sc1(k); dp[0][0][0]=1; x=strlen(n); for (int i=1;i<=x;i++) { for (int j=0;j<4;j++) { if (dp[i-1][0][j]>0) { if (n[i-1]-'0'>0) dp[i][0][j+1]=1; else dp[i][0][j]=1; for (int m=0;m<n[i-1]-'0';m++) { if (m==0) dp[i][1][j]+=1; else dp[i][1][j+1]+=1; } } if (dp[i-1][1][j]>0) { dp[i][1][j+1]+=dp[i-1][1][j]*9; dp[i][1][j] +=dp[i-1][1][j]; } } } printf("%lld\n",dp[x][0][k]+dp[x][1][k]); return 0; }
一応C++でも書き直し。書き慣れていないので無駄に手間取りました。
