🦁

AtCoder Beginer Contest 368~383 Dまでの要点・解答（Go）

2024/11/29に公開

AtCoder

tech

※ 個人的なメモ。コードは比較的読み易いと思います。
※ そのトピックにおいて典型的な問題の場合、問題タイトルの後ろにトピックを記載。

383

A - Humidifier 1

水量を減らす時にマイナスの数字にしない様に注意。

code

B - Humidifier 2 / 全探索

グリッドサイズが 10*10 と極小なので、全探索で解くべき。DFS や BFS より確実にシンプルになる。

ある配列からの二つの要素の組み合わせは、以下で列挙できる。

for i := 0; i < lne(sl); i++ {
  for j := i+1; j < lne(sl); j++ {
    fmt.Print(sl[i], sl[j])
  }
}

該当範囲を重複してカウントしないための工夫が必要。
- 全探索なら、セルがいずれかの加湿器からのマンハッタン距離以内かを同時に判定すればいい。
- DFS、BFS ならカウント済み範囲をグリッド状のデータで保持すればいい。

code

C - Humidifier 3 / 多始点 BFS or BFS + メモ化

max で、グリッドサイズ、始点ノードの数、移動距離が 1368*1368 なので、全探索は間に合わない。
始点ノードから一定距離の条件を満たすノードの探索なので、BFS か DFS。再帰よりキューの方が直感的に書けるので BFS が優勢か。
BFS または DFS だとしても、移動距離の長さ、始点ノードの多さからなんらかの工夫をしないと間に合わない。

多始点 BFS

複数の始点を持つ BFS においては、最初に全ての始点をキューに入れて探索をすれば、visited を共有することができ効率的な探索ができる。これを多始点 BFSという。（DFS ではこれはできない。）

BFS + メモ化（※ 多始点 BFS の方が簡単なのでそっちでいい）

ある始点ノードからの探索において別の始点ノードに到達した場合、そこから先は探索しなくていい。その始点からの BFS に内包されている範囲だから。
これを拡張すると、別の始点からの探索で訪問済みのノードにある始点からの探索で到達した時に、残り移動回数がより少ない状態で到達していた場合そこからはもう探索しなくて良い。このデータをメモ化すれば効率化可能。
- （メモは visited の役割も兼ねることが可能。visited を別のデータで保持してアクセスする実装だと TLE になった。）

code

D - 9 Divisors / 約数、巨大な数

解説
約数の個数の性質
- $p_1^{r_1}*p_2^{r_2}*...*p_k^{r_k}$ に因数分解される整数の約数の個数は、 $(r_1+1)(r_2+1)...(r_k+1)$ 個である。
素因数分解には素数が必要なので、あらかじめ任意の数以下の素数を列挙できるライブラリを用意しておく。
条件にあてはまる数の素因数分解に含まれる素数は、 $\sqrt{N}$ 以下である。（もっと小さいが。）
- 素数の列挙は計算コストが重いので、条件を狭めておく必要がある。
巨大な数の操作はint, int64だとオーバーフローする可能性があるので、math.Bigを使うか、ルートにして扱うことを考える。

code

382

愚直

code

愚直

code

C - Kaiten Sushi / 二分探索

$N*M$ が 20 万の 2 乗なので、計算の効率化が必要。寿司ごとに誰が食べるかは判定しなくてはならないので、M（寿司）ではなく N（人）のループを無くしたい。
ある数字以下の数字（美味しさ以下の美食度）を見つける必要があるので、二分探索が使えそう。
- 美食度の並びについて、単調減少を満たすようにできないか？
- k 番目の人の美食度が、それまでの人の美食度の中で minimum ではない場合、その人は何も食べられない。
- これを利用して美食度の並びに対し、それまでの minimum でない値は、minimum に書き換える操作を行い、二分探索が使えるようにする。

code

ちょっと違う変な周りくどいやり方をしていた。

D - Keep Distance / DFS（数列）

パターンの列挙
存在しうるパターンが木構造で表現できるので、パターンの列挙は DFS で可能
DFS の一段目はちょっと特殊なので、そこだけ再帰関数の外に出してもいい。
再帰関数 * Go のスライスだと予期せぬ影響が起きかねないので、スライスを引数に渡すときはmake()や copy()でコピーを作って渡した方が良い。

code

381

A - 11/22 String

愚直
問題文で、数式が連続する複数行に書かれているとき、一部が重なっていて読み間違えることがあるので注意！
条件が箇条書きで書かれている時、条件のチェックはその数だけ必要！

code

B - 1122 String

文字種のカウントの条件と、同じ文字種の連続の条件を別々にチェック

code

C - 11/22 Substring

特定の文字種の連続を考えたいのでランレングス圧縮。
条件を満たす区間の最長を求めるので尺取法も使えそうだが、区間が条件を満たさなくなった時に左端を動かしても満たすようにできないので、使えない。

code

Substring の最長の文字列を求めるのに、スライスで保持して後で比較するのではなく、現在の最長を記録・更新する方がパフォーマンス良かった。

D - 1122 Substring / 尺取法

条件を満たす区間の最長を求めるので尺取法が使えそう。以下の性質から、利用可能なことがわかる。
- 空配列も条件を満たすので、区間が条件を満たさなくなった時に左端を動かして満たすようにできる。
- ある区間が条件を満たすかどうかは、含まれている要素の種類の記録と、追加した２つの要素が同じかどうかの比較から簡単に判定できる。
区間をどのように伸長すべきか考える。 1122 String は 2 連続する異なる文字種から構成されるので、2 づつ伸長する。
偶数インデックス始まりの区間は偶数インデックス始まりの区間にしか変化できず、奇数についても同じ。なのでインデックス 0 から始めるチェックとインデックス 1 から始めるチェックを２段階でやる。

code

380

A - 123233

文字列のカウント

code

文字列として入力を受け取って、split にしてスライスにした方が良かった。

B - Hurdle Parsing

愚直
特定の文字列の連続を考えたいので、ランレングス圧縮でも良かった

code

C - Move Segment / ランレングス圧縮

特定の文字列の連続を考えたいので、ランレングス圧縮

code

D - Strange Mirroring / 二進数

S が複数文字だと考えづらいので、1 文字の場合を考える。（後で、その考えを応用するために S が何セットあるのかで考える。）
桁数が倍々になっていくので、2 進数が使えないか考える。そしてポップカウントやビット演算が使えないかどうか考える。
桁数の二進数表記の最も左側の１が右から何桁目にあるのかで何回倍にしたのかが分かるようにしたいので、最初のセットを 0 セット目として考える。2 進数で数字を管理する場合、最初の数字は 0 とおいた方が良いことが多い。
桁数の二進数表記から、一番左の 1 を消すと反転の元となった桁数になる。よって何回反転前の桁数にいくと一番最初の 0 桁目になるのかが、ポップカウントで求められる。

code

379

A - Cyclic

整数の特定の桁の数を取り出す

code

B - Strawberries

計算量少ないので愚直
問題文の X(large x), x(small x), 0(zero), O(large o), o(small o)が見分けづらいので注意！

code

C - Sowing Stones

入力値がソートされていそうでソートされていないことがあるので注意。入力例のみ偶々ソートされていることもある。
数列の和の公式 $(A_i+A_n)*N/2$
- ループせずに和が求められる
条件が成立することのチェック、求めたい値を求めることを分けて考える。

code

D - Home Garden / 遅延評価

遅延評価
二分探索
- 二分探索は単調非減少性を満たすようにソートされていないと使えない。（condition(arr[i]) == true なら condition(arr[i+1]) == trueを満たす。）

code

378

A - Pairing

何ペア作れるか = ペアになりうる要素の数 / 2

code

変なやり方で解いてた：

B - Garbage Collection

割り算、余り、場合分け

code

C - Repeating

メモ化？（後で比較に使う要素をあらかじめ記録）

code

D - Count Simple Paths / DFS（グリッド）

グリッド
DFS
- 「探索済みノードを記録するマップ（グローバル変数）」「探索の深さ（グローバル変数）」「探索を行う再帰関数」で行う。
- 「探索を行う再帰関数」では開始ノード、現時点の探索の深さを引数に取る。隣接ノードでループをし、その中で再帰する。関数が呼び出し元に戻るときに、探索済みノードのマップをリセットする。
グリッド内の条件を満たす経路の個数を求める問題なので DFS。
- BFS と比べて、キューを使わずに死路を早く切れるのでメモリが少なく済み、再帰処理で簡潔にかける。

code

377

A - Rearranging ABC

文字列並び替え
文字列 A を同じ文字数の B に並び替えられるかどうかは、B に含まれる各文字種のカウントと、A に含まれる各文字種のカウントが一致しているかどうか。

code

B - Avoid Rook Attack

グリッド
愚直

code

C - Avoid Knight Attack

グリッド
グリッドサイズが大きいので、セルではなくより数が少ない駒の位置でループを回す

code

D - Many Segments 2

区間が登場する問題だが、尺取法は使えない。 有効な区間を見つけたときに、左端を動かすことでも新たに有効な区間を見つけられる可能性があるため。
2 つの数字の組み合わせの個数を考える問題だが、1 つの数字を固定し、それに対して何通りのペアが考えられるか（0 通りでも OK）を考えるのが筋がいい。

code

376

A - Candy Button

愚直

code

B - Hands on Ring (Easy) / 円環

円環
1 と N が隣合う所が含まれる範囲だと都合が悪いので、回転させて含まれない範囲にする
始点と終点を入れ替えても問題ないなら始点 < 終点になるように入れ替える（考えやすくなる。パターンも減る。）

code

C - Prepare Another Box

二つの配列を同時にイテレート。特定のタイミング以降インデックスがズレるのに注意。

code

D - Cycle / BFS（有向グラフ）

BFS
- 「探索済みノードを記録するマップ」「次にどのノードを起点に隣接を探索すべきかを記録するキュー」を使う。
単純有向グラフ（自己ループなし、同じ方向の辺の重複なし）
- edges := make(mmap[int][]int) // 各頂点からどの頂点へ辺が伸びているか
ある頂点を通る閉路を見つけるには、その頂点から始めて、その頂点へ向く辺が伸びている頂点に到達するまで探索する。最短距離の閉路の距離を求める問題なので BFS。

code

375

A - Seats

全探索

code

B - Traveling Takahashi Problem

愚直に計算
べき乗の計算はmath.Pow()でやるとズレるので、2 乗程度なら掛け算でやる

code

C - Spiral Rotation / グリッドの回転

正方形グリッドの回転
正方形グリッドの周のレイヤー
問題のタイトルがヒント

code

補足

 正方形グリッドの回転座標(h, w)は、一辺 N の正方形グリッドを 90 度回転させると(w, N-h+1)に移動する。

 正方形グリッドの周のレイヤー一辺 N の正方形グリッドの一番外側の周のマスを 1 周目、二番目に外側の周のマスを 2 周目、...とした時に、マス目(h, w)が何周目かは min(h, w, N-h+1, N-w+1)となる。
左下から右上に対角線を引くと左側のエリアのマスについては、min(h, w)周目となる。
右側のエリアは左側のエリアの線対象な位置のマスと同じ週目になるので、min(N-h+1, N-w+1)周目となる。
対角線が通っているマスはどちらでも同じ。

D - ABA / メモ化

メモ化
N が巨大なので計算量を O(N)にする工夫

code

374

A - Takahashi san 2

strings.HasSuffix()

code

B - Unvarnished Report

愚直

code

C - Separated Lunch / ビット全探索

N 個の部署が、A、B いずれかのグループに属するので、パターンは $2^N$ 。起きうるパターンが $2^N$ で N が現実的な範囲のため、ビット全探索。
for i := 0; i < 1<<N; i++ でループし、各桁が 1 かどうかで各部署のグループ分けを決めれば全パターン試せる。

code

D - Laser Marking / 全探索、DFS（順列）、ビット全探索

パターン数は、線の順列パターン * 各線をどちらから始めるか： $O(N! * 2^N)$
- Max： $O(6! * 2^6) = O(46080)$
- 十分に少ないので、全探索できる。
順列のパターン（木構造になっている）は、DFSで列挙できる。
各線をどちらか始めるかは、ビット全探索で列挙できる。

code

373

A - September

愚直

code

B - 1D Keyboard

問題文をよく読む（キー配列が S で固定なのか AtoZ 固定なのか、最初逆で認識していた。）

code

C - Max Ai+Bj

ソート

code

D - Hidden Weights / BFS or DFS（有向グラフ）

ある２点とその辺について、辺の向きに関わらず一方の点の値が分かっていれば他方の点の値が分かる。
- $toX - fromX = weight$ から $fromX - toX = -weight$ が成り立つため。
- var weights map[int][][2]intのように重みを記録し、from => to だけではなく to => from の重みも記録する。有向グラフであることに囚われすぎない。
あとはDFSでもBFSでも列挙可能。
map の初期化、要素へのアクセスより、スライスの初期化、要素へのアクセスの方が大分高速。
サンプルが複数あるときは、それぞれが重要な示唆を持つ可能性があるので、できる限りそれぞれ図を書く。
- 今回も孤立ノードや、どこからも辺が向いていないノードのパターンを教えてくれていた。
問題タイトルがヒント

code

372

A - delete .

愚直

code

B - 3^A / N 進数

2 進数以外の N 進数ではビット演算が使えないものの、実装で N 進数表記を使ったり、考察パートで N 進数の考えを使ったりすることがある。
M を 3 進数表記すると、3 の乗数の足し算で M を表現していることになる。
後は 3 進数の桁を 0 桁目からループしていき、桁の数字の数だけ桁数 k を ans 配列に追加していけば、答えになる。
あるいは、M に対して 3 の 10 乗（制約上のマックスの乗数）を可能な限り引く、3 の 9 乗を可能な限り引く...という様にして解いても良い。

code

C - Count ABC Again

全探索は $N * Q = 4^{10}$ なので間に合わない。Q 個のクエリを順に処理することは確定なので、N のループをなくす。
「ABC 部分文字列がある場所をマップに保存しておいて、クエリ処理時の探索に使う」でもいいし、「ABC 部分文字列の数を保存しておいて、クエリ処理時に毎回影響を受ける範囲を探索する」でもいい。

code

D - Buildings / スタック

探索すべきものの条件について、直感的な概念に言い換えることができることも多い。　今回は、ビル i に対するビル j は、ビル i の前方に見えるビル。
前からの処理が難しそうなら、後ろからの処理を考える。
ビル i に対するビル j の高さの配列を考える。これは単調増加である。
後ろから処理していき、ビル i に対してビル i+1~ビル n で単調増加な配列を作ることを考える。データに対しビル i+1 を追加していき、その際事前にビル i+1 より低いビルを削除していけばいい。
最後に追加したデータから取り出して削除するということなので、スタックが使える。スライスからデータを削除するコストは $O(len(sl))$ なので、スライスは使わない。削除回数は最大 N なので、 $O(N)$ で処理できる。

code

371

A - Jiro

大小関係、愚直
頭だけで考えると絶対混乱するので、紙に書いて整理する（パターン： $2^3$ ）

code

B - Taro

愚直

code

C - Make Isomorphic / 無向グラフ、順列、全探索

無向グラフ A、B が同型とは、 A の頂点 1, ... N に対し、B の頂点 1, ...N を任意の順番で一対一対応させ、Ai - Aj 間の辺の有無と Bi' - Bj'間の辺の有無が全て一致している対応が存在するということ。
- 頂点数は同じである必要がある。
- 頂点の対応のパターンは、頂点の順列（N!）で列挙できる。
無向グラフをデータとして保存するときは、Ai - Aj と Aj - Ai を両方記録する。片方しか記録せず、後で計算量節約できるかもなどと考えるとおかしなことになる。（今回なった。）
```
var graph map[int][]int
a, b := read2Ints(r)
graph[a] = append(graph[a], b)
graph[b] = append(graph[b], a)
```
計算量：グラフ G の頂点とグラフ H の頂点の対応 _ 6 頂点 _ 隣接頂点の diff： $O(6! * 6 * 5) = O(21600)$
- 全探索可能

code

D - 1D Country / 累積和、二分探索

区間[L, R]の人口 = 「R 以前の R に最も近い村までの人口累積和」-「L より前の村までの人口累積和
「R 以前の R に最も近い村」「L より前の村」は二分探索で見つけられる。
- 前者は累積和のスライスを逆順にしたものを用意し探索できる。
二分探索の条件や、結果を元にした場合分けをしっかり考える。

code

370

A - Raise Both Hands

愚直

code

B - Binary Alchemy

愚直、命名をちゃんとやると混乱しない

code

C - Word Ladder

文字の辞書順
- 文字は辞書順で比較可能："a" < "b" // true
- アルファベットはこの様にイテレート可能(今回は使ってないが)：
```
// 'a' の文字コード: 97, 'z' の文字コード: 122
for ch := 'a'; ch <= 'z'; ch++ {
  fmt.Println(string(ch))
}
```
必要な変更を列挙。辞書順を早める変更と、遅める変更に分ける。先に前者を適用する。そして後者について、元の文字列の後ろの方から変更した方が辞書順の悪化が少なく済むので、逆順にソートしてから適用する。

code

D - Cross Explosion / メモ化

$max(H*W)=4*10^5$ より、正方形グリッドで考えると 600*600 程度。一度のクエリに対し、最悪縦横全てで 1200 確認する必要がある。クエリは 20 万個なので、 $O(2400万)$ となり全探索で間に合いそうだが...
40 万 * 1 の様なグリッドで、20 万回同じ箇所を爆破する様な場合を考えると、計算量は数列の和の公式より $(1+20万)*20万/2 = 約20億$ となり、間に合わない。
メモ化を利用し、ある座標から上下左右を探索したときに、どこまで空マスが続いたかを記録し、次回以降の同じ座標の探索時に利用する。
（後半の）問題の計算量があまりに少なそうに思えたら、エッジケースで計算量が増大しないか考える。誤答のペナルティは重い。

code

369

A - 369

A, B, x の配置と、A == B と A != B である場合の場合分けを考えて、コードに落とし込む。

code

B - Piano 3

右手と左手の位置を記録しながら、コストを足していく。

code

C - Count Arithmetic Subarrays

有効な区間の数を求める問題とも言えるが、有効な区間から左端を動かすことでも新たな有効区間を見つけることができるので、尺取法は使えない。
left, right を記録していき、探索する。右端を increment するループ。
```
left := 0
right := 0
ans := 1
for right = 1; right < N; right++ {}
```
探索で等差数列の長さが順調に伸びていく場合を考えると、長さが伸びる度に組み合わせが現在の範囲の長さ分増えることが分かる。図を書くと分かる。
重要なのは右端を伸ばして、等差数列が破綻した時に左端と右端をどこの位置にするのかということ。 左端を右端-1 のところに移動させ、長さ 1 の状態から 1 伸びた場合の様にすればいい。あとはうまくコードに落とし込むだけ。

code

D - Bonus EXP / DP

全てのモンスターの倒す倒さないのパターンは $2^N$ なので、全探索は無理。
1 体目のモンスターまで処理した時の最大経験値を記録、それを元に 2 体目のモンスターまで処理した時の最大経験値を計算し記録...ということができないか？この様な考え方がDP（動的計画法）。
k 体目のモンスターを処理する時の経験値の変動は、そのモンスターが偶数体目の討伐対象か、奇数対目の討伐対象かによる。(倒す倒さないの選択もあるが。)これは、k-1 対目まで処理した時点で、偶数体討伐済みか奇数体討伐済みかと言い換えることもできる。
以下の DP テーブルを作成することで問題が解ける。値から次の列の値を求めるために、どんな状態を記録する必要があるかを考え、DP テーブルの設計をする必要がある。　この設計が DP で一番難しい。
- 縦：偶数体討伐済み or 奇数対討伐積み
- 横：何体目まで処理したか
- セルの値：その状態での最大経験値

code

368

A - Cut

スライスの操作

//「index x-1まで」「x番目まで」
// xにはlen(sl)まで渡すことが可能！
// sl[0] ~ sl[x-1],
sl[:x]

//「index xから」「x+1番目から」
// sl[x] ~ sl[len(sl)-1]
sl[x:]

code

B - Decrease 2 max elements

数列の長さ N、要素の上限値 Ai が 100 なので、全探索可能。変に効率化を考えずに愚直にやる。

code

C - Triple Attack / 割り算

敵の数 N の大きさ、体力 Hi の大きさから、愚直に一回ずつ攻撃する方法だと間に合わない。
3 回ごとに 5 ダメージを与えられる。
- $体力/5$ で、何回攻撃する必要があるかが求まる。
- $商 * 5 + (余りに対して必要な攻撃回数)$
重要なのは余りに対して必要な攻撃回数を求めることで、「その敵に対する最初の攻撃が通算何回目の攻撃か」「余りがいくつか」によって変わってくる。
- 分岐が多いので、switch case で書くと分かりやすく書ける。

code

D - Minimum Steiner Tree / 木、DFS

解説
木とは、「閉路」の無い「連結無向グラフ」のことである。
- 「連結」とは、任意のノード２点に対して１つ以上の経路が存在すること。
- 「閉路」が無いことから、任意のノード２点に対して２本以上の辺が存在しない。
- 頂点数 N の木の辺の数は、N-1 である。
- 頂点の隣接ノード数のことを 「頂点の次数」 という。
- 木は、任意の頂点をルートノードとする階層構造として捉えることができる。
- 木構造における 「葉」 1 とは、子ノードを持たない木構造の最も末端に位置するノードのこと。
- 木構造も、通常の隣接リストに格納できる。
任意の指定された頂点をルートとし、葉の階層から順に指定されていないノード、次数が 1 のノードを削除していくと、指定のノードが全て含まれた最小の部分木になる。なぜなら、指定されたノードと、ルートと指定されたノードを繋ぐために必要なノードしか残らないから。
上記の方法は木を変形させながら探索せねばならず難しいので、別の方法を考える。
- 要は、自身のノード以下に指定のノードが存在しないノードは削除可能。
- 任意の指定された頂点からの DFS で、葉に到達したら return。その過程でvar numOfPicked map[int]int // そのノード以下の階層に、指定された頂点がいくつ含まれているかを埋めていき、最後にマップのゼロ以外の要素をカウントすれば答えとなる。

code

GitHubで編集を提案

383

B - Humidifier 2 / 全探索

C - Humidifier 3 / 多始点 BFS or BFS + メモ化

多始点 BFS

BFS + メモ化（※ 多始点 BFS の方が簡単なのでそっちでいい）

D - 9 Divisors / 約数、巨大な数

382

C - Kaiten Sushi / 二分探索

D - Keep Distance / DFS（数列）

381

D - 1122 Substring / 尺取法

380

C - Move Segment / ランレングス圧縮

D - Strange Mirroring / 二進数

379

D - Home Garden / 遅延評価

378

D - Count Simple Paths / DFS（グリッド）

377

376

B - Hands on Ring (Easy) / 円環

D - Cycle / BFS（有向グラフ）

375

C - Spiral Rotation / グリッドの回転

正方形グリッドの回転

正方形グリッドの周のレイヤー

D - ABA / メモ化

374

C - Separated Lunch / ビット全探索

D - Laser Marking / 全探索、DFS（順列）、ビット全探索

373

D - Hidden Weights / BFS or DFS（有向グラフ）

372

B - 3^A / N 進数

D - Buildings / スタック

371

C - Make Isomorphic / 無向グラフ、順列、全探索

D - 1D Country / 累積和、二分探索

370

D - Cross Explosion / メモ化

369

D - Bonus EXP / DP

368

C - Triple Attack / 割り算

D - Minimum Steiner Tree / 木、DFS

Discussion