🦁

AtCoder Beginer Contest 351~396 D or E までの要点・解答（Go）

2024/11/29に公開

AtCoder

tech

prev: AtCoder Beginer Contest 301~350 D or E までの要点・解答（Go）

※ 個人的なメモ。コードは比較的読み易いと思います。
※ 愚直に解くだけの問題は省略。

396

C - Buy Balls

価値が正の黒いボールは全て取った方がいい。価値が正の白いボールの数が、黒のそれ以下であればそれら両方を取ればいい。問題はそうでない時。
黒いボール、白いボールを価値順ソート。二分探索で 0 以上の Idx を見つける。白いボールの 0 以上の領域の方が長ければ、黒いボールと同じ数はまず取っておく。その後、黒と白のまだ取っていない領域について、価値の合計が正ならば貪欲に取っていく。（範囲外アクセスにも注意。）

code

D - Minimum XOR Path / DFS（バックトラック）

単純連結無向グラフの、単純パス（同じ頂点を通らない）の列挙は、バックトラックありの DFS で可能。
- 頂点 1 から N の単純パスの列挙は、 $O((N-2)!)$
  - 完全グラフの場合の最悪計算量。他のノードの順列に等しいため、N-2 の階乗になる。
ノード数が少なく間に合うので、XOR をとりながら DFS する。

code

E -　 Min of Restricted Sum　/ XOR、連結成分分解

As := make([]int, 0)を作り、-1 で初期化。index i のノード数 N のグラフを作り、node X, Y を重み Z の辺で結ぶ。
ある頂点 i のAs[i]を適当にゼロで固定すると、辺で繋がったノードが連鎖的に prevNode^zの値で決まっていく。あるいは矛盾が露わになる。
連結成分毎に上記をやる必要があるので、予め連結成分分解をやっておく。
問題はこれで見つかる As が、総和が最小の組み合わせではないこと。
XOR は桁毎に独立で考える。　ある桁の最終的な XOR が同じなら、立っているビットの合計が少ない方がいい。XOR はビットを反転させることと同義なので、それぞれの桁について、あり得るビットの立ち方は適当に作った As のそれか、それを反転させたものである。
各連結成分について、各桁（0~30 を固定で見れば制約より十分）について、0 と 1 をカウントする。1 の方が多ければ、各 As[i]のその桁のビットを反転させる。

code

395

C - Shortest Duplicate Subarray / 尺取法

典型的な尺取法の問題
あるいはlastIndexes map[int]intを作成し-1で初期化し、同じ数字が出現したときにその距離でminAnsの更新を試みる方法でもいける。

code

D - Pigeon Swap / ポインタ

クエリ 3 を高速に処理するためにvar birdsNest map[int]intのようなものは必要。
クエリ 2 は、var nestBirds map[int]map[int]struct{}の中身をスワップすれば巣の鳥を高速に入れ替えられるが、それら全ての鳥のbirdsNestの高速な更新が無理。
var birdsNest map[int]*intとしてポインタを使いさらにvar nestNoPtr map[int]*intを管理すれば、ポインタの値のスワップ、nestNoPtrの値のスワップでクエリ 2 も $O(1)$ でいける。

code

E - Flip Edge / ダイクストラ法、頂点倍加

2*Nのサイズのグラフを用意し、i <=> i+N (cost: X)の辺、u => v, v+N => u+N (cost: 1)の辺を張る。（頂点倍加）
あとはダイクストラをし、min(dists[N-1], dists[2*N-1])が答え。

code

394

C - Debug

前から見ていき、Ss[i]+Ss[i+1]==WAがあればACに置換。それによりSs[i-1]+Ss[i]がWAになる可能性が生まれるので、再帰的に戻ってチェック&置換。
外側のループで一回、再帰関数で最大一回文字列をチェックする必要があるので、 $O(2 * |S|)$
- 一度再帰関数で戻ってチェック&置換した領域に、後の別のSs[i], Ss[i+1]への変更起点の再帰で戻ってくる可能性はない。

code

D - Colorful Bracket Sequence / Stack

括弧は閉じなければならない。左括弧を Stack に入れていき、右括弧が現れたらPop()して比較。Stack が空または Popped が適切な相方でない場合破綻する。最後まで破綻せずStack も空なら、条件を満たす。
$O(|S|)$

code

E - Palindromic Shortest Path / 回文、BFS

最短経路の問題なのでBFSが使えそう。
両端から同じ文字を追加し、qItem{startNode, endNode, currentLen}という状態をキューに積む BFS で解けそうだが、最後に両端が落ち合う時に「新しい頂点で落ち合う場合=偶数長の回文」と「nextStartNode == endNode (i.e. nextEndNode == startNode)で落ち合う場合=奇数長の回文」があり、早く見つかった回文が最短の回文とは限らないため上手くいかない。
逆に真ん中から BFS をし、dist[i][j]テーブルを埋めていく。
- ある頂点（辺の空集合）から始まる偶数長の回文のための qItem（ex, qItem{0, 0, 0}）を先にキューに積む
- その後にある辺から始まる奇数長の回文のための qItem（ex, qItem{0, 1, 1}）をキューに積む
- グラフを陽に持たない BFS をし、dist[i][j]を埋めていく。上記の始点ノードの積む順番により、dist[i][j]には最短長の回文の長さが最初に入る。
- startNode, endNodeの組み合わせは $N^2$ であり、それらが一度ずつキューに積まれる。 BFS のループ 1 回につきnextStartNode, nextEndNodeの列挙が $N^2$ の二重ループで行われるので、全体の計算量は $O(N^4)$
  - $O(100^4) = O(10^8)$ は定数倍が軽ければ 2sec に間に合う。
回文の問題は真ん中の文字から考えたり、偶数長と奇数長を分けて考えたりが有効。

code

393

B - A..B..C

全ての間隔（dist）を試す。maxDist := (N-3)/2
if Ss[i] + Ss[i+1+dist] + Ss[i+2+dist*2] == "ABC" { ans++ }

code

C - Make it Simple

グラフを作りながら、その辺が自己ループまたは既に存在する辺ならans++。
隣接リストの要素を Map にして、 $O(1)$ で既に存在する辺かどうか求められる様にしておく。

code

D - Swap to Gather

最善の操作（の内の一つ）は、中央にある1に他の 1 を寄せていくことである。
最終的な集合の中心を x だけ右（左でも同じ）にずらすことを考える。1の数を k とする。
- k が奇数の場合
  - newCost := cost + x * (k/2) - x * ((k-1)/2) となりコストが増加する。
- k が偶数で、右よりの中央を選択していた場合
  - newCost := cost + x * (k/2 + 1) - x * (k/2) となりコストが増加する。
- k が偶数で、左よりの中央を選択していた場合
  - newCost := cost + x * (k/2) - x * (k/2) となりコストが変わらない。
- よって最終的な集合の中心を中央にある1の座標から動かしてもコストが改善しないため、中央の 1 に寄せるのが最善。
1が登場する Index を記録する。oneIndexes[len(oneIndexes)/2]を中心とする。（上記より、k が偶数個の場合も左右のどちらの中央を選んでも変わらない。）
その後中央の左側、右側に何個1が連続しているかを記録しながら、移動コストの和を求めていく。

code

E - GCD of Subset / 最大公約数、調和級数

制約より組み合わせ全探索は無理。各 i に対して、Ai の約数であり、約数の出現回数が K 以上の中で最大のものが求められばいい。
約数列挙は $O(\sqrt N)$ かかるため、さらなる工夫が必要。（高度なアルゴリズムを使えば別だが。）

約数の問題は倍数を考える。 1~M（最大の A）の約数候補に関して、その倍数を数えることはできる。

var numCnt map[int]int // Asをループして数えておく
multipleCnt := make(map[int]int, M)
for i := 1; i <= M; i++ {
  for j := i; j <= M; j+=i {
    multipleCnt[i] += numCnt[j]
  }
}

この様なループは $O(M*\log M)$ であることが知られている。
- 内側のループの計算回数は $\sum_{j=i}^{M} M/i$ と表現でき、これは調和級数として知られ、計算量が $O(\log M)$ である。
- 級数とはシグマ式で表せる、法則性を持った項の総和のこと。
- 調和級数は項の分母が徐々に大きくなっていくシグマ式。その総和は無限に発散するが、発散が非常に緩やかであり計算量は $O(\log M)$ 　（証明には積分等の知識が必要。）

最後に1~Mまでの全ての数に対する最大の約数を求めて、出力時に使う。これも調和級数により

O(M * \log M)

ansSl := make([]int, maxA)   // ansSl[i]: Aがi+1のときの最大の約数
for i := 1; i <= maxA; i++ { // 1~maxAまでの約数を試す
	if multipleCnt[i] < K {
		continue
	}
	for n := i; n <= maxA; n += i { // 現在の約数の倍数であるnについて、最大の約数を更新
		ansSl[n-1] = max(ansSl[n-1], i)
	}
}

code

392

A - Shuffled Equation

組み合わせをハードコーディングするか、NextPermutation()で全順列を試す。
NextPermutation()をするときは、最初の呼び出しの時の引数に昇順ソート済みのスライスを渡す。
あるいは実は昇順ソートしてAs[0] * As[1] == As[2]を判定するだけで良い。（A が 0 を範囲に含んでいたら無理だったが。）

code

C - Bib

「i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数」を求める。そのために必要なマップをちゃんと言語化する。
- map[ゼッケン番号][人番号]
- map[人番号（見てる）][人番号（見られている）]
- map[人番号][ゼッケン番号]

code

D - Doubles / 確率問題、全探索

ダイス i, j を選んだ時の目が揃う確率は以下。（絶対に必要な数式を最初にちゃんと立てる。）
- ある特定の目が揃うパターンは、「i にあるその目のどれが出るか」*「j にあるその目のどれが出るか」。
- いずれかの目が揃う確率は、共通で存在する目について上記の総和をとり、総パターン数で割ればいい。
- $\dfrac{(\verb|cnt x on i|) * (\verb|cnt x on j|) + (\verb|cnt y on i|) * (\verb|cnt y on j|)...}{K_i * K_j}$
ダイスごとの目ごとのカウントマップを作成しておく。ダイス i, j を選んだ時の共通の目は、カウントマップの長さが少ない方でループを回して、もう一方に要素がなければ無視すればいい。
計算量は以下の様になる。 $_{100} C_2 = 4950$ のループの中で、上記の処理で間に合うのか？
- $O(\sum_{i=1}^{K-1}\sum_{j=i+1}^{K} min(len(cntMap_i), len(cntMap_j)))$
最悪計算量を考えると、実は各ダイスが均等な数の目（ $10^5/N$ ）を持っている時が一番大きい。
- 各ダイスの目の数を小さい順に $a_1, a_2, ...$ としたとき、計算量は以下の様にも表現できる。
- $O(\sum_{i=1}^{K}) (K-i)*a_i$
- もしダイスの目の数が均等でないなら、多いダイスの目の数を減らし、少ないダイスの目の数をプラスすることで上記の総和を増やすことができることになる。
- よって計算量は、 $O(\sum_{i=1}^{K-1}\sum_{j=i+1}^{K} N/10^5)$ となり、組み合わせの全探索が間に合う。

code

E - Cables and Servers / Union Find

サーバーをUnion Findで連結成分にわけ、不要な辺を張り替えて異なる連結成分を繋いでいけばいい。
不要な辺は、自己ループや多重辺だけではない。すでに同じ連結成分にあるサーバー同士を繋ぐ辺も無駄である。入力を受け取りながら Union Find でサーバーを連結させ、すでに連結済みなら不要な辺としてスライスに格納する。
ルートノードをマップで管理し、不要な辺に対して map からランダムに取り出した別のルートノードと連結させていく。（ルートノードで無くなったものをマップから削除する。）

code

391

B - Seek Grid

全探索。グリッドの範囲外アクセスを予防するため、必ずc.IsValid(H, W)する。

code

C - Pigeonhole Query

鳩を巣から巣に移動させなければならないため、鳩の現在の巣を管理する必要がある。var birdNestMap map[int]int
複数鳩がいる巣を検知しないといけないため、巣ごとの匹数を管理する必要もある。var nestBirdCount map[int]int
複数鳩がいる巣の数を ans とし、ある巣の匹数が増減したとき、2->1 の変更が起きたらans--、1->2 の変更が起きたらans++とすればいい。

code

D - Gravity

ブロックが消えるのは、横一列揃った時。X 座標ごとの Y 座標のデータを作り、各 X 座標から一つづつ Y 座標を取り出し、全ての X 座標から一つづつ取り出せたら、それらの座標のブロックを全て削除できる。取り出せなかったら、もう削除できるブロックはない。
- X 座標ごとの Y 座標のデータはOrdered Setでもいいし、普通のスライスでもいい。（入力を受け取ってソートしたら、あとは末尾から削除するだけだから。）
- 全ての X 座標に最低一つの Y 座標がない場合は 1 列も削除できないことに注意。
ブロックが消える時刻 T は、同じ回に消えるブロックの中で最も Y 座標が高いもののそれと同じ。

code

E - Hierarchical Majority Vote / DP（ボトムアップ）

取りまとめられた票のデータを木構造として作っていった場合、一番下の階層から順にノード数は $3^n, 3^{n-1}, 3^{n-2}, ...3^{0}$ となる。総ノード数は等比数列の和の公式より $1* (3^{14} - 1) / (3-1) = 2391484$ となり、全列挙も全探索も可能。
木を作り、再帰的に結果を裏返す最小コストを求めればいい。既に目当ての結果ならコスト 0、そうでなく最下層でなければ下層に潜って戻り値をもとに判定、最下層なら既に目当ての結果ならコスト 0、そうでないならコスト 1 とすればいい。（ボトムアップ）

code

390

A - 12435 / Sort

As をコピーしてソートして、sortedを作成。
for i:=0; i<N-1; i++ {}でループして、As[i], As[i+1]をスワップしたスライスがsortedと一致するかチェックする。（ループごとに As のコピーを作成して行う。）
類題：350 C - Sort

code

B - Geometric Sequence / 等比数列

項数 3 の等比数列{a, b, c}について、 $a^{r*0}, a^{r*1}, a^{r*2}$ より、 $a*c = b^2$ が成り立つ。これを index 0 ~ N-1 で検証すればいい。
隣り合う二つの比率を出して比較し続ける方法だと、小数になり精度の問題で WA になる可能性がある。小数を整数で扱う方法を考える。

code

C - Paint to make a rectangle

黒マスのうち、最も上、下、左、右の座標を出し、左上-右下の範囲で黒マスおよび?マスのみしか存在しないことを検証すればいい。
- 座標の列挙は 4 回ループしてそれぞれを見つけてもいいし、min(), max()を使えば 1 回のループで済む。

code

D - Stone XOR / XOR、グループ分け、DFS（全探索）

XOR の性質は以下の様なものくらいしかない。これらを活用して複数のパターンを同一視するなどはできないため、全探索を考える。

fmt.Println(a^b^c == c^b^a) // true. 可換。順番を入れ替えても結果が変わらない。
fmt.Println(a^0 == a)       // true. aと0のxorを取るとaになる。
fmt.Println(a^b^c^a == b^c) // true. aの逆元はaであり、同じ数字でxorをとると0になる。

この問題は、As を N 個以下の（区別されない）グループに分け、グループ内の和同士で XOR を取る場合の答えのパターン数を出すということ。
- このようなグループ分けのパターン数は ベル数 と呼ばれる。（ベル数一覧）。
- 12 個の要素から 12 個以下の任意の数にグループ分けするパターンは 4213597 個であるため、全探索が可能である。
複雑な全探索なので再帰で書く。 ある要素は、すでにあるグループのいずれかに追加するか、新しいグループを作ってそこに入れるか。index 0~N-1 までそのような操作を再帰的に行い、index N に到達したらグループ分けのパターンをグローバル変数に追加して return。詳細は実装参照。
- 今回はグループ内の総和だけ記録更新すれば済むのでそうしている。

code

E - Vitamin Balance / ナップサック問題、DP（テーブル）、二分探索

問題の簡単なバージョンを考える。「カロリー X 以下になるように食べ物を食べた時の、ビタミン 1 の摂取量の最大は？」=> ナップサック問題。
- var dp1 [][]int // dp[i][j] i番目(1-indexed)までの食べ物を処理した時に、丁度jカロリーで得られる最大のビタミン1の最大摂取量
各ビタミンについて DP で上記の問題を解くと、dp[N][0~X]に、最後までの食べ物を見て決めた時に、j カロリーでビタミン V が最大どれだけ摂取できるかわかる。
- 各食べ物は１種類しかビタミンを含まないので、各 DP で重複して食べ物を選んでいることはない。
ans は、a+b+c <= Xとなるように a, b, c を選び、min(dp1[N][a], dp2[N][b], dp[N][c])が最大になった時のその値。
- その場合、dp1[N][a] >= ans && dp2[N][b] >= ans && dp3[N][c] >= ansを満たしていることにもなる。
最小値の最大化については、二分探索で解けることが多いらしい。
ans（候補）が大きくなっていった場合、単調に変化するものは何か？
- dp1[N][a], dp2[N][b], dp3[N][c] >= ansである必要がある為、必然的に総カロリーが増える。（摂取ビタミンの下限が上がる。摂取ビタミンを増やすには、カロリーも増やす必要がある。）
- 逆に言えば ans が小さくなるほどX <= 総カロリーが true になりやすいという単調増加性があるので、DescIntSearch()が使える。
- 二分探索のコールバックの中で、各dp[N][0~X]から、値（摂取ビタミン）が ans 以上になる最小の添字（カロリー）を探す。（ループでもいいし更に二分探索でもいい。）
  - 最小のカロリーを選択するのが、X <= 総カロリーを目指す上で最適な選択。
  - そしてreturn calorie1 + calorie2 + calorie3 <= Xする。

code

389

B - tcaF

サンプル 2 より、N = 20 で X が 2432902008176640000（19 桁）になる。よって N >= 21 で X の上限（19 桁）を超えることがわかる。なので、N=1~20 を全探索すればいい。

code

C - Snake Queue / 累積和 or Deque + 遅延評価

累積和

蛇の頭の座標は、それ以前の蛇の長さの総和になる。蛇の長さを累積和に記録し、何番目の蛇が先頭かを記録すれば、累積和の差で目当ての座標が求められる。

// k番目をidxにするため-1. 累積和配列は先頭の0の分長いので+1. idx kの蛇の座標はidx k-1の累積話に等しいので-1（左記と相殺）.
ans := prefsum[startIdx+(k-1)] - prefSum[startIdx]

Deque + 遅延評価

Dequeは、先頭/末尾の削除、追加、インデックスでの要素アクセス全てを O(1)で行えるデータ構造。詳細は実装を参照。
deque.PushBack()で蛇の長さの累積和を記録していく。（通常の累積和とは違い、都合により 0 始まりにはならないことに注意。）
蛇が抜けるたびにdeque.PopFront()で削除し、これまでに抜けた蛇の長さの和をその値で上書きする。（遅延評価用の値。）
クエリ 3 ではdeque.At(k-1)でインデックスアクセスし、遅延評価用の値を引けば答えになる。

code

D - Squares in Circle / 座標平面（円）、二分探索

円の対称性を利用し、第一象限だけ考えて 4 倍できないか考える。
小数は扱いづらいので、等倍にして無くす。
ツールで作図する。
image
第一象限について、右上の座標までの距離が半径 R 以下なら円に含まれることがわかる。
- maxY, maxX が R-1 であることが分かる。
- 各 Y に対して、ギリギリの X を二分探索 できそう。DescIntSearch(R-1, 1)
- Y を上から試し、minX を直前のギリギリの X で更新すれば範囲が狭まり効率化する。範囲が広いのは最初の二分探索のみなので、 $O(\log R)$ になる。
「座標を 2 で等倍していること」、「中心のブロックを最後に足すこと」、「R=2 // 1*2の時は上記とは別に処理した方がいいこと」に注意する。

code

388

C - Various Kagamimochi

餅ごとに二分探索して、下に置いて鏡餅にできる組み合わせの数を求めて足し上げる。

code

D - Coming of Age Celebration / imos 法

N 人の所持石をそれぞれ求める必要があるので、N のループは必要。つまり制約より、前の人からいくつ石をもらうのか、後ろの何人にを渡すのかを高速に求める必要がある。
前から処理し、後ろのデータを更新していけば、各人のイテレートについて前の何人から石をもらうのかは考えなくていい。後ろの何人に石を渡すのかの判定と、石を渡した後のデータ更新を高速化できればいい。
- 前者は簡単。min(所持数, 後ろの人数)
「配列の部分区間の、等しい更新処理」を高速に行う手法として、imos 法が存在する。range update of difference array、差分配列への区間更新とも言う。
- 差分配列（index iまで累積和を取ることで、index iの値を求められる配列）を事前に作成しておく。
- [index i, j]の区間の値に+xする更新をしたいとして、差分配列の index iに+xし、index j+1に-xする。こうすると累積和で値を復元する際に、適切な値が復元される。
- つまり計算量がO(k) // k: 更新区間の長さから、O(2)になる。下準備（差分配列の作成）と値の復元（累積和の取得）にそれぞれO(n)かかるが、何度も区間更新を行う場合大幅に有利。

遅延評価＋Ordered Multi Setで解く方法をずっと考えていたが、tree set では二分探索ができるが、条件に合致するノードの数は高速に求められない。（言語やライブラリによらない。）終端までイテレーターを動かして列挙する方法しか無理。

code

E - Simultaneous Kagamimochi / 二分探索

『K 個の鏡餅を作るとき、先頭 K 個と末尾 K 個の餅を使うとしてかまいません（上に乗せられている餅が先頭 K 個と異なる場合、先頭 K 個の餅が上になるように入れ替えることができます。末尾 K 個も同様です）。』
K が小さいほど K 個の鏡餅は成立しやすく、一定以上大きくなると成立しなくなる。K を 0~N/2 で二分探索し、K 回ループして全てで 1:2 以上の比率が成立するか判定すればいい。
- $O(N/2 * \log N/2)$

code

387

A - Happy New Year 2025

愚直。答えは最大でも 8 桁にしかならないので、オーバーフローはしない。
- $(2 * 10^3 + 2 * 10^3)^2 = (4 * 10^3)^2 = 16 * 10^6$

code

C - Snake Numbers / 整数問題（いい数の個数）、桁 DP（メモ化再帰）

L 以上 R 以下の条件を満たす整数の個数を求めたいなら、「引数以下の、条件を満たす整数の個数を返す関数」を実装し、f(R) - f(L-1)すればいい。
条件を満たす整数の個数を求めたい場合、桁 DP（メモ化再帰） が使える。
- 何を再帰的に数えればいいのか考える。（テーブルをイメージするのは違う。）
- |R|桁目まで確定した R 以下の数について、１を返す。|R|-1 桁目まで確定した R 以下の数について、再帰呼び出しの戻り値の合計を返す。...。これをするための再帰関数を実装する。
- 桁 DP を実現するための再帰関数では、pos（left indexed の桁数）、strict（上限を気にして次の桁を列挙する必要があるか）を最低限受け取る ことになる。後は問題に応じた保持すべき状態を受け取る。
  - strict == 1 になるのは、現在埋まっている桁が全て上限の数のそれと一致している時。
  - 今回は追加で、firstNum int // 最初に登場したゼロでは無い数字 || ゼロも受け取る。
- 途中の計算結果をメモ化し、条件を満たす整数を全列挙するまで再帰呼び出しをする必要をなくす。メモは多重スライスに格納してもいいし、状態からキーを生成してマップに格納してもいい。
  - 前者はスライスの初期化が面倒。また前者の場合、メモ用の多重スライスのインデックスで状態を表現できるよう、bool の状態（strict など）も int で管理する。
- 桁 DP の計算量は、O(取りうる状態の数)。
  - 今回の場合： $O(pos * firstNum * strict) = O(18 * 9 * 2) = O(18^2)$

code

D - Snaky Walk / 多始点 BFS

最短経路を求める問題なのでBFS。
- 縦移動の後は横移動しかできない（逆も然り）ので、キューアイテムに最後どちらで移動したかを記録する。
- 隣接をとるときに、最後どちらで移動したかで上下を取るか左右を取るかスイッチする。
- 訪問済みノードについて、縦移動で訪問済みでも横移動なら再訪する価値がある。なので、boolean ではなく int で記録する。（未、縦、横、両方。）
縦始まり、横始まりで 2 回 BFS をしてもいいが、最初から縦始まりと横始まりをキューに積んでおいて多始点 BFSとしてやると効率的。
- BFS の最大計算量はノード数。各ノードに縦と横移動で 2 回訪問する可能性があるので、今回は O(200 万)。
- BFS を 2 回やる方法でも O(400 万)なので十分間に合う。
BFS で visited を記録するのは、キューにノードを積んだ直後！ノードを取り出した後ではない！
- 後者のタイミングだと記録前の訪問済みノードがキューに積まれてしまい非効率。
類題：351 D - Grid and Magnet

code

386

B - Calculator / ランレングス圧縮

0 が K 個連続するときに、コストを+ 2/K + 2%Kしたいので、ランレングス圧縮が使える。

code

C - Operate 1

操作 1 は|S|-|T| = 0の時、操作 2 は |S|-|T| = 1の時、操作 3 は |S|-|T| = -1の時に試す価値がある。長さの差分がそれ以外の時は一致させることは不可能。あとはそれぞれの場合を処理。
- インデックスのズレを記録しながら、長さの短い方を基準にイテレート。
|S|-|T| = 1、|S|-|T| = -1のケースは、値を反転すれば同一のケースとして見做せてコード量が減らせる。
類題：358 D - Souvenirs、376 C - Prepare Another Box

code

D - Diagonal Separation / グリッド（応用）

制約よりグリッドの全探索は無理で、M でループすることが分かる。
左上が黒で、右下が白になるように塗り分けられるかどうかということ。つまり、任意のマスが黒で確定している時、それより左上には白は存在してはいけない。逆も然り。
グリッドを規則的に塗ることを考えるので、入力値（確定マス）ついて、行や列の順に処理した方がいいかどうか検討する。
入力値をソートして下の行から処理し、最も右にある黒の W を記録、更新。それより左にある白が出現したらNoで終了。
- ただし、入力値が白マス、黒マスの順になっていてタイミングの問題で矛盾を検出できないことがあるので、同じ行なら黒を優先するようソートする。

code

コンテスト中の反省
- 行ごとに最も右の黒（左の白）を記録し、列ごとに最も下の黒（上の白）を記録し、各確定マスが矛盾してないかを調べる方針を最初とった。
  - この方針だと、確定黒マスで挟まれたマスも黒マスで確定することから、ある確定マスの処理中にそのマスと同一行、同一列以外の記録スライスも更新しなければいけないことがある。
  - このようなデータの更新は、いかなるデータ構造（Slice, Map, Ordered Set, Heap, etc...）を持ってしても効率化不可能。方針自体が間違っていることを認識すべき。
- 二進数でマスの状態を管理する方法を少し考えたが、白黒空で三種類の状態があるのでそぐわないしトリッキーすぎる。もっと早く考えを切るべき。

E - Maximize XOR / XOR、組み合わせ

実は $\binom{N}{K}$ が最大になる K は N/2 である（証明は省略）。
$\binom{N}{K} <= 10^6$ より、実は $min(K, N-K)$ の最大値は 11 である。
- ある N に対して $min(K, N-K)$ は 1 ~ N/2である。
- 1 から十分な大きさ（ex, 100）までの N について、 $1 <= K <= N/2$ の範囲で $\binom{N}{K} <= 10^6$ を満たす K を二分探索して maxK を更新すると、 $\binom{22}{11} = 705432$ の時の 11 であることが分かる。
$min(K, N-K)$ が十分に小さいので、全探索できる。X 重ループなのでDFSで書く。
- $K < N-K$ なら組み合わせの XOR をとり maxAns を更新。
- $N-K < K$ なら予め総 XOR をとっておき、組み合わせの XOR を総 XOR から打ち消し、maxAns を更新。

code

385

B - Santa Claus 1

愚直
grid（二重スライス）に h, w の座標でアクセスする時、grid[h-1][w-1]としてインデックスをマイナス 1 するのを忘れない！

code

C - Illuminate Buildings / 等差数列

方針がすぐ思いつかない時は、問題の簡単な部分問題を考える。
- 公差 1 の等差数列の最長を求めるには？=> Hi~Hn をループすればいい。
- 公差 2 の等差数列の最長を求めるには？=> Hi~Hn を 1 個飛ばしでループすればいい。index0 始まりと index1 始まりの 2 回やる。（交差 N も同様）
計算量：
- $O(\sum_{dist=1}^{N-1} N/dist * dist) \simeq O(N^2)$
- 公差 dist に対して、N/dist の要素をチェックするループを、0~dist-1 インデックス始まりでやる必要がある。結局これは N^2 になる。
最長の等差数列を記録する方法：
- map[height]countではなく、現在続いている等差数列の長さと、今までの最長を保持すれば良いだけ。
map は遅いので、複数使っているなら数を減らせないか考える。map ではなくてスライスで済まないか考える。スライスではなくて特定の値の保持で済まないか考える。

code

D - Santa Claus 2 / 二分探索、Ordered Set

家の、x 座標ごとの y 座標リスト、y 座標ごとの x 座標リストを持っておけば、サンタの垂直な移動、水平な移動についてそれぞれのデータから二分探索によってヒットする家（の数）を見つけることができる。
- from 以上の二分探索、to より大きいの二分探索を行えばいい。二つの線分や区間の重なりを見つけることに等しい。
問題は、家を重複してカウントしてはいけないこと。
- var housXYMap, housYXMap map[int][]intで家を、var visited map[[2]int]boolで訪問済みを管理するシンプルな方法だと、二分探索で見つけた区間の要素を列挙し、訪問済みマップに照会、記録するコストが高すぎる。
- var housXYMap, housYXMap map[int][]intで家を管理し、訪問済みの座標を消す場合、垂直の移動で housXYMap から見つけた家を、housYXMap からも消すコストが高すぎる。
- スライスから特定の要素を消すコストは高い(二分探索できても、要素を消した後の再構築が O(N)かかる)
家の、x 座標ごとの y 座標リスト、y 座標ごとの x 座標リストにOrdered Setを使えば、要素の発見や消去を高速に行える。（どちらも $O(\log N)$ ）
- Ordered Set は平衡二分木（なんらかの方法で木の高さを均一に保つように制御する二分木）で実装することができる。
- 構造よりノードを辿ることで二分探索ができるため、要素の発見、削除、追加が全て $O(\log N)$ で行える。
- c++のstd::setがこれ。（std::multiSetという要素の重複を許すバージョンもある。）

code

コンテスト中の反省
- グリッドの座標と、グリッドのスライスのインデックスは 1 ズレている！
- スライスの初期化時に、レングスを 0 にするのを忘れない！
- オーバーフローが心配になったら、制約からちゃんとマックスの桁数を確認する。
  - go の int64 は、2^63 - 1、10^18まで扱える。

E - Snowflake Tree

どこをユ木の中心にすべきかは自明ではない。
- 例えば childNode の数が最も多いノードを中心にしようと思っても、childNode の数は何処を根にするかで変わる。また、葉から中心に攻めていっても、たとえば完全なユ木から一直線に無駄なノードの長い列が生えているような場合を考えると、明らかに最適でないノードが中心と判定される。
全てのノードについて、それを中心とした場合のユ木のサイズを求められないか？
- 予めノードの次数を数えておけば求められそう。1 + 次数 + 次数 * min(隣接ノードの次数) で良さそうだが、実は違う。隣接ノードを切った方が得な場合もあるので、y を隣接ノードの次数のうちどれに決定するかを全て試せばいい。
- 木の辺数は N-1 であり、全ノードの隣接ノードの次数を見ると辺が 2 回ずつ処理されることになる。さらに隣接ノードの次数をソートして、最適な y を見つけるためにループする。よって $O(2 * N + N \log N) = O(N \log N)$ となり間に合う。
  - 長さ N の配列のソートと、任意の連続部分列に区切ったそれら全ての部分列のソートは、どちらも $O(N \log N)$ である。

code

384

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、346 B - Piano

code

E - Takahashi is Slime 2 / 優先度付きキュー（ヒープ）

倒すことのできる範囲にいる最弱のスライムを倒すことが最善なので、隣接マスのスライムの強さを**優先度付きキュー（min ヒープ）**に入れていく。
ヒープから取り出した強さが、現在の強さの X 分の 1 未満だったら現在の強さに加算し、更にその隣接ますのスライムの強さもキューに入れる。
currentStrength/x > strengthを判定するときに、少数を考えなくて良くするためにcurrentStrength > strength*xとするとオーバーフローする。
- if currentStrength%x == 0 { currentStrength/x > strength } else { currentStrength/x >= strength }とする。
- 解放の方針が立ったら、オーバーフローの可能性がないかを確認する癖をつける。

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

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

E - 11/22 Subsequence / 二分探索、累積和

i 番目の文字までの 1 の数、2 の数の累積和を作成する。
各スラッシュに対して、左側の 1 の数、右側の 2 の数を記録する。var slashInfos []{idx, leftOnes, rightTwos}
L 以上 R 以下のスラッシュのslashInfosを二分探索する。
左側の 1 の数に着目する。max はtargetSlashInfos[len(targetSlashInfos)-1].leftOnesで、min は 0。
- この値は、小さくなるほど 11/22 文字列を成立させやすい単調性がある。小さくなるほどスラッシュを左に移動でき、右側の 2 の数が増えるから。
- 二分探索で得た答え*2+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

E - 1D Bucket Tool / Union Find

隣接するマスの色が同じになったら、以降はそれらは一つのグループになり色が同期する。グループの管理なのでUnion Find。
- 厳密には、隣接する"グループ"の色が同じになったらそれらがマージされる。よってグループの色、右端、左端のインデックスを別で管理する必要がある。
  - var colors,ls, rs []int // rootNodeIdx -> color, r_idx, l_idx
  - （マージで吸収されたグループルート i のcolors[i], ls[i], rs[i]は、削除の印をつける更新などをしなくても以降参照されないので問題ない。）
またクエリ 2 で特定の色のカウントを出力する必要があるので、色ごとのカウントも保持しておく。
- var colorsCount map[int]int
クエリでループし、色ごとのカウントを増減させる。隣り合うグループとのマージ判定、マージを行い、それに伴うグループの色、右端、左端のインデックスを更新する。

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

E - Sum of All Substrings / シグマ、巨大な数

明らかに INT_MAX を超える数が出てくるが、多倍長整数を使うと TLE する。
- 桁数 N の A と B を演算するとして、加算減算は $O(N)$ 、乗算徐算は $O(N^2)$ 　かかる。
扱う数字を INT_MAX 以下に抑える方法として、答えの 1~最終桁を独立して求めて、最後に出力して繋げる方法がある。
- 筆算の様に考える。
- 一桁目の数字は、足し算に使われる数の 1 桁目の和による。2 桁目の数字は、左記の和の繰り上げ分と、足し算に使われる数の二桁目の和による。...。

足し算に使われる数の k 桁目の和を高速に求められればいい。以下の例から、 N 桁目の数字の和から順に 1 桁目の数字の和を求めていける。var digitSum []int // N桁目の数の和, N-1桁目の数の和, ... 1桁目の数の和
- $1桁目の数字の和 = 3*1 + 7*2 + 9*3$
- $2桁目の数字の和 = 3*1 + 7*2$
- $3桁目の数字の和 = 3*1$
あとはdigitSumを反転してループして、繰り上げ分を上の桁に渡していけばいい。
- digitSum[i+1] += digitSum[i] / 10; digitSum[i] %= 10;
この時、最終的な桁数は N 以上になるので digitSum の length（=最終的な答えの桁数）をどうするのかという問題がある。
- 最も大きくなるdigitSum[i]は、1 桁目の和のdigitSum[0]
  - $10 * (1 + N)*N/2 \simeq 10*N^2 \simeq 10^{11}$
    - 簡素化のために最大の数字として 9 ではなく 10 を使用、N の最大値に 10^5 を使用。
    - これからdigitSum[i]がオーバーフローしないことも分かる。
  - これが N 個あるとして、 $10^{11} * 10^5 = 10^{16} = 17桁$ 。つまり、N 桁目から 17 回程度繰り上がるだけ。十分な数の 0 をバッファとして digitSum に append しておく。最後に余分なゼロはトリムする。

code

378

A - Pairing

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

code

変なやり方で解いてた：

B - Garbage Collection

割り算、余り、場合分け

code

C - Repeating

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

code

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

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

code

E - Mod Sigma Problem / シグマ、累積和、フェンウィック木

区間の合計を求めるのには、累積和が使える。以下のように式変形できる。
- $\sum_{l=0}^{N} \sum_{r=l}^{N} psum[r] - psum[l-1] \mod M$
  - N は+1 して累積和の長さにしておく。
- 累積和は予め $\mod M$ に変換しておいても問題ないのでしておく。
- とりあえず全ての psum[i]に対して、左になる回数（=N-i-1）だけansから引き、右になる回数（=i）だけansに足す。
$psum[r] - psum[l-1] \mod M$ は、 $psum[r] >= psum[l-1]$ ならばそのままの値だが、そうでないなら M を足した値になる。
各psum[i]に対して、転倒数（数列で自身の左側（右側）にあって自身より大きい数（小さい数））を求めればいい。
- 転倒数は フェンウィック木 で求められる。
- 0~あり得る最大の数字の数列のフェンウィック木を作り、psum[i]を前から見て、ftree.Update(psum[i], 1)する。
- ftree.Query(psum[i]+1, maxNum)で自身より左にあり、自身より大きい要素の合計数が分かる。
最後にans += 総転倒数*Mする。

code

377

A - Rearranging ABC

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

code

C - Avoid Knight Attack

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

code

D - Many Segments 2

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

code

376

B - Hands on Ring (Easy) / 円環

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

code

C - Prepare Another Box

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

code

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

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

code

E - Max × Sum / ヒープ

A の最大値という概念が出てくるので、As をソートすると良さそう。
- この時type AB struct {int, int}のペアを作った後に ABs を A の値で昇順ソートすると、maxA がある値（ABs[i].A）であるときにABs[i]以降のABs[j].A, Bが使えないことがわかる。maxA == ABs[i].Aの前提が崩れるため。
maxA を固定し、順に試すことを考える。
- 使える B の中で、K 個の合計が最小となる B の組み合わせのを考えたい。使える B が A を試すごとに増えていき、その中の最小の K 個の合計を出したい。これは最大ヒープを使えば実現できる。
- A を昇順に試し、使える B をヒープに足していく。ヒープのサイズが K 以下なら continue、K より大きいなら最も大きな B をPopI()で捨てる。ヒープ内の合計を記録しておき、PushI(), PopI()の時に更新する。

code

375

B - Traveling Takahashi Problem

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

code

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

正方形グリッドの回転
正方形グリッドの周のレイヤー
- 今回の問題では、一番外側のレイヤーのセルは一回 90° 回転、二番目のレイヤーのセルは二回 90° 回転、...。ということになる。
問題のタイトルがヒント

code

補足

※ h, w は 0-indexed

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

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

D - ABA / メモ化

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

code

374

A - Takahashi san 2

strings.HasSuffix()

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

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

B - 3^A / 整数問題（いい数を見つける）、N 進数 or 貪欲法

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

E - K-th Largest Connected Components / Union Find、ヒープ

連結成分を高速に判定する必要があるので、Union Findを使う。また、各連結成分に属する頂点番号を大きい順に保持したい。
ソートを保ったまま高速に要素の追加ができるデータ構造としてOredered Setやヒープがある。
- ここで、制約より K の上限が 10 でありとても小さいことに注目する。つまり連結成分ごとのノードは、大きいものから順に 10 個までしか保持しなくていい。
- 要素の削除が $O(log N)$ かかる Set より、 $O(1)$ で済むヒープが適切。
実装
- Union Find、ルートごとの頂点の最小ヒープ（頂点を捨てる時は最も小さい頂点番号のものを捨てたいため）var rootNodes []IntHeapを作る。
- クエリ 1 では頂点同士をUnion()する。ルートでは無くなる頂点が発生するので、そちらのヒープから生き残ったルートのヒープに要素を移動させる。その後ヒープの要素が 10 以下になるまで要素を捨てる。
- クエリ 2 では指定頂点のルートを判定し、そちらのヒープから K 個目に大きい頂点番号が出るまで順にPopI()する。（最小ヒープのためやりにくいが頑張ればできる。）その後入れ直す。
- $O(Q)$ // Union Find の操作やヒープの操作は軽いので雑に無視。

code

371

A - Jiro

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

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

E - I Hate Sigma Problems / シグマ、区間問題

そのままの式では TLE になるため、別の方向からのシグマの式にすることを考える。
登場するすべての数字について、それが登場する区間の個数を数えられればそれが答えになる。（結果的にすべての区間について、登場する）
- $\sum_{x} countSec(x)$
- N 個の要素の部分区間の取り方は、 $_{N+1} C_2$
  - 先頭の前と末尾の後ろと各要素の間に、二つ仕切りを置くことに等しい。
「ある数字 x が1 個以上登場する区間」は数えるのが困難なため、余事象の x が 1 個も登場しない区間を考える。
var numIndexes map[int][]intを作成しておけば、index[i]+1 ~ index[i+1]-1の区間が x が全く登場しない区間ということになる。
- 最初のインデックスの手前、最後のインデックスの奥のセクションを考えたいので、prevIdx を-1 で初期化し、あらかじめ indexes に N を append しておくと上手くいく。

累積和や差分配列ではこの手の問題は解けない。
- 『一般に「累積和」「差分配列」でうまくいくのは、“区間に対する和(または差)が線形的に分割できる”タイプの量です。たとえば「区間の要素の総和」など。「異なる値の種類数」は「単にどこかの部分区間を足して、どこかの部分区間を引けば答えが出る」という形にはなりません。』

code

370

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（ノードカウント）

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

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 演算は、割られる数が負の時に結果が違うので注意！ 参照
[類題]: 384 D - Repeated Sequence

code

366

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

E - Xor Sigma Problem / XOR

ある区間の排他的論理和を求めるためには、累積 XORが累積和と同様に使える。（区間の累積和を求めるときには、二つの値でさらに累積和をとる。）
区間の列挙は $O(N^2)$ かかるので不可能。XOR の問題は、桁ごとに分けると良いことが多い。 XOR 演算は桁ごとに独立なので。また、制約より桁の上限数もわかる。
i 桁目について、i 桁目のビットが立っている値と立っていない値の XOR をとると、答えの i 桁目は 1 になる。
累積 XOR から二つの値を選ぶことは区間（(l, r]）を選ぶことに等しい。桁数でループし、i 桁目が立っている値の数を数える。poppedCnt * N-poppedCntが XOR で i 桁目のビットが立つ区間の数であり、その分だけ総和に1<<2を足せばいい。
最後に、問題の制約上長さ 1 の区間( $区間内のXOR=A_i$ )が許されていないため、 $A_1$ ~ $A_N$ を総和から引く。
- 一つ前のステップで、これらの値の二進数表現の立っているビットが、総和に加算されている。

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

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 で確定。
- 始点から隣接するノードのコストを記録する。
- コストが記録されており確定されていないもののうち、最小のコストのノードのコストを確定させる。
- そしてそのノードの隣接ノードのコストを調べ、記録する。（すでに記録済みのノードに、より少ないコストで到達できる場合は上書きする。）
- 二つ前の手順に戻る。全てのノード（あるいはゴールとなるノード）のコストが確定するまで繰り返す。
ダイクストラ法は、優先度付きキュー（ヒープ） で実装できる。
- 優先度付きキューとは、優先度の高いものから取り出されるキューである。
- 優先度付きキューは、ヒープというデータ構造で実装できる
- ヒープは、キー順序性を満たす完全二分木である。
類題: D - Super Takahashi Bros.

二分木とは

各ノードが最大で 2 つの子ノードを持つ木構造のことです。この特性から、「二分木」という名前がつけられています。

特徴

ノード（節）:
- 各ノードは 1 つのデータ要素を持ちます。
- 親ノード（Parent）: 自分より上の階層のノード。
- 子ノード（Child）: 自分より下の階層のノード。左の子ノード（Left Child）と右の子ノード（Right Child）があります。
ルート（根）:
- 木構造の最上部に位置するノードです。
- 二分木には 1 つだけルートがあります。
リーフ（葉）ノード:
- 子ノードを持たないノードです。
高さ:
- ルートからリーフノードまでの最長パスの長さ。
  :::

完全二分木とは

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

最も深い階層より浅いレベルのノードは、全て埋まっている。
最も深い階層のノードが左から順番に埋まっている。

ヒープとは

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

キー順序性を満たす:
- 各ノードの値は、その子ノード、左にあるノードの値よりも大きいまたは小さい。
  - 最大ヒープ: 親ノードの値が子ノードの値以上、兄弟ノード（同じ親の子ノード）において左のノードが右のノードの値以上。
  - 最小ヒープ: 親ノードの値が子ノードの値以下、兄弟ノード（同じ親の子ノード）において左のノードが右のノードの値以下。
  - 同じ階層の親が違う兄弟の比較については、左から右へ値が単調増加/減少する保証はない。
形状が完全二分木である
要素の Push 時、Pop 時の両方でソートが行われるため、両方の計算量は $O(N*logN)$ である。

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

code

361

A - Insert

オリジナルを K 番目まで copy した配列に、X を append。そしてオリジナルの K+1 番目以降を apennd
copy(dest, src)するときに、dest はコピーしたい範囲と同様の length, size を両方持つこと

code

B - Intersection of Cuboids

二つの立方体が重なっているのは、x 軸、y 軸、z 軸の範囲がいずれも重なっている時。
any 軸の範囲が重なっている時はどう言う時か？ある事象のための条件を考える時、考えづらかったらその逆のための条件を考える。
「範囲[a, b]と[c, d]が、長さが 1 以上の共通部分を持たないとき」はどんな条件か？
- d <= a || b <= cの時である。（一方の上限が他方の下限以下である時。）
- その条件の否定が、求めたい条件である。

code

C - Make Them Narrow

(B の最大値) − (B の最小値) としてありうる最小値を考えたいので、消して意味のある要素は、ソート後の配列の両端から、合計 N 個。
前から x 個、後ろから y 個消すとする。そのパターンは、K 個の直列に並んだ石の、どこに仕切りに置くのか（0 個になる側が出ても OK）と同じで、K+1 パターン。
K は $2*10^5$ なので、全探索可能。

code

D - Go Stone Puzzle / BFS（応用）

$2\leqN\leq14$ と言う N の小ささに注目する。盤面のパターンが列挙できるのでは？現在のパターンから行ける次のパターンは限られているので、DFS や BFS が使えるのでは？
最短手数を求める問題なので、BFS。
実際の盤面のパターンは、最悪で $2^{14} * 15 = 16384$ 。（15 は空の連続 2 マスをどこに置くのか。）
BFS の計算量は、16384 より悪くならない。同じ盤面を二回経由する意味はないので、他のすべての盤面を経由してゴールに辿り着く場合に 16384 になる。（実際にそのようなパターンはあり得ないため、実際の最悪はもっと少ないが、その証明や計算は難しいためしなくていい。）

code

360

B - Vertical Reading / 全探索

$1\leqc\leqw<∣S∣$ 、 $1\leq∣T∣\leq∣S∣\leq100$ より、c と w の組み合わせは $100^2$ を超えない。絶対に全探索でやる。スマートな方法とか考え始めない。
w（チャンクサイズ）でループ。スライスをチャンクに分割して、可能な縦読みを全て試す。
または、w と c を二重ループで全探索し、その場合の文字列を計算し、それが T と一致するか判定。

code

C - Move It / 優先度付きキュー（ヒープ）

箱に入っている荷物を、軽さによる 優先度付きキュー（ヒープ） で管理する。
map[箱]優先度付きキューで全体を管理。マップでループして、すべてのキューから要素 1 になるまで取り出しを行い、コストを足していく。

code

D - Ghost Ants / 二分探索（応用）

少し面倒だが、それでも図を書く
- 最初 start - end の区間で表現する方法を選んでしまったが、始点のみを管理する方法が解放としてもシンプルになりよかった。
- 考慮する要素が少なくなるよう、なるべくシンプルな方法で表現すると良いかも？
交差することができるのは、forward の蟻と backward の蟻。かつ距離が 2T より多く離れていない場合。
forward、backward の蟻をソートし、前者でループ。自身より前にいる backward の蟻を 二分探索 で見つけ、そこからさらに一定の距離以上離れていない蟻を二分探索で見つける。

二分探索 tips

スライスから「ある条件に合う要素」を二分探索した場合

=> ある条件に合う要素の数は、スライスの長さ引く結果のインデックスになる。

sl := []int{1, 2, 3, 4, 5}

// 4以上の要素の数が知りたいとする。
idx := sort.Search(len(sl), func (i int) bool {
  return sl[i] >= 4
})


// 最後の要素だけヒットしたとする。その場合該当する要素数は1。len(sl) - idx (=len(sl)-1)も1になる。
// 最後から二つの要素だけヒットしたとしても、同様に考えて引き算の結果が要素数と一致する。
ans := len(sl) - idx

fmt.Printf("answer is %d", ans)

スライスから「ある条件に合わない要素」を二分探索した場合

条件そのものを使うと、スライスが単調増加性を満たさない場合に上記の探索をすることになる。

=> ある条件に合う要素の数は、結果のインデックスと同じになる。

sl := []int{1, 2, 3, 4, 5}

// 4以下の要素の数が知りたいとする。
// **4以下という条件では、対象のスライスは単調増加性を満たさないので、4より大きいという条件で二分探索することになる。**
idx := sort.Search(len(sl), func (i int) bool {
  return sl[i] > 4
})

// 答えがidxと同じになるのは、以下の直感的な式を変形すると結局 ans := idxになるから。
// numOfNotMatched := len(sl) - idx
// ans := len(sl) - notMatched
ans := idx

fmt.Printf("answer is %d", ans)

code

359

C - Tile Distance 2 / 座標平面

図を書いて実験する。手書きが難しいものは、スクショしてそれをペイントする。
タイルから別のタイルに行く時にコストがかかる。タイルのどちら側にいて、別のタイルのどちら側に行くかは関係しない。
- よって、座標を、タイルの左側に統一する。（元々左側ならそれを、右側ならそのタイルの左側の座標に変換する。）
- 同一と見做せるものは、どちらかに統合して考える。パターン数や、問題の複雑さを減らせる。
図を書くとわかるが、始点から波紋状にコストが増えていくことがわかる。
そして、 yDelta >= xDeltaの範囲ではコストがyDeltaであり、そうではない範囲ではコストがxDelta+yDelta/2であることが分かる。

図

code

D - Avoid K Palindrome / DP（テーブル）、DFS、回文

ある?がAになれるかBになれるか、その両方になれるのか、（回文が成立してしまい）どちらにもなれないのかは、そのインデックス i の直前の i-1 ~ i-K 文字目の状態に依存すする。 このことから、DPが使えそう。
DP テーブルの設計
- 列：何文字目（index i）を考えているか
- 行：i-1 ~ i-K 文字目の文字列
- セル：その状況に到達しうるパターン数
  - セルの値はどうする？最終的に求めたいのは、良い文字列の合計数。int になりそう。その状況に到達しうるパターン数にすれば、最終列の合計を取れば答えになる。最終列を見れば知りたい答えがわかるように、セルの値を設計する。
  - 列 i から列 i+1 に遷移するときに、セルの値を引き継いで足せばいい。複数のセルからあるセルに遷移した場合、その状態に到達しうるパターン数の合計になる。
- var table []map[string]int
最初の index 0 ~ K-1 文字目のパターンはどう列挙すればいい？（DP テーブルの実質の 1 列目）
- その文字列の中に含まれる?を A、B どちらかにするかで枝分かれする構造なので、DFSで列挙できる。（再帰の前のスライスのコピーを忘れずに。）
あとは列挙した 0 ~ K-1 文字目のパターンをテーブルに挿入し、その列の参照から始まるループを回し、ループ内で次の行を埋めればいい。（N-1 列目を参照するループで終わり。）
類題：312 D - Count Bracket Sequences

code

358

B - Ticket Counter

順番待ちの列が出てくるからと言って、queue を使うとは限らない。
待ち時間は、その直前の人が終わった時間プラス処理時間 A になる。つまり、直近の人が終わった時間を記録しながら前から順に処理していけばいい。

code

C - Popcorn / 全探索（順列）、二進数（論理和）、貪欲法

売り場の数 N が 10 なので、売り場の順列パターン数は 10!(=約 360 万)なので、全探索可能。
順列に対して、貪欲に上からできる限りポップコーンの種類を買っていき、何個の売り場を回ったらコンプリート可能か見ていけばいい。（貪欲法）
どの種類のポップコーンを売っているかの情報は、二進数で表現できる。複数の売り場の二進数の論理和を取れば、集められるポップコーンの種類数の和が求められる。

code

D - Souvenirs

二つのスライスをソートして、両方を最初から見ていけばいい。
各 B にどの A を当てがうかを調べたいので、B でループする。対応するインデックスの A をみて、マッチすればそれを当てがう。そうでなければマッチするものが見つかるまでループ内部でループし、A のインデックスをどれだけ進めたのかを記録する。
インデックスがスライスのレングス内に収まっているかチェックするのを忘れない！
類題：376 Prepare Another Box

code

357

B - Uppercase and Lowercase

愚直
小文字判定：'a' <= rune(S) && rune(S) <= 'z'
大文字判定：'A' <= rune(S) && rune(S) <= 'Z'
strings.ToUpper(S), strings.ToLower(S)

code

C - Sierpinski carpet / グリッド(応用)、再帰

可能ならグリッドを 9 つの部分グリッドに分け、真ん中を白で塗りつぶす。それ以外を同様の処理に回す。ということのため、再帰関数を実装する。
指定サイズの黒で塗りつぶされた string pointer のグリッドを用意し、再帰関数に渡す。
go 1.22 より前だと、for 行で宣言される変数は最初のイテレートでメモリが確保され、以降は値のみ更新される仕様であることに注意する。
- ref
ポインタ変数の「値」を変更したいときは、*ptrVariable = "foo"のようにする。

code

D - 88888888 / 等比数列、合同式

等比数列

$V_N$ は、初項 $N$ 、公差 $10^K (KはNの桁数)$ の等比数列であることが分かる。
- $V_5 = 555 = 5*10^0 + 5*10^1 + 5*10^2$
- $V_{10} = 10101010101010101010 = 10*(10^2)^0 + 10*(10^2)^1 + ... 10*(10^2)^9$
等比数列の和 $S$ は、初項を $a$ 、公差を $r$ 、項数を $n$ とすると以下になる。( $S*r - S$ の式を立てることで求まる)
- $S = (a*r^n - a) / (r - 1) = a(r^n -1) / (r-1)$

合同式

合同式において、足し算、引き算、掛け算における任意の項を合同な数に置き換えても、結果は変わらない。
(乗数計算においても、基数を合同な数に置き換えて良い。指数はダメ。)

よって以下が成り立つ。

var isSame bool
isSame = (A+B)%M == (A%M+B%M)%M // true
isSame = (A-B)%M == (A%M-B%M)%M // true
isSame = (A*B)%M == (A%M*B%M)%M // true

// (A+B)%M == (A%M+B%M) のようなものは成り立たないことに注意。（「合同式」ではなく「等式」になっているので）

逆元という概念があり、 $a$ の逆元は $a^{-1}$ と表記される（ $1/a$ を意味しない）。 $a*a^{-1} \equiv 1 \pmod M$ となる数のことである。
a の逆元は、法 m と a が互いに素（最大公約数が 1）の場合のみ存在する。a の逆元はフェルマーの小定理またはユークリッドの拡張互除法で求められる。
- フェルマーの小定理： $mが素数でGCD(a, m) = 1ならば、a^{m-1} \equiv 1 \pmod m$
  - $a * a^{m-2} \equiv 1 \pmod m$ となるため、 $a^{m-2}$ が a の逆元。
- ユークリッドの拡張互除法: $GCD(a, m) = 1ならば、a*x + m*y = 1となるx, yが求められる$
  - $a*x + m*y \equiv 1 \pmod m$ より、 $a*x \equiv 1 \pmod m$ 。よって x が a の逆元。

code

356

A - Subsegment Reverse

あるスライスの区間[L,R]を別のスライスで置き換えたい場合、以下のようにすればできる。
```
replaced := append(original[:L], change...)
replaced = append(replaced, original[R+1:]...)
```

code

C - Keys / ビット全探索、二進数（論理積）

ややこしそうな問題文は、解釈を間違えないように気をつける。
- 「N 個の鍵の中に正しい K 個の鍵の組み合わせが存在し、その組み合わせの鍵をドアに刺せば（追加で他の鍵を刺していても）開く」ということではない。
- 「N 個の鍵の中にいくつかの正しい鍵が存在し、K 個以上の正しい鍵をドアに刺せば開く」ということ。 鍵の番号は関係ない。
標準入力の一行に複数の型のデータが入っていて面倒だが、愚直にハンドリングする。
2^N は最大でも 2^15 のため全探索できそう。各番号の鍵が正しいか正しくないかは二進数で表現できるので、ビット全探索する。
各テストについても、どの鍵を使ったかを二進数で表現できる。各番号の鍵が正しいか正しくないかのパターンの二進数との論理積を取ると、使っていてかつ正しい鍵の本数が分かる。
- 正しい鍵を K 本以上使っているならドアが開くべきで、K 本未満ならドアが開かないべき。各テストがこれと矛盾しないかチェックし、テストで矛盾が生じるパターンはありえないパターンとして除外できる。
- 論理積は、int, int64, uint64 などどんな型でも取れる。（同じ型同士で。型変換して揃えても問題ない。）
- 演算子は&：conjunction := A & B

code

D - Masked Popcount / 二進数（数え上げ）

0~N のループは重すぎてできない。二進数は桁ごとの処理にするといいことが多いので、桁ごとの処理のループを作ってやる。
$\sum_{K=0}^{N} popcount(K \& M)$
$\sum_{K=0}^{N} \sum_{j=1}^{60} isBitPop(K \& M, j)$ 　// 制約より、K & M は最大 60 桁。
連続するシグマの位置は入れ書いても良い。二つ目のシグマ以降のループをなくせれば、60 ループで済むようになる。
$\sum_{j=1}^{60} \sum_{K=0}^{N} isBitPop(K \& M, j)$
$isBitPop(K \& M, j) = true$ となり得るのは、M の j 桁目が 1 の場合のみ。
二進数の j 桁目（一番右を一桁目とする）のビットは、^j の周期を持ち、周期の前半が 0 で後半が 1 である。
この性質を利用すると、各桁について以下の式で立っているビットの数え上げができる。
- 0~Nまでの間に何周期存在するか * 周期/2 + 余りが周期/2を超えていればその分
- 1 ではなく 0 始まりであることに注意。

// 二進数を最初から列挙
00000
00001
00010
00011
00100
00101
00110
00111
01386
01001
01010
01011
01100

code

355

A - Who Ate the Cake?

マップ、愚直

code

B - Piano 2

マップ、愚直

code

C - Bingo 2 / ビンゴ

N*N グリッドに 1, 2, ...N と番号を順に埋めていく場合、マス目の値はN*rowIdx+colIdx+1となる。
逆にマス目の値から行と列を知りたい時は、以下のようになる。
- 行：num / N
- 列：num % N
マスが対角線上にあるかどうかを知りたいときは、以下のようになる。
- 左上から右下：rowIdx == colIdx
- 右上から左下：rowIdx + colIdx == N-1

code

D - Intersecting Intervals / 区間、二分探索（応用）or 余事象

解法 1 二分探索

数直線上に区間が並んでいるので、二分探索が使えそう。
区間をソートし、左側の区間から順に、それより右側の区間で始点が現在の区間の終点以前にある区間を探せないか。
- 区間スライスと始点スライスを作り、昇順にソートする（始点が同じなら終点が左の方を優先）
- 区間スライスでループし、始点スライスをstars := starts[1:]で現在の区間を削る。
- starts[i] > currentSeg.rで二分探索し、現在の区間の終点以前にある始点の数を調べる。（二分探索-tips）

解法 2 余事象、重ならない区間の性質

区間の組み合わせの数はN*N-1/2なので、全探索無理。余事象である重ならない区間の数が分かれば、N*N-1/2からその数を引けば答えになる。
A の右端 < B の左端　となる区間 A,B は重ならない。逆も然り。
つまり、ある左端の座標の前に、幾つ右端の座標があるかを数えて足し上げていけばいい。x 座標、種類（右端 or 左端）を持った構造体のスライスを作りソートし、ループすればいい。

code

354

B - AtCoder Janken 2

辞書順ソート

code

C - AtCoder Magics

問題文の言い換え。「コストが増えたなら、攻撃力も増えなければならない」（or 「攻撃力が減るのなら、コストも減らなければならない」）
- 言い換えを思いつくまでは、実装をガチャガチャ試すのは悪手。
- コストの昇順で入力値をソートし、攻撃力の閾値を記録しながらループで有効なカードをチェックしていけばいい。

code

D - AtCoder Wallpaper / 座標平面、面積、包除原理

座標平面 tips

x, y 座標が正になるように、入力値に下駄を履かせる。

今回の場合、+10^9 すれば制約より座標が必ず正になる。
- 今回の場合、座標平面が 4*2 の周期で同じ模様をしているので、x 座標に 4 の倍数、y 座標に 2 の倍数を足しても同じ模様の範囲になる。（4 の倍数判定は、下 2 桁が 4 の倍数かどうか。）

面積を求める時に「右上座標-原点」の面積を出し、包除原理で求めたい範囲を求める。

「任意の座標-原点」の面積を求める関数を実装すればいい。
「(A, B) (C, D)」の面積は、f(C, D) - f(C, B) - (A, C) + f(A, B)

解法

図

4*2 のブロック（黒い部分は全体の 1/2）がいくつ入っているかをみたい。
- ans := x/4 * y/2 * 1/2 * 2
縦方向の余り
- if y%2 == 1: ans += 1 * 1/2 * 2
横方向の余り
- x 方向の周期は４なので、余りは 3 パターン
- 余りが１以上なら周期の最初から１行目を足し、２以上なら最初から２行目を足し、３なら最初から３行目を足せばいい。
- 右上の１行についても、x 方向の周期は４なので、y%2 == 1なら上記のそれぞれの行について足しておく。
go の int の割り算は結果が切り捨てなので、気を付ける！

code

353

B - AtCoder Amusement Park

座っている人数を記録しつつグループ毎にループ。K と同じになるか、越えるか、未満かで分岐。

code

C - Sigma Problem / 合同式、二分探索

式変形を考える。
- $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(A_i, A_j)$
- $(A_1 + A_2) \mod M + (A_1 + A_3) \mod M + (A_2 + A_3) \mod M$ // N=3 の場合
$\mod M$ が分配できるのは、合同式の場合のみ。等式ではできない。
$\mod M$ がなかった場合、 $\sum_{i=1}^{N} A_i * (N-1)$ で答えが求められる。
- $(a + b) \mod M$ とは、a+b が M を超えていれば、引けなくなるまで M を引くということ。
- ソートした As でループし、 $A * (N-1)$ 分総和を増加させる。
- As[idx:]から二分探索で $A + A_j <= M$ になる A の数を調べ、その分だけ M を引く。（制約より、 $A_i + A_j < 2M$ ）

code

D - Another Sigma Problem / シグマ、合同式、累積和

式変形を考える。
- $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(A_i, A_j)$
- $(A_1 * 10^{|A_2|} + A_2) + (A_1 * 10^{|A_3|} + A_3) + (A_2 * 10^{|A_3|} + A_3)$ // N=3 の場合
- $10^{|A_3|} * (A_1 + A_2) + A_3 * 2 + 10^{|A_2|}* (A_1) + A_2 * 1$
- $\sum_{i=1}^{N} 10^{|A_i|} * prefSum[i-1] + A_i * (i-1)$
オーバーフローしないように適切に式に%M をつけておく。誤答ペナルティ勿体無い。

code

352

B - Typing

インデックスのズレを記録しながら見つけたい文字列の方でループし、もう一方の文字列を idx+diff で参照。
相方が見つかるまでループの中でさらにループし、diff をインクリメント。

code

C - Standing On The Shoulders

最後の巨人のみ、A ではなく B の値で総 Height が加算される。B-A の値で昇順ソートし、最後の要素だけ B で加算する。

code

D - Permutation Subsequence / Ordered Set

Ps について、元々の番号を保持したまま数字順にソートする。その後、index0 から K 個ずつの数字を見ていき、最大番号-最小番号を計算し minAns を比較、更新する。
ループ毎に番号が一つ削除、追加される。また、現在の K 個の番号から最大値と最小値を取得する必要がある。これは、Ordered Set で高速に行える。全て O(log N)。

code

E - Clique Connect / クラスカル法

最小全域木とは
- 全域木とは、無向グラフの全ての頂点を含む様な木である。（木は閉路のない、全ての頂点が連結である無向グラフ。）
- 最小全域木とは、辺の重み付き無向グラフにおいて、辺の重みの重みの総和が最も小さくなる全域木である。
最小全域木を求める方法としてクラスカル法が存在する。全ての辺から最も重みの小さい辺を採用していく。ただし閉路が誕生する場合はその辺をスキップする。
- これが成立する理由：もし top K 個の重みの小さい辺以外の辺が採用されたとする。出来上がった全域木に対して、新たにスキップした小さい重みの辺を追加するとする。そうすると閉路ができるわけだが、閉路に含まれる他の辺を削除しても全域木が保たれる。そしてその辺は必ず追加した辺より重いことになる。
- 辺を重みの小さい順にソートして、Union Findを使って連結成分の更新、閉路の判定をすることで実装できる。
- （最後まで辺を処理して UnionFind のルートのカウントが 1 でなければ、全域木は作成できなかったということになる。）
- $O(E * α(E))$
今回の問題では、愚直に全ての辺を追加したのちにクラスカル法を適用すると辺が多すぎるので、減らす工夫を考える。
各操作において、与えられた頂点集合が完全グラフになるように辺を貼るが、その全ては必要ない。それらが連結になるだけでいいので、例えば頂点を順番に繋げる様な辺だけを残せばいい。
- この範囲においてどのように辺を残すかは関係ない。最終結果のコストや全域木が達成できるかに関係ない。
- これにより辺の数の総和が $4*10^5$ に収まるのでクラスカル法が間に合う。

code

351

C - Merge the balls　/ スタック、巨大な数

ボールを列に追加していき、最後に追加したボールを（から）参照する必要があるのでスタックが活用できる。
ボールのサイズは $2^N (N = 2*10^5)$ なので、愚直にサイズを記録するとオーバーフローする。乗数が出てきて、指数が巨大ならオーバーフローを回避することを考える。
もともとあるボールのサイズは 2 の乗数で、合体してできるボールのサイズは $2^x + 2^x = 2(2^{x+1})$ なので、2 の乗数のサイズしか考えなくていい。なので指数のみ記録すればよく、オーバーフローを回避できる。

code

D - Grid and Magnet　/ DFS（グリッド）、連結成分

連結成分とは、グラフにおいて経路で繋がれた頂点の集合である。
今回の問題においては、ある開始頂点から到達できる別の頂点について、自由度は開始頂点以下である。
- 磁石の隣接頂点では身動きできないため自由度１だが、それ以外の点については開始頂点と到達できる範囲が全く同じであるため。
よって、DFSで探索を行うとして、探索済みの頂点は別の DFS の開始頂点とする必要はない。
- 別の連結成分に属する別の開始頂点からの DFS では、過去に探索済みの頂点には必然的に訪れることはない。
- ただし今回の場合、連結成分の境目である磁石の隣接マスのみ再訪の可能性がある。
訪問済みデータを管理する必要がある。（開始頂点の訪問済みスキップ、各 DFS での訪問済み管理。）
- ただし、グリッドが 1000*1000 のため、二つ目の訪問済みデータを毎回初期化していると TLE になる。そこで、一つのデータを使い回すことを考える。
- 連結成分の境目の磁石隣接マスには、各 DFS で再訪しても良いため、工夫が必要。
- var visited [][]intとし、各 DFS で（１以上の）異なる数字を入れたなら、全 DFS を通して訪問/未訪問か、今回の DFS で訪問/未訪問かを識別することができる。

code

GitHubで編集を提案

396

D - Minimum XOR Path / DFS（バックトラック）

E - Min of Restricted Sum / XOR、連結成分分解

395

C - Shortest Duplicate Subarray / 尺取法

D - Pigeon Swap / ポインタ

E - Flip Edge / ダイクストラ法、頂点倍加

394

D - Colorful Bracket Sequence / Stack

E - Palindromic Shortest Path / 回文、BFS

393

E - GCD of Subset / 最大公約数、調和級数

392

D - Doubles / 確率問題、全探索

E - Cables and Servers / Union Find

391

E - Hierarchical Majority Vote / DP（ボトムアップ）

390

A - 12435 / Sort

B - Geometric Sequence / 等比数列

D - Stone XOR / XOR、グループ分け、DFS（全探索）

E - Vitamin Balance / ナップサック問題、DP（テーブル）、二分探索

389

C - Snake Queue / 累積和 or Deque + 遅延評価

累積和

Deque + 遅延評価

D - Squares in Circle / 座標平面（円）、二分探索

388

D - Coming of Age Celebration / imos 法

E - Simultaneous Kagamimochi / 二分探索

387

C - Snake Numbers / 整数問題（いい数の個数）、桁 DP（メモ化再帰）

D - Snaky Walk / 多始点 BFS

386

B - Calculator / ランレングス圧縮

D - Diagonal Separation / グリッド（応用）

E - Maximize XOR / XOR、組み合わせ

385

C - Illuminate Buildings / 等差数列

D - Santa Claus 2 / 二分探索、Ordered Set

384

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

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

解法 1 尺取法

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

E - Takahashi is Slime 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 / 尺取法

E - 11/22 Subsequence / 二分探索、累積和

380

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

D - Strange Mirroring / 二進数（ポップカウント）、回文

E - 1D Bucket Tool / Union Find

379

D - Home Garden / 遅延評価

E - Sum of All Substrings / シグマ、巨大な数

378

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

E - Mod Sigma Problem / シグマ、累積和、フェンウィック木

377

376

B - Hands on Ring (Easy) / 円環

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

E - Max × Sum / ヒープ

375

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

正方形グリッドの回転

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

D - ABA / メモ化

374

C - Separated Lunch / ビット全探索

E -　 Min of Restricted Sum　/ XOR、連結成分分解