LPであることと、フローっぽいことはなんとなく分かるけど、最小費用流のLP双対の形にするのが少し難しいので、1100妥当だと思う。 解法 最小費用流の双対なので、変形してから流す。 ネットワークが少し特殊な形をしてるけど、蟻本とかで調べるとやり方が書…

解法 木のサイズに関する自明な枝刈りをすると計算量が落ちるから、頑張って実装する。 木を作ったり判定したりするのが大変なので工夫すると比較的楽に実装できる。 判定するときは、queueを3つくらい使うと綺麗に実装できる。 #include <iostream> #include <string> #includ</string></iostream>…

解法 包除原理+DP包除原理に気づかずbitDPしようとしたら複雑すぎて無理だった(解説スライド見ても解けるとしか書いてなかった) あと、解説スライド見ると包除原理だけで良いらしい(ちょっと読んでもよく分からなかった) #include <cstdio> #include <cstring> #include <algorithm> #inc</algorithm></cstring></cstdio>…

解法 cuteでソートするとDPできて、cuteの最大値が定数で、dp[鍋の種類][重さ] := max{cuteの最小値}となるようなテーブルがO(NW)で作れる。 できたテーブルは尺取法でO(W)で走査できる。全体で、O(NW) #include <iostream> #include <algorithm> #include <map> #include <cstring> using names</cstring></map></algorithm></iostream>…

解法 dp[index][分割する個数] := min{右端に来る数} とするとO(N^3)でDPできるが、これでは間に合わないので、工夫して dp[index][右端に来る数] := max{分割する個数} として、j #include <iostream> #include <cstdio> #include <vector> #include <map> #include <algorithm> using namespace std; </algorithm></map></vector></cstdio></iostream>…

考察要素が大きく、実装パートも面白いので良問だと思う。 解法 完全グラフK_nのときは、自明 そうでないとき、他の全ての点と接続しているような点が存在しているから、その点を取り除く。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef lon</vector></algorithm></cstdio>…

解法 sort+累積和+setで解こうとするとsetのメモリの定数倍が大きくMLEするので、 尺取法みたいな感じ(？)で次数を1つずつ順に見ながら、最小カットを考えるとO(n)で解けて、メモリも足りる。 #include <iostream> using namespace std; typedef long ll; #define N 25</iostream>…

解法 想定解は、後ろからUnionFindらしい。賢い。この問題は(実装が重くなるが)平方分割でも解けて、 MクエリがB回来るたびにO(N)で全部の頂点を更新すると、Qクエリをダブリングを用いてO(BlogN)で処理でき、全体でO(Q*(N+BlogN))となるので B = √(NlogN)程…

解法 SRM607Med CombinationLockDiv1と同じように考えると、直ぐ解ける。 まず、to - from を計算して、回転数を求めて、差分を求めることができる。 「(複数の)ダイアルを1回回す」 ⇔ 「差分を任意に2つ選び、それぞれ +x, -x する」 であるから、差分を総…

解法 直近の順列に着目して、DPする #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; #define chmax(X,Y) X=max(X,Y) #define N 200 map<vector<int>, int> dp[N]; int main(){ int n; cin>>n; vector<int> d(n), a(n); for(int i = 0; i < n; i++) cin>>d[i];</int></vector<int></algorithm></map></vector></iostream>…

良問 解法 nが3^*のときは解を二分探索すると解けるから、ダミーの貴族を追加する。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 401000 int d1[N], p[N], d2[N], d[N], s[N]; int n, m, n2; int rest, off, lm; int rec(int l, int r){ </algorithm></cstring></cstdio>…

解法 できるだけ状態をまとめるようにして、場合分けする。 n=1のコーナーケースはm=1のケースに帰着できる。 正しいコード(下のと同じ)http://ideone.com/gFCDZv 場合分けしすぎてTLEするコードhttp://ideone.com/s13jcw #include <iostream> #include <algorithm> #include <cstring> usi</cstring></algorithm></iostream>…

解法 基本的にはさほど難しくない考察をひたすら続けるだけなので省略.Wikipediaやuwicoderを見ながら考察する. ただし、(1+q+q^2+...+q^*)の周期はpより大きくなることがあることに注意する. 再帰するとスタックオーバーフローでREが出るので、TopCoderのス…

Person responsible for problem description don't w 解法 grundy数のベクトルで考える. ある頂点 u から出る辺が存在しないとき r(u) := 0 と定義し, u の子が存在するとき, r[u] := 「r(uの子の集合) に含まれない最小の自然数」 として, grundy数のベク…

問題 となるようなA, Bの組の個数を1,000,000,007で割ったものを求める. (A, Bの条件については問題文参照) 解法 まず にを代入し整理すると、となる. を求めれば良い. ただし、 は N次元ベクトルで、 で、置換の大きさは同じであるとする. 置換の大きさは、…

解法 bitDP(の別解)で解きました. 下から見ていき、Iになっている場所と、直前がJでその下がIという状態を持つことでも解ける. JOが隣り合う状態を持つ方が状態数が少なくなるが, この解法でもO(n^2*2^n)なのでAOJでは間に合う. #include <iostream> #include <string> #includ</string></iostream>…

解法 音程の最小値と最大値の間は、単調にすべきである。(単調で無かったらswapしてよりよい状態にできる) 音程をソートして、最小値から考えることにする。常に、左が右に追加していけばよいが、実はgreedyでよいことが分かる。floor(スコアの和/L)の部分は…

問題 二人完全情報ゲームをする。 グラフが隣接行列で与えられる。交互に辺を追加していき、グラフを連結にしたほうの負けである。 解法 N( とりあえず、Union-Find木を用いて、既に連結になっている部分を調べる。 少し考察すると、(既に連結である部分の頂…

中央の','を見つけるのは簡単(左から見て、'('が一つ多い時に来る','が中央の',')なので、簡単な構文解析で解けます。get_i()とget_u()はほとんど同じだから、まとめても良さそう。 #include <iostream> #include <string> using namespace std; int center(string& s){ int co</string></iostream>…

まず、逆向き(プレゼントを拾う方向)に考えると探索空間が減ることが、この問題の重要な性質です。これに気が付かないとAOJでは通せないと思います。AOJの場合、実行時間制限とメモリ制限が厳しく、ナイーブな探索やDPでは解けないので、少し工夫する必要が…

横棒を通るときに、番号をその棒に記録しておけば、もう片方から来たときにO(1)で交差してることが分かります。 交差を切ることで、得点を入れ替えることができるから、最も得点差(点数を減らせる量)の大きいものを求めれば良いです。 #include<cstdio> #include<cstring> #in</cstring></cstdio>…

愚直に全てシミュレーションするとTLEするので、N-1回散歩した後の地図を求めます。 ある点をn回通るとき、 (i) nが偶数のとき、東と南にn/2回ずつ通る (ii)nが奇数のとき、最初に書かれていた文字の方向に(n+1)/2回、もう一方に(n-1)/2回通る よって、通過…

特定の区間に足し算をするのを高速(全体でO(n+m)くらい)に行えば良いから、累積和で解くことができます。 #include<cstdio> #include<algorithm> using namespace std; #define MOD 100000 int inn[100000],walk[100001]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i </algorithm></cstdio>…

動的計画法で解けます。引っかかる人はほとんどいないかもしれませんがコーナーケース(最初が0のとき)があります。 #include<iostream> using namespace std; typedef long long ll; ll dp[100][21]; int data[100]; int main(){ int n; cin>>n; for(int i = 0; i < n;</iostream>…

" 入力例 2 において，あなたには友達はいない．"単一始点最短路を求める問題。 普通にダイクストラ法やワーシャルフロイド法するのは面白くないので少しだけ違う解き方をしました。想定解法とあまり変わらないみたいです。 #include<iostream> #include<cstring> #include<algorithm> usin</algorithm></cstring></iostream>…

DFS(深さ優先探索)の典型問題。m+2 × n+2のマップを使うとマップ外に出なくなるのでオススメです。 #include<cstdio> #include<algorithm> using namespace std; int m,n,unused[90][90],dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; int dfs(int y, int x, int d){//座標と、今までに</algorithm></cstdio>…

実装。色の変え方が最大で2パターンあるので、両方とも試す。 #include<cstdio> #include<algorithm> using namespace std; int n,chain[10000]; int fig(int b){ int a = b-1,c = b+1,color,res = 0; if(a>=0){//b == 0のバターンを弾く int s = 1; color = chain[a]; while(a></algorithm></cstdio>…

動的計画法で解きました。INFで初期化する代わりに-1で初期化してます。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,x[151][11],d[150][11],dp[150][10][77]; const int INF = 1000000000; int main(){ while(scanf("%d%d",&n,&m),n){ memset</cstring></algorithm></cstdio>…

共通部分文字列の長さの最大値を求める問題。 1文字後ろを調べ、同じ文字列を重複して調べないようにすると、TLEしないで解けます。 O(n^3)かO(n^2)です。 #include<iostream> #include<string> #include<algorithm> using namespace std; string s,t; int main(){ while(cin>>s>>t){ int </algorithm></string></iostream>…

辺が増えていく最短経路問題。増えた辺を使うと経路が短くなる場合があるので、それを調べます。(増えた辺を使わないで経路が短くなることはない) O(kn^2)です。AOJではギリギリ通せなかったのですが、ワーシャルフロイド法(や、その他の最短路のアルゴリズ…