ゲーム木の問題。 この前も同じのやったんだけどやっぱり考え方がいまいち上手く行かない… こういうので大事なのは、最初からやっても大変だから、一番最後から考えよう、という発想。 つまり再帰的に計算する。あとでゲーム木探索について軽くまとめようか…

考察系の問題。 辺を順番に塗っていき、折り返してもう一度塗り直すことができる。こういうときの常套手段として、過去から遡れば、辺の彩色は一度でいいという、つまり塗り直す必要は無いという性質がある。また、これより、分岐の時も何も考えなくていいこ…

簡単なのにかなり時間がかかった。 なぜかWAが少し生えるのが不思議だったが、最初はlen()がintになっていてオーバーフローしているだけだった。long longに直したのでもう大丈夫… #include<bits/stdc++.h> using namespace std; #define len(v) static_cast<long long>(v.size()) #def</long></bits/stdc++.h>…

グラフの問題。最小全域木かなぁと思ったけど、都市に対してもコストがあったので、無理だなぁと重い最初は愚直に書くもTLE。 ある適当な仮想国家を一つ持ってきて、そこから都市への道をその都市のコストにしてあげると綺麗になって、最終的にプリム法で一…

積み木を並べ替える問題。 BIT使えばO(nlogn)ですね、はい。 問題をもっと簡単に表せる方法を頑張って探せば、こういう問題は楽。 難しく考えない。ちなみに、最初 int res = 0;と書いていて値が大きい時オーバーフローして死んだ。 int は2*1e9くらいまでし…

今回は高速フーリエ変換の問題。 まさかこんな問題がフーリエ変換で解けるとは…FFTはいくつかアルゴリズムがある。再帰のものは理解したけど、Cooley-Tukeyは理解するのが面倒だからやめた。サイトのプログラム大体そのまま使った。 typedef complex<double> Complex</double>…

難しかった。まず、攻撃力と防御力とか言われて二次元座標に落としこむような発想がない。 二次元配列の累積和はすごい使えそうなのでライブラリ化したい。 また、今までcombinationにはPascalTriangleを使っていたけど、数が大きい時に死ぬので普通に逆元と…

多項式の値、f(0), f(1), …, f(N)が与えられるから、f(T)を出力しろ、という問題。 単純にラグランジェ補間でよい。 逆元を求める際はextgcdとmod_inverseを使ってあげる。 ll mod = (ll)1e9+7; // extgcd // ax+by = gcd(a,b)の階を生成する。返り値はgcd(a…

数を加えるか、n番目に小さい値を出力して、その数を削除するか、の２つのクエリを処理するだけの問題。 簡単だけど、２分探索のところで少しバグらせてしまった。 友人曰く大事なのは highとlowどちらが合ってるのか、を理解すること。 今回だったら、lowは…

今回はgrundy数の問題。勉強したことがなかったので、蟻本を読んでから解きました。grundy数は、今の状態から一手で行ける状態のgrundy数に含まれていない最小の非負整数です。 これは、grundy数がxの状態からはgrundy数が0〜x-1の状態へ移動できる、という…

ゲーム系の苦手な問題。先手が勝てば勝ち、もし負けることがあれば、負け、という感じで考えるといいっぽい？まず全探索のイメージから入って、そのあとメモ化できるからメモ化しよう、みたいに考えるのがいい。全探索を考えるのが全てにおいて最初。 int H,…