頂点v-u間への操作を考える時、グラフを木にできるなら根rを定めて、v-r,u-rに分けて考えてみる v-uのLCAをpとして、v-uへの操作はv-p,u-pに分けることができる。p-rへの操作を二回しているとみなしてv-r,u-rに分けてみる。「二回操作すると戻る」タイプの場…

atcoder.jp 値の列に対して二項演算を実行していって値を計算したい。そして、一つ抜いた時の値を計算したい。 この問題で言えば、gcdを実行していくが一つ抜いた時のgcdを高速に計算したい。 この時二項演算が結合則を満たすと、どこから計算していっても良…

atcoder.jp UnionFindの例題としてみたのでUnionFindを使うことは分かっていた状態だったけど解くことは出来なかった。。。 ので思いつく為に必要なことをまた考察してみる 場所iと値p_iを同一視する x,yのスワップをUnionFindに突っ込めば良さそうな雰囲気…

atcoder.jp 消滅していないゴーレムを数えるのではなく消滅するゴーレムを数えよう、というところまでは思い至ったのだけど結局解けず。解説見て一発で理解出来て悔しかった。 とうことで、どんな事を検討していたら解けたか考えてみる 1クエリで最悪10**5箇…

ABC121-Dが競技中に解けなかったので、XORの性質について調べて追記していく。コードはpython。 基本 「^」で計算できる。 a = 1 b = 2 c = a^b # 3 整数をビットごとに考えて、aとbで0/1が異なる場合に1それ以外は0となる。 性質 1. 0とXORを取っても値は変…

atcoder.jp 何とか時間中に解けたけどもう少しスマートに早くできるようになりたい、、 二分探索を使うという発想は良かったが、解説にあるような最小値と最大値を挿入するというのを思いつかなかった。リストの中から見つからない、という状況をif文で何と…

atcoder.jp すぬけ君一体どういう生物、、 まだこのレベルはコンテスト中に解けない気がする。 解法 すぬけ君が行ったり来たりする中で、石が数がどんどん増えていき、一つも石が入っていない耳ももちろんある状態。どれだけ石が入るかは散歩の仕方によるけ…

atcoder.jp 考え方は正しかったっぽいので、本番で解きたかった。 あとネタの種類に対して美味しさが複数値あり得るということにしばらく気付かなかった。サンプルとかちゃんと見よう。 解法 とりあえず美味しさが大きい順に取っていって、暫定の回答を作る…