📌

AtCoder Beginner Contest ABC427 解法メモ

2025/10/12に公開

Nim

AtCoder

tech

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

ABC427

ABC427A - ABC -> AC

解法

l=S.len div 2とすれば、
S[0..<l]&S[^l..^1]を出力すればよい
ACコード

メモ

なぜかS[0..<l]&S[^(l+1)..^1]とし、サンプルすら通らないのに提出してしまいWA

ABC427B - Sum of Digits Sequence

解法

f(x:int):intは
for xi in $x: result+=($xi).parseInt
とすればよい
後は、問題文通り、
A[0]=1とした上で、
1..Nの $i$ に対して、
for j in 0..<i: A[i]+=f(A[j])
としていけばよい
ACコード

メモ

Aまで再帰で書き始め、計算量が膨れたので、さらにあわててメモ化までした
ACコード

ABC427C - Bipartize

解法

制約から、すべての2色の塗り替えパターンに対し、与えられた辺が同じ色を結んでいたら削除していき、その最小値を答えればよい、と考える
bit全探索が好適で、
0..<2^Nの $i$ に対して、
(i shr u and 1)==(i shr v and 1)
となる場合を数え上げていけばよい
ACコード

こうした組み合わせゲームは、後退解析が好適である
有向グラフ $g$ を構築した上で、
dp[何手目か][どの頂点か]=Aliceが必勝かどうかの真偽
とし、
0..<Nのiに対して、dp[2*K][i]=S[i]=='A'として、
i=2*K手後を初期値に、
0..<Nの $j$ にわたって、
$i$ が偶数、つまり、Aliceの手番では、
dp[i][j]=g[j].anyIt(dp[i+1][it])
$i$ が奇数、つまり、Bobの手番では、
dp[i][j]=not g[j].anyIt(not dp[i+1][it])
として、 $0$ 手目まで局面を戻せばよい
dp[0][0]がtrueならAliceが、faliseならBobが答えである
ACコード

メモ

組み合わせゲームなので後退解析、まではわかったが、制約もふまえ、頂点0から2*K手で到達する頂点を列挙せねばならないと思い込んで無駄な実装を試み、単に、全頂点で巻き戻せばいい、とは気付かなかった

ABC427E - Wind Cleaning

解法

この問題を、グリッド上のゴミの状態を頂点とした最短経路問題（BFS）として考える
ゴミの状態とは、
元の位置から $h$ 方向、 $w$ 方向にどれだけゴミ全体を動かしたかの $2$ 次元と、
一連の移動の結果、元のグリッド範囲0..H-1、0..W-1からどれだけの範囲のゴミが消滅して、どの矩形範囲のゴミが残っているかlh..rh、lw..rwの $4$ 次元で表される
すなわち、
(lh,rh,lw,rw,h,w)の初期値(0,H-1,0,W-1,0,0)から初めて、
高橋君がゴミに触れないようゴミ全体を移動させ、
残された矩形範囲内のゴミが $0$ になる最短操作数をBFSで求めることになる
lh..rh、lw..rwの範囲内のゴミの数をすぐに求めるために、 $2$ 次元の累積和をとっておくとよい
$4$ 方向移動 $dh$ 、 $dw$ に対し、nh=h+dh、nw=w+dwとすれば、
新たな矩形は、max(lh,-nh)..min(rh,H-1-nh)、max(lw,-nw)..min(rw,W-1-nw))であり、
高橋君の初めにいた位置を $th$ 、 $tw$ とすれば、そこに重なってくる座標はth-nh、tw-nwなので、
その矩形範囲にゴミがあるか、高橋君とゴミが重なるらないか確認しながら操作を続けていけばよく、操作の最小値が答えとなる
探索が尽きてもゴミが $0$ になる操作がみつからなければ $-1$ を出力すればよい
ACコード

メモ

状態を頂点とした最短経路問題という手法を知らない
移動方向に対する矩形の変化と高橋君のところにくる座標の符号に迷いがあった

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