AtCoder Beginner Contest 099

atcoder

はい。
https://atcoder.jp/contests/abc099

A - ABD

C++

#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

C++

#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色は全て試して計算して最小値を保存しておくと解になるはずです。多分。