1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数を求める問題。 これって冷静に考えれば重複組み合わせだからcombination(n+k-1, k-1)じゃん… なんかちょっとむずかしいことしてみたけど結局求めているものは一緒です…はぁ… const ll mod = (ll)1e…
最短経路の組み合わせの数を求める問題。 完全に発想が凝り固まっててすごい時間がかかった…。頭の中で考えてるうちは、普通に始点からつながっているところの組み合わせを更新していくだけじゃ無駄に数えてしまいそうだなぁとか考えていたけど、手を動かし…
dpなんだけど、かなり上手くやらないとTLEする難しい問題。dpは現在の状態を上手く簡単に表すことでいろんな場合を統合して扱うものなので、今回も現在の状態をより簡単に表す方法を探さないといけない。'0'を-1, '1'を+1としてグラフにして見ると、これって…
モーターの種類が個人的にゴチャゴチャしてきたので一回まとめます。直流と交流 直流(DC) 電圧に対しての回転特性が安定していて制御しやすく、一般的には安価。 ブラシや整流子が入っているのでノイズや機械的な劣化が問題になりやすい。 また特徴として、…
回路について知らなさすぎるので、忘れないように用語をまとめてみる(STM32の話多め)。CAN Controll Area Networkの略。相互接続された機器間のデータ転送に使われる規格。ロボット分野に置いても使われる。二本のデータ線からなり、電圧の差動によってデー…
初期点群が与えられ、平行移動、回転、拡大をしたあとの最終点群が与えられたときの拡大率を求める問題。最近、こういう問題にはこれを考える。こういう問題にはこういうアプローチが多い。みたいに頭の中でカテゴリ化していた自分としてはイレギュラーで、…
風船が上がっていくのを撃ち落としてなるべく撃ち落す風船の最大の高さが最小になるようにする問題最近こういう問題多く見る気がする。 最大、最小を求める系の問題である程度値が大きくて時間足りないよぉ> ある高さ以内で撃ち落とせるかを判定して、それを…
盤面のある行とある列を足してKとなる組み合わせの数を出力する問題。 すごい簡単そうなんだけど、普通にやろうとするとO(R*C)でR,Cが10^5なのでTLE どう考えるかというと、盤面ではなくて、飴のあるマスに関してだけ注意を配る。 単純に足し合わせがKになる…
頂点1からその頂点にもどるとき、同じ道を使わない最短経路の最小コストを出力する問題。ダイクストラとかを変形して使えないかなぁと考えたけど無理。 なんとかして最短経路問題に落ち着かせられないか。頂点0に直接つながっている頂点を2つ選んで、その2つ…
もはや蟻本ではないけど、アルゴリズム関係は全部蟻本カテゴリーに入れてしまおう。ゲーム木探索をするときの基本的な方法についてまとめてみる。 minimax法 自分は評価関数が最大になる手を打ち、相手はこちらの評価関数が最小になるように手を打つ。negama…
ゲーム木の問題。 この前も同じのやったんだけどやっぱり考え方がいまいち上手く行かない… こういうので大事なのは、最初からやっても大変だから、一番最後から考えよう、という発想。 つまり再帰的に計算する。あとでゲーム木探索について軽くまとめようか…
辺eにはコストd(e)と容量c(e)が定まっていて、sからtへ流量Fのフローを流したときの全ての辺の流量×コストの和が最小になる時の費用を求める問題。これは単純で、最大流のときとほぼ同じです。残余グラフを考えて、そこでコストを考慮して最短路に沿って流せ…
考察系の問題。 辺を順番に塗っていき、折り返してもう一度塗り直すことができる。こういうときの常套手段として、過去から遡れば、辺の彩色は一度でいいという、つまり塗り直す必要は無いという性質がある。また、これより、分岐の時も何も考えなくていいこ…
試験が残り一つなので適当に蟻本を読んでみることにした。 最大流 …グラフにおいてs(source)からt(sink)に水を流したときに最大どのくらい流せるか？蟻本にのっていたように、最初にdfsでsからtまで限界まで水を流す。 その後、水を押し戻したりして最大にな…
簡単なのにかなり時間がかかった。 なぜか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。 ある適当な仮想国家を一つ持ってきて、そこから都市への道をその都市のコストにしてあげると綺麗になって、最終的にプリム法で一…
今度は最小全域木問題に関してまとめてみます。まず、最小全域木問題を解くには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,…
とりあえず始めてみました。 大したことは書きませんが、備忘録的な感じで使っていきたいと思います。
