JavaScriptでABC420(A-E)
A - What month is it?
XとYを足して12で割ったあまりを求めると月になります
答えが12月の場合だけ0になっちゃうので、そこだけ||演算子とかで拾い上げればOK
00分51秒 AC!
B - Most Minority
Bは愚直
人数分の長さのnumberの配列を0で初期化して、投票結果を一回ずつ集計して少数派にポイントを上げればOK
途中iとj逆に書いちゃって混乱しかけましたが耐え
7分48秒 AC!
C - Sum of Min Query
「現時点の
クエリを処理する前の初期値は普通に計算すればOK
クエリ処理時、min(A_k, B_k)とmin(変えなかったほう, V_i)の差だけ合計値が変わるので、それを反映してあげます。
18分14秒 AC!
D - Toggle Maze
グリッド怖いよ〜〜〜
まあBFS(最短経路必須だからDFSじゃないよ)でしょう
とりあえずBFSやるならキューが必要になりますね、私はDequeを作ってるのでこれを使います
「与えられた迷路とドアの開閉が反転した迷路があり、スイッチマスに移動しようとした瞬間にそれらを行き来する」みたいに考えるとうまく探索できると思います
訪問が確定している場所はSetで管理。
私はn/1/1とかr/2/1みたいな「${currentMaze}/${i}/${j}」形式の文字列を保存してました
あと最短手数が必要なので、各マス(通常迷路と反転迷路は区別する)への最短手数は都度メモっておきましょう どうせ一回しか訪問しないから大小比較して小さい方を……とか考える必要はなし
57分14秒 AC!
E - Reachability Query
無向グラフで連結判定に近いけど"黒色"をどう処理すればいいか……
ちょうど今日の夕方にUnion-Findを用意したのでこれが使えないかと考えた結果思いつけました
「各要素が黒色か」と「(根の要素限定で)その要素が含まれる木の中に黒い要素はいくつあるか」を持ってunion()のときにsizeと同様に処理してあげれば、「根を見つける→その要素が含まれる木の中に黒い要素が1つ以上あれば到達可能」といえます
ということでがんばってそれをやります Union-Find作っておいてよかった〜〜！！
86分36秒 AC!
F-G
チラ見したけど見当つかなかったよ
Perfomance
- perf : 1025
- レート変化 : 841 → 861 (+20)
感想
祝、初5完！！！！！嬉しい！！！！！！
DequeとUnion-Findを持っていたのがだいぶプラスに働きました、最高
過去のABCも似たような記事を書いています。よければそちらもどうぞ。
Discussion