Zenn
👻

AtCoder Beginner Contest ABC404 解法メモ

に公開
Nim
AtCoder
tech

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC404

ABC404A - Not Found

解法

a～zを順に試し、最初にSに入っていないものを出力して終了すればよい
Nimなら、
for i in 'a'..'z':
　if i notin S: echo i; quit()
と書ける
ACコード

ABC404B - Grid Rotation

解法

初めに回転してから、塗り替えてもよいので、
0..3回右回転してから、SとTの色の異なる箇所を数え上げ、最小値を答えればよい
回転は、
proc f(i,j,k:int):(int,int)=
　if k==0: return (i,j)
　f(N-1-j,i,k-1)
としておけば、k=0..3で
let (ni,nj)=f(i,j,k)
if S[ni][nj]!=T[i][j]: ai+=1
とすればよい
ACコード

ABC404C - Cycle Graph?

解法

サイクルグラフであることは、全ての頂点の次数がで2あって、連結であればよい（複数のサイクルを否定）
これは、Union-Findで、
u=initDSU(N)としておき、
u.merge(A,B)
d[A]+=1; d[B]+=1
としていけばよい
ACコード

メモ

想定誤解法ではないが、N==Mは不要
その上、わざわざ0からスタートしてBFSで本当に一周できるか、などと無駄なことをしてTLE＆WA

ABC404D - Goin' to the Zoo

解法

各動物園に行く回数が0、1、2回のどれかにしかならないのであれば、
最大10園ゆえ、3^{10}=59049にて、全探索が可能である
よって、N桁の3進数を表現できればよく、
for i in 0..<3^N:
　var
　　n=i
　　id=0.repeat(N)
　var j=0; while n>0: id[j]=n mod 3; n=n div 3; j+=1
とすればよい
初めに、「動物iは動物園Aijで見ることができる」と与えられるときに、その通りに格納せず、
「動物園Aijでは動物iを見ることができる」という形で入力をしておけば、
後は先程のN桁の3進数の通りに動物園に行き、結果的に全動物を2回以上見た場合の、入園料合計の最小値を更新していけばよい
ACコード

メモ

各動物園に行く回数（N桁の3進数）の部分は、深さNまですべて0..2に分岐するDFSで書いてもよい

ABC404E - Bowls and Beans

解法

豆を複数の茶碗にわけ入れることに意味はなく、後ろから0に向けて順にまとめていけばよい
今、一番右の茶碗から入れられる範囲の中に、次に豆の入った茶碗があれば、その茶碗にすべての豆を入れてしまえばよい（いずれにせよ、その2番目の茶碗を処理せねばならないため）
次に豆の入った茶碗がなければ、「その次の移動で一番左まで入れられる範囲を広げられる茶碗」に入れるのが最善である
各々を操作1回として足し上げたものが答え
実装としては、Aで豆の入っていた茶碗の位置だけをDequeで持っておき、
popLastした茶碗位置rから、左に進める範囲lの茶碗のうち、

  • l以上のpeekLastの茶碗があったら、そこを次のrとして豆を入れる
  • そうでなく、l\leqq 0であれば、r=0（ゴール）
  • それでもなければ、その次に進める範囲が最も左となる茶碗の位置をrにしていけばよい

ACコード

メモ

後ろから、一箇所に、は直感的にわかったが、パスをとりながらBFSといった、グラフでのアプローチに固執してしまった
次の茶碗を探す前に、0に到達したかを確認したため、移動残しを発生させてしまった

反復学習にはmochiがおすすめ
全問入ったdeckはこちら

Discussion