ISUCON4に初参加した。 予選通過ならずっぽいけど、いろいろ勉強になったので、記録しておく(だらだら書き)。 チーム aomoriringoさん、matsu4512さん、自分。 おおよその役割分担は、 aomoriringo : アプリ周り中心 matsu4512 : DB周り中心 自分 : その他 …

問題 無向木が与えられる。 クエリとして、頂点a,bが与えられるとき、aとbに辺を追加したら閉路ができる。このとき、閉路を形成する辺の数を返す。V Q 考え方 Qが10^5まであるので、O(n)な解法だと間に合わない。 頂点aから頂点bまでの距離がわかっていれば…

問題 木が与えられる。 木の辺を以下のルールで削除していく。 ・最初にどこかのノードを決める ・ノードから辺を渡って別のノードへ移動する ・今いるノードにつながる辺を一つ削除し、今いるノードにとどまる 辺が無いノードには移動できない。削除や移動…