ABC099(バーチャル):水色競プロerの復習

昨日のABC100バーチャルコンテストは、緊張感が出てとても良い精進になったので、今日もABC099で復習しました。

コンテストの時期的に、これもリアルタイムで参加したはずです。

〇コンテスト名：ABC099

〇配点：不明

〇制限時間100分(A～Dまでの4問の時代のコンテスト)

〇今回の方針

　本番のコンテストのつもりで解く

　緊張感を大切に

コンテスト開始！
A - ABD

与えられたNが999以下ならABCと、1000以上ならABDと出力。
ただそれだけの問題なのに、勝手にNが90ならABC090と、数字部分はゼロ埋めしようとしました。
地味に1分弱のロス。これを本番でやると、時間のロスは大したことなくても焦りますね・・
問題文とテストケースの解答は良く見ましょう。
それさえできれば難しくない問題

N=int(input())
if N<=999:
    print("ABC")
else:
    print("ABD")

1:49 AC

B - Stone Monument
地味にこれB問題としては難しくないですか？
問題文の式を見れば、bが西から何番目かはb-aで求まることがわかります。
bが西から何番目かがわかれば、bの高さ(雪に埋もれてない場合)は1+2+・・+(b-a)で求まります。
bの高さ(雪に埋もれてない場合)-b(雪の上に出ている高さ)を出力すれば良いですね。

a,b=map(int,input().split())
N=b-a
H=0
for i in range(N+1):
    H+=i
print(H-b)

4:17 AC

C - Strange Bank
はいこの良問見て思い出しました。
この回のコンテストには参加してます。
コンテスト当時はこれができず、1時間以上固まってました。
今ならどうするか。
まず、1回の引き出しでおろせる額のリストを作ります。
6**1,6**2・・10**5を超えない範囲で加えていく。
同様に9**1,9**2・・10**5を超えない範囲で加えていく。
次に、DP用リストを用意し、dp=[i for i in range(N+1)]
これは全てを1円玉で払った枚数。
これに対し、上で作ったリストを使い
dp[i]=min(dp[i],dp[i-1回で引きおろせる額]+1)として更新
文章ではわかりにくいのでコードをどうぞ

Coin=[]
for i in range(1,100):
    if 6**i<=10**5:
        Coin.append(6**i)
for i in range(1,100):
    if 9**i<=10**5:
        Coin.append(9**i)
        
N=int(input())
dp=[i for i in range(N+1)]
for c in Coin:
    for i in range(N+1):
        if i-c>=0:
            dp[i]=min(dp[i],dp[i-c]+1)
print(dp[N])

9:15 AC

D - Good Grid
全探索
まずは、色は30色までしかない。そして、3で割ったあまりは0,1,2の3通りしかない。
そこで、あまり0～2の3種に対し、長さ30のリストを作る。
各あまり毎に色Cがいくつあるかを集計しておく。
あまり0～2をどの色にするか全探索。
itertoolsをインポートして、itertools.permutationsを使うと楽に全部の色の組み合わせを作成できますね。
そして、あまり0～2をどの組み合わせにすれば違和感が少ないかを全探索
ところが、コードの最後でansを出力していますが、ここを誤ってcntとしていて、答えが合わずに困りました。
コンテスト本番でなくて良かった。

N,C=map(int,input().split())
D=[]
D.append([0 for i in range(C+1)])
for i in range(C):
    d=[0]+list(map(int,input().split()))
    D.append(d)

L=[]
for i in range(N):
    c=list(map(int,input().split()))
    L.append(c)

M0=[0 for i in range(C+1)]
M1=[0 for i in range(C+1)]
M2=[0 for i in range(C+1)]

for i in range(N):
    for j in range(N):
        if (i+j)%3==0:
            M0[L[i][j]]+=1
        elif (i+j)%3==1:
            M1[L[i][j]]+=1
        elif (i+j)%3==2:
            M2[L[i][j]]+=1

Col=[i for i in range(1,C+1)]

import itertools
Arr=list(itertools.permutations(Col,3))

ans=10**20
for i in range(len(Arr)):
    cnt=0
    for j in range(1,C+1):
        cnt+=M0[j]*D[j][Arr[i][0]]
        cnt+=M1[j]*D[j][Arr[i][1]]
        cnt+=M2[j]*D[j][Arr[i][2]]
    if ans>cnt:
        ans=cnt
    
print(ans)

34:03 AC

結局34:03ノーペナで全完！
コンテスト当時は2完だったので、成長しているようです。