💭
AtCoder Beginner Contest ABC391 解法メモ
文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです
ABC391
ABC391A - Lucky Direction
解法
d=["N","NE","E","SE","S","SW","W","NW"]とおけば、
d[(d.find(D)+4) mod 8]が答え
メモ
Copilotに手伝ってもらわないと、誤記が怖い
ABC391B - Seek Grid
解法
a、bを0..N-Mで全探索すればよく、縦横0..<Mで合致するか総当たりすればよい
メモ
特になし
ABC391C - Pigeonhole Query
解法
- 鳩
i p - どの巣に何羽いるか持つ配列
n - 2羽以上いる巣の個数を保持する変数（答え）
a
を用意してシミュレート
Nimならp=(0..<N).toSeq
n[i]が
メモ
無駄に怖がって何をどう持つかで混乱し、大いに時間ロス
ABC391D - Gravity
解法
時刻ごとの動きはどうでもよく、全部落ちたときに一行揃うかどうかが問題
一行揃うなら一番遅い（もともと一番上にいた）ブロックが一番下に落ちたタイミングで消える
- 各列毎の配列x[xi]に(yi,i)の形でブロックを読み込み
- 各ブロックが下から何層目にいるかを保持する配列a
- その層の最高位置を保持するためのy
- その層の個数を保持するc
を用意し、
xをソートしてから、順に
- a[i]に下から何層目かを保存
- その層の最高位置を更新 y[a[i]].max=yi
- その層の個数をインクリメント c[a[i]]+=1
ここまで用意して、クエリ毎に、T<=y[a[A]]か、c[a[A]]<WならYes
メモ
ブロックの挙動の本質から、何をどう持つかが出ない
ABC391E - Hierarchical Majority Vote
解法
操作後の1文字には、もとの3個の要素セットしか影響を及ぼさないので、
初めの文字列Aを(
普通にN回操作をすればよい
各操作は、
- 多数決の結果がtupleの前
- 000か111ならコストの低い方から2つの合計、0か1が2つならどちらかコストの低い方1つがtupleの後
最後のtupleの後が答え
メモ
独立していることに気づかない
1文字ずつコストを管理すればよいことに気づかない
Discussion