まあケースあたりO(N^2)くらいのDPをするだけ。 ケースがたくさんあるから最初に全部前計算をtotal O(N^3)未満でやるのかなと思ったら、ケース数が全然なかった。(このせいで無駄に時間を消費した) テストケース数に強く依存する計算量の問題はケース数とか…

英語を読むだけ。*1 1145148108931919364回くらい誤読すると自然とコードが汚くなる。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<map> #include<vector> using namespace std; int G[510][510]; int L[510][510]; int x[510]; int y[510]; int cnt[510]; vector<int>g[510</int></vector></map></queue></algorithm></math.h></stdio.h>…

これがこれで通るのは知識ゲーだと思う。 と思ったけど前にも木上でシュタイナー木作る問題は見たことがあるような…(非自明)Greedyです。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; vector<pair<int,int> > g[11000]; pair<int,pair<int,int> > edge[11000]; int v[11000]; </int,pair<int,int></pair<int,int></queue></vector></algorithm></stdio.h>…

文字ごとに桁数と(2桁なら)一の位が制約つきかを決めて(3^n通りある) 場合わけをひたすらがんばって数えるだけ。 まあ、解いてる人数が少ないだけあってつまらなかった。 #include<stdio.h> #include<algorithm> using namespace std; char str[1100]; char in[2]; int u[110]; i</algorithm></stdio.h>…

双対とって最小費用流。なかなかいろいろなものが得られた。 ・双対のやり方…知らないとどうしようもない。 ・出てきた形…フローを表す式も知らないとわかりにくい ・特殊な形の最小費用流…負コストがあり、最小流量制限があり、そして全体として流す量には…

これらの一部または全部を適当に並べて数字を作ることを考えます。 答えを1,000,000,007 で割ったものを出力してください。問題文がガバガバすぎる。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int mod=1000000007; int b[210]; int kt[210]; int c[</vector></algorithm></stdio.h>…

最小有向全域木。 勉強がてら書いてみました。変な幾何パートもあるし、初書きはこういう問題ではやるべきでないと確信。 あと、こういう問題で英字配列の練習をするべきでないというのも確信。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; d</math.h></vector></algorithm></stdio.h>…

いやあもうホント嬉しい。10: Boomerang 最初に投げる先の頂点を選んで、行った先からのatan2でソートしてO(N^2 log N)。 1点しか行き先がなくて1*1みたいなので落としやすいので気をつけましょう。 #include<stdio.h> #include<algorithm> #include<math.h> using namespace std; const </math.h></algorithm></stdio.h>…