AtCoder Beginner Contest 099
はい。
https://atcoder.jp/contests/abc099
A - ABD
#include<bits/stdc++.h> using namespace std; #define PI 3.1415926535897932 int main(){ int mod=1000000007; int n,m; scanf("%d",&n); printf("%s\n",n>999?"ABD":"ABC"); return 0; }
999,1000を境にして出力。
B - Stone Monument
#include<bits/stdc++.h> using namespace std; #define PI 3.1415926535897932 int main(){ int mod=1000000007; int a,b,chk; scanf("%d %d",&a,&b); chk=b-a-1; chk=(chk+1)*(chk/2)+(chk%2? chk/2+1:0); printf("%d\n",chk-a); return 0; }
b-aの差が総和のa(1+2+...n)、b(1+2+...n+(n+1))とかのnが特定できる。そこから塔の高さがわかるので見えてる高さとの差が積雪量になる、と思います。
C - Strange Bank
C++14
#include<bits/stdc++.h> using namespace std; int main(){ int n,tmp; scanf("%d",&n); int d[100001]; bool x[100001]; for (int i=0;i<100001;i++) x[i]=0; d[0]=1; int t[12]={1,6,9,36,81,216,729,1296,6561,7776,46656,59049}; for (int i=1;i<100001;i++) { for (int j=0;j<12;j++) { tmp=i+t[j]-1; if (tmp>100000) break; if (x[tmp]==0) { d[tmp]=d[i-1]+1; x[tmp]=1; } else { d[tmp]=min(d[tmp],d[i-1]+1); } } } printf("%d\n",d[n]-1); return 0; }
配列で回数管理して6xや9yの数は回数+1したりmin取ったりしながら更新して全部調べたあとで入力に応じて解を出力した。けどこれだと解説と違います。。まぁ気にしないことにしましょう。
D - Good Grid
PyPy3
def sol(): n,c=map(int,input().split()) d=[[int(i) for i in input().split()] for i in range(c)] t=[[int(i) for i in input().split()] for i in range(n)] x0,x1,x2={},{},{} for p in range(n**2): h,w=p//n,p%n x=(h+w)%3 o=t[h][w]-1 if x==0: if o in x0: x0[o]+=1 else: x0[o]=1 if x==1: if o in x1: x1[o]+=1 else: x1[o]=1 if x==2: if o in x2: x2[o]+=1 else: x2[o]=1 ans=-1 for a in range(c**2): for k in range(c): i,j=a//c,a%c q=[i,j,k] if len(set(q))<3: continue chk=0 for p in x0: chk+=d[p][q[0]]*x0[p] for p in x1: chk+=d[p][q[1]]*x1[p] for p in x2: chk+=d[p][q[2]]*x2[p] if ans==-1: ans=chk ans=min(ans,chk) print(ans) if __name__=="__main__": sol()
Cに何が何個あるか数えておく。最大でNが500なので500x500の数列を何度もループ回しているとTLEします。こういうのを数えておいたほうがいいか、影響しないかとかは問題文と制約をよく確認して考えましょう。今回は最大でも30種類の数が最大250,000マスに並んでいるのなら数えておいたほうが早いです。i+jの剰余が0,1,2のマスごとに数えておいて3色は全て試して計算して最小値を保存しておくと解になるはずです。多分。