HackerRank World CodeSprint 13 参加記

今回の World CodeSprint 13 で初めて HackerRank の T シャツをゲットできてテンションが上がったので調子に乗って参加記的なのを書いてみました.
問題番号順じゃなくて解いた時系列順に書いてるので注意.

7問目：Dynamic Trees

問題概要：木の辺を繋ぎかえたり, 頂点のブール値を反転させたり, パス上の k 番目の true の位置を求める.

これはもう問題文を読む前から問題名で解法がわかります（ほんまか）
↓
あとは Sleator と Tarjan に感謝しながら ST-Tree(Link-Cut Tree) を生やすとAC.
↓
と思ったらめっちゃバグった.
evert 機能つけてるのに上から探索するときにフラグを push するの忘れてた…だめやんけ…

この問題は Link-Cut Tree ゲーに見えるけど, たぶんクエリ平方分割でもいけます.
あんまりちゃんと考えてないけど.

1問目：Find The Absent Students

問題概要：1-n のうち入力に無い番号を出力する.

まあ, はい.
注意点としては答えが空のときに改行出力を忘れないこと.
（なくてもACになるかも？HackerRank のジャッジをよく知らない）

2問目：Group Formation

問題概要：条件を満たすようにマージしまくったした後一番大きい全てのグループの人の名前を列挙するみたいな感じだった気がする.

列挙が楽なように Quick-Find を使った.
寝不足すぎたため, 既にマージされたのを unite するときの continue を忘れる典型的なミスをして 1 WA.

0 が含まれると逆元がなくて困るので, 場合分け.
↓
k = 0 なら 0 以外の区間の任意の部分列を求めて n * (n+1) / 2 から引く.
↓
k != 0 なら 0 以外の区間に区切ってそれぞれ処理する.
各区間で左から順番に積の累積を持ちながらその逆元を map に入れていってカウントを持っておく.
あとは各位置で ( (k の逆元) * 現在の積) の逆元の個数を足し合わせると答えみたいな感じだったはず.

n * (n + 1) / 2 を計算するときに n が int なのでオーバーフローして 2 WA. おいおい.

4問目：Balanced Sequence

問題概要：'('と')'の列が与えられて, 区間に対する左右反転 & '('⇔')'反転の操作を使って最小何回でvalidな括弧列にできるか.

この問題はこのセットの中で一番難しい.（ ※個人の感想です）
苦手なDP系の問題っぽく見える.
とりあえず, 元々 valid なら 0 でそれ以外は 1 というガバガバを投げてみたところ, 41.25/55 点貰えたため満足して飛ばす.

5問目：Competitive Teams

問題概要：チームのマージクエリと, チームのサイズ差が c (各クエリによって違う値) 以上のチームペアの個数を求めるクエリがくる.

とりあえず Union-Find パートをなくすと, 整数集合に対する追加 / 削除 / 差がc以上のペアの個数のクエリになる.
↓
一見不可能に見えるので平方分割とかか？と思う.
↓
が, よく考えるとサイズの合計は n なので, サイズの種類数は √n になることを考えると map で愚直にやって良いことがわかる.
↓
意味不明なバグらせ方をして6WAするも AC.

この辺りから寝不足+バグらせまくりで精神を病み始める.

6問目：Landslide

問題概要：木があり, 辺が通れなくなったり通れるようになったりするクエリと, x-y パスが通れるかの判定クエリがくる.

お, また Link-Cut Tree ゲーじゃ～んとなる.
↓
よく考えると木の構造は変わらないので HL 分解 + RMQ でよいのでは？
↓
でも Link-Cut Tree 大好きマンなのでそのまま実装する（これがよくなかった）
↓
既に繋がってるのに繋ぐクエリがきたり, 繋がってないのに切るクエリがくることを考えてなくて 9 WA して鬱病になる. 問題文をちゃんと読もうな.
↓
やっと AC.

4問目：Balanced Sequence（再）

なんかよく考えたら, 最悪でも2回くらいで valid にできるんでは？という気持ちになる.
↓
色々サブミットして試したところ, 1回目の提出の 1 を 2 に変えると1回目通らなかったケースは全部通るので, さっきの仮説は正しいことがわかる.
↓
あとは実質 Yes/No 判定
↓
思考力がもう残ってないので, 適当にそれっぽい嘘の条件をいっぱい増やして投げて, 1と2のどちらかに完全に包含されていれば確定するという虚無をする.
↓
あと2ケースだけになったけど, もうそれっぽい条件が思いつかない＞＜
↓
randome_device() を使えば確率 1/4 のガチャになるので, 十分な回数投げれば勝ち確（は？？？）
↓
3回目のガチャでAC（不正ACをやめろ）（Codeforcesだと不可能）（T回のテストケース形式でも無理）（実質0完）

感想

HackerRank は WA のペナルティーがないし, 間違ったケースの番号もわかるので最高だなと思いました.（不正AC者並みの感想）
あと Link-Cut Tree ゲーを出してくれたのは本当に神.

kazuma8128’s blog

競プロの面白い問題を解きます