🦁

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

2024/11/29に公開

AtCoder

tech

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

384

A - aaaadaa

愚直

code

B - ARC Division

愚直

code

C - Perfect Standings / 組み合わせ（ビット全探索 or 再帰）、辞書順ソート

配列の部分列とは、元の配列からいくつかの要素を順番を保ったまま選んで作られる新しい配列。組み合わせの数は $nCr$ である。（n:配列の長さ、r:部分列の長さ）
配列の連続部分列とは、元の配列からいくつかの連続する要素を順番を保ったまま選んで作られる新しい配列。組み合わせの数は $n-r+1$ である。（n:配列の長さ、r:部分列の長さ）
部分列の列挙は、ビット全探索または再帰関数の実装で行える。

code

D - Repeated Sequence / 無限数列、尺取法 or 円環 + 累積和

規則的な周期をもつ無限数列の、和が S となる区間を求めたい。和が $S\bmod 一周期分の和$ (以降 remainder と呼ぶ)となる区間を見つければ良い。
ただし、一周期分の区間を探索するのでは足りない。[N-1, N, 1, 2]のような区間があり得るから。

解法 1 尺取法

二周期分の数列を用意し、そこを尺取法で探索することで全ての区間を探索することができる。

解法 2 円環の性質 + 累積和

円環における A to B の距離が x である時、B to A の距離は全周-x である。
一周期分の累積和を配列に記録する。配列を左から探索し、それ以前の累積和に以下と一致する値がないかを調べれば良い。
- $現在の累積和 - remainder$
- $現在の累積和 - (一周期分の和 - remainder)$
類題: 367 D - Pedometer

code

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 で、グリッドサイズ、始点ノードの数、移動距離が 10^6 なので、全探索は間に合わない。
始点ノードから一定距離の条件を満たすノードの探索なので、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

367

A - Shout Everyday

数直線を書いて場合分け

code

B - Cut .0

数字を文字列として受け取る

code

C - Enumerate Sequences / DFS（数列）

長さ N であり、i 番目の要素が[1, ..., Ri]のいずれかである数列を列挙し、その数列に対して総和が K の倍数であるかどうかをチェックすればいい。
上記の数列のパターンはグラフ構造で表せるため、DFSで列挙可能。

code

D - Pedometer / 円環、累積和、合同式

円環

1, 2, ...N, 1 という円環がある時、1~N の数直線で、全ての区間の距離を列挙することができる。
円周の距離をCとすると、地点 a から b までの距離 x と、地点 b から a までの距離 y（a < b）の関係は、 $y = C - x$ となる。
1~N の数直線で任意の地点 a から b までの距離を列挙でき、その $C-x$ を取れば地点 b から a の距離を列挙できる。

累積和

数直線上から２点間の距離を素早く出すために、距離の累積和が使える。

合同式

x - y が M の倍数になるのはどんな場合か？
- $x \equiv y \mod M$ の時である。
- $(M*i + a) - (M*j + a) = M(i-j)$ となり、M の倍数であることが保証される。
よって、累積和の数直線上を順に探索していき、現在の累積和より前の累積和で、mod M で合同なものがいくつあるのかを数えて答えに足していけばいい。
- var m map[int]int // key: 0 ~ M-1, value: count に記録していく。
上記は、累積和の数直線上を通常通り探索する場合の話。逆側の経路の場合はどうなる？
- $y = C - x$ である。 $y \equiv 0 \mod M$ である y を見つけたい。
- => $x \equiv C \mod M$
- => $rightSum - leftSum \equiv C \mod M$
- => $rightSum - C \equiv leftSum \mod M$ である leftSum を見つければいい。
go の%演算と、数学上の moduro 演算は、割られる数が負の時に結果が違うので注意！ 参照

code

366

A - Election 2

愚直

code

B - Vertical Writing

文字列の数、最大文字数ともに 100 と小さいため、辺に工夫せず全探索でやるべき。
二重スライスに縦にアクセスする。
文字列末尾のトリムはstrings.TrimRight(s, "*")

code

C - Balls and Bag Query

マップ使うだけ。

code

D - Cuboid Sum Query / 三次元累積和、包除原理

立方体のブロックに数字が入っていて、指定の範囲の数字の合計を出す問題。
3 次元累積和を記録し解く。元々の数字を 3 次元配列（各次元に 0 埋めされた余剰を作っておく）入れ、それを各次元でイテレートし、cube[x][y][z] += c[x-1][y][z]と処理していくことで 3 次元累積和が完成する。
累積和から特定の範囲を出すときは、範囲を含む一番大きな累積和から、引くべきところを引き、重複して引いたところを足すことで求められる。
集合の和を求める時に使う包除原理を使う。
- $∣A\cupB∣=∣A∣+∣B∣-∣A\capB∣$
- $∣A\cupB\cupC∣=∣A∣+∣B∣+∣C∣-∣A\capB∣-∣B\capC∣-∣C\capA∣+∣A\capB\capC∣$
- 「各集合を足す　=> 2 つの集合の交差を"引く" => 3 つの集合の交差を"加える" => 4 つの集合の交差を"引く" => ... 」数が集合の種類数 N になるまでこれを繰り返せばいい。

code

365

A - Leap Year

愚直に上から条件を評価

code

B - Second Best

ソート後も元のインデックスを保持するために、インデックスと値を持った構造体にした上でそのスライスをソート。

code

C - Transportation Expenses　/ 二分探索(応用)、累積和

答えが infinite になる時はどんな時か？全ての交通費が実費精算されるので、実費の総和が M 以下なら補助上限を infinite にできることになる。
x はどんなものを試せばいい？求めたい値が漠然としている時は、上限と下限を考える。
- 上限は、制約より M である。（一人の交通費が M 円で、他の人が全員 0 円の時実際 x = M となる。）
- 下限は、M/N である。全員に支給しなければならないときに、総和が M 円となり予算を使い切れる。支給しなければならない人間が減った場合、x は M/N より大きくなるので、M/N が下限。（支給人数が N より増えることもない。）
x について、N/N から M までの数字を試せばいい。これらの数字は単調増加性を満たす。（x が増えるほど、交通費補助額の総和が増える。）なので、二分探索が使える。
- 計算量は $O(\log M) = O(\log 2 * 10^{14}) \approx O(\log 2^{43}) \approx O(43)$ なので、間に合いそう。
$交通費補助額の総和 = 実費精算の範囲 + x * 実費がx以上の人数$
- 実費の配列の累積和を作成しておき、「x 以上」で実費の配列を二分探索すれば、 $O(logN)$ で x ごとの交通費補助額の総和を求められる。

code

D - AtCoder Janken 3 / DP

相手が同じ手を連続で出した時だけ win と tie を交互にすればよく、それ以外は勝ち続ければいい？
- 相手の同じ手の連続に対して、win から入るか tie から入るかのパターンがある。
- SSP の様なパターンの場合、win から入ると win, tie, tie の一勝で、tie から入ると tie, win, win の二勝になる。
現在の勝利数の最大化が、前回の選択に依存している。このことから、DPが使えそう。
テーブル設計
- 横：何回勝負したか
- 縦：[0]その回を win [1]その回を tie
- セル：最大の通算勝利回数
状況変数（win の場合に最後に出した手、tie の場合に最後に出した手）を更新するのは、現在の列のセルに値を全て入れてから！

code

364

A - Glutton Takahashi

条件によってループが終了しても、最後のイテレートなら成功になる。
- 「甘い料理を 2 つ連続で食べると気持ち悪くなってしまい、"その後"料理が食べられなくなってしまいます」

code

B - Grid Walk

グリッドのライブラリを活用するだけ。

code

C - Minimum Glutton / 累積和

甘さの降順ソート、しょっぱさの降順ソートを作り、そこから累積和を作る。
各累積和に対して、それぞれの限度以上になる地点を二分探索する。
上記のインデックスの小さい方が、いずれかの限度を超すための最小の要素数となり答え。

code

D - K-th Nearest / 二分探索(応用)

入力値がソートされている保証がないのでソートする（a_i の配列）
条件を満たす距離を求める問題。ソート可能な数直線上の座標などが存在するし、二分探索が使えないだろうか？
距離の下限は 0 であり、上限はmax(abs(b_j-as[0]), abs(b_j-as[len(as)-1]))
距離が増加するのに伴って単調増加するものはないか？ => 基点から距離以内に存在する座標の数が単調増加。
基点、距離からその範囲の座標の数を返す関数を実装し、それを二分探索の条件関数として渡せばいい。

code

363

A - Piling Up

愚直

code

B - Japanese Cursed Doll

命名ちゃんとすると混乱しない

code

C - Avoid K Palindrome 2 / 順列、回文

文字列の並び替え全パターンの探索が必要。 $O(10!) \approx 360万$
与えられた順列を次の辞書順の順列にならび変えるアルゴリズムは高速。
- DFS で全列挙する実装は、同様の計算量だがスライスを何度も操作やコピーする関係上遅い。
長さ N の文字列に長さ K の任意の回文が含まれるかの判定の計算量は、以下のとおりで、全探索と組み合わせても十分高速
- $O((N-K+1) * K) = O((10-5+1)*5) = O(20)$

code

D - Palindromic Number / 回文

回文数は、一桁の場合は 10 通り。N 桁の場合は、N 桁目から(N+1)/2 桁目まで（左半分）のパターン数通り。（右半分は左半分を転写するだけなので。）
回文数の総数が N を超えるまで、桁数を増やしながら回文数の総数を足していく。そうすると、N 番目の回文数が、何桁の回文数の何番目かがわかる。あとは上手くコードを書く。

code

362

A - Buy a Pen

色（string）、価格を持った構造体のスライスを作り、ソートしてループ

code

B - Right Triangle

ピタゴラスの定理が成り立つ時、その三角形は直角三角形である。
辺の長さ（ルート）の比較は小数点の精度の問題で正しくできない時があるので、辺の長さの二乗を比較する。

code

C - Sum = 0 / 貪欲法

答えの配列を、各要素の下限で初期化する。
sum が 0 になるまで、各要素について順に、min(要素の上限, 0 - 現在の総和)だけプラスしていく。（貪欲法）

code

D - Shortest Path 3 / ダイクストラ法、優先度付きキュー、ヒープ

解説
ダイクストラ法を使って、重み付き経路における２点間の最短経路を求めることができる。
- 始点から任意の点に到達する最小コストを考える。始点のコストは 0 で確定。
- 始点から隣接するノードのコストを記録する。
- コストが記録されており確定されていないもののうち、最初のコストのノードのコストを確定させる。
- そしてそのノードの隣接ノードのコストを調べ、記録する。（すでに記録済みのノードに、より少ないコストで到達できる場合は上書きする。）
- 二つ前の手順に戻る。全てのノード（あるいはゴールとなるノード）のコストが確定するまで繰り返す。
ダイクストラ法は、優先度付きキュー（ヒープ） で実装できる。
- 優先度付きキューとは、優先度の高いものから取り出されるキューである。
- 優先度付きキューは、ヒープというデータ構造で実装できる
- ヒープは、キー順序性を満たす完全二分木である。

完全二分木とは

完全二分木は、以下の条件を満たす二分木のことを指します：

レベルが満たされている:
- 木のすべてのレベル（深さ）は完全に埋まっている（すべてのノードが存在する）。
最後のレベルでは左詰め:
- 最下段のノードが左から順番に埋まっている。

ヒープとは

ヒープは、以下の特性を持つデータ構造です（ソートされた配列もヒープと言うことができます）：

キー順序性を満たす:
- 各ノードの値は、その子ノード、左にあるノードの値よりも大きいまたは小さい。
  - 最大ヒープ: 親ノードの値が子ノード、左にあるノードの値以上。
  - 最小ヒープ: 親ノードの値が子ノードの左にあるノードの値以下。
形状が完全二分木である

確定済みノード、各ノードの到達コストをそれぞれマップで記録。{始点ノード, コスト0}を優先度付きキュー（コストが少ない物を優先）に入れ、探索開始。キューから要素を取り出すときに、そのノードを確定させる。隣接ノードのコストを調べ、キューに入れていく。

code

GitHubで編集を提案

384

C - Perfect Standings / 組み合わせ（ビット全探索 or 再帰）、辞書順ソート

D - Repeated Sequence / 無限数列、尺取法 or 円環 + 累積和

解法 1 尺取法

解法 2 円環の性質 + 累積和

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

367

C - Enumerate Sequences / DFS（数列）

D - Pedometer / 円環、累積和、合同式

円環

累積和

合同式

366

D - Cuboid Sum Query / 三次元累積和、包除原理

365

C - Transportation Expenses / 二分探索(応用)、累積和

D - AtCoder Janken 3 / DP

364

C - Minimum Glutton / 累積和

D - K-th Nearest / 二分探索(応用)

363

C - Avoid K Palindrome 2 / 順列、回文

D - Palindromic Number / 回文

362

C - Sum = 0 / 貪欲法

D - Shortest Path 3 / ダイクストラ法、優先度付きキュー、ヒープ

Discussion

C - Transportation Expenses　/ 二分探索(応用)、累積和