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

今度は最小全域木問題に関してまとめてみます。まず、最小全域木問題を解くには2つの方法が知られています。1.プリム法 2.クラスカル法 1.プリム法これはダイクストラ法と似ていて、O(ElogV)のアルゴリズムです。 ある頂点群Vの部分集合であるXとXの補集合を…

ARC031のD問題解こうと思ったら二部グラフの最大流とか言われてうぇええんって感じなので、グラフについて調べつつ忘れないように書いていきます。最短経路問題には3種類の解法があります。 1. ベルマンフォード法 2. ダイクストラ法 3. ワーシャルフロイド…

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

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

立体角って毎回うやむやにしてきたので調べてみた。 つまりは切り取った半径1の球の面積。 だから全部で4π。 まぁ平面角からの拡張と考えると当たり前かもしれない。また、半頂角θの円錐が切り取る立体角は、2π(1-cosθ)。立体角 - KobaWikiココらへん見ると…

難しかった。まず、攻撃力と防御力とか言われて二次元座標に落としこむような発想がない。 二次元配列の累積和はすごい使えそうなのでライブラリ化したい。 また、今まで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,…

とりあえず始めてみました。 大したことは書きませんが、備忘録的な感じで使っていきたいと思います。