Going Home割り当て問題。最小費用流で解ける。 #include <iostream> #include <string> #include <vector> using namespace std; // 最小費用流 O(fn^2) // F: 容量, C: 費用, s: 始点, t: 終点, f: 目標流量 // 返値: 最小コスト、目標流量を流せないなら-1 // 両方向のフローには未</vector></string></iostream>…

A decorative fence分からないのでカンニング。なるほど、途中まで板の長さを決めたときに残りの板の選び方が何通りあるかを先にDPで求めておくのか。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { const int M = 20; // [i][j][k] 残</algorithm></vector></iostream>…

Spell checker手抜きで編集距離=1としたらTLEだった。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool replace( string a, string b ); int main() { vector<string> dict; while ( true ) { string s; cin >> s; if ( s == "#" ) break; dict.</string></algorithm></vector></string></iostream>…

The dog task２部グラフの最大マッチング。 #include <iostream> #include <vector> #include <cmath> using namespace std; double dist( vector<int> a, vector<int> b ); /*int*/ vector<vector<bool> > maxmatch2( vector<vector<bool> > G ); /*int*/ vector<vector<int> > maxflow( vector<vector<int> > G, int s=0, int t=-1 ); i…</vector<int></vector<int></vector<bool></vector<bool></int></int></cmath></vector></iostream>

Gangsters動的計画法。O(NKT)は間に合わなかった。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, K, T; cin >> N >> K >> T; vector<int> t(N), P(N), S(N); for ( int i=0; i<N; i++ ) cin >> t[i]; for ( int i=0; i<N; i++ ) cin >> P[i]; for ( int i=0; i<N; i++ ) cin >> S…</n;></n;></n;></int></algorithm></vector></iostream>

Rating問題文の通りに実装。面倒。 #include <iostream> #include <vector> #include <sstream> #include <string> #include <algorithm> using namespace std; int main() { // Input const int N = 101; vector<vector<int> > team( N, vector<int>(2,-1) ); for ( int i=0; i<2; i++ ) { int n; cin >> n, cin.ignore(); i</int></vector<int></algorithm></string></sstream></vector></iostream>…

Defragment各ファイルを移動すべきクラスタは一意に定まる。そのようなクラスタが空いていればファイルを移動、空きがなければ位置が間違っているファイルを適当なクラスタに移動、が最善。O(n2)で間に合うようだ。 #include <iostream> #include <vector> using namespace std</vector></iostream>…

Parliamentグループは2つとは限らないのか。動的計画法。桁あふれするので、小さなNに対しての答えから法則を探した。 #include <iostream> #include <vector> using namespace std; int main() { int N; cin >> N; vector<int> v; int s = 0; for ( int i=2; s+i<=N; i++ ) v.push_</int></vector></iostream>…

Fence真面目に計算すると大変そうだけど、原点から見て360度のうちどれだけ壁が見えるかを考えれば良い。ある点を基準として最左と最右の点の角度を求める。ただし角度は最大で2π。 #include <iostream> #include <cmath> #include <algorithm> using namespace std; int main() { const </algorithm></cmath></iostream>…

False coini番目のコインが偽者と仮定して、計量の結果と矛盾が無いか調べる。矛盾の無いコインがちょうど１枚ならば、そのコインが偽者。 #include <iostream> #include <vector> #include <algorithm> using namespace std; bool contain( vector<int> v, int c ) { return find( v.begin(), </int></algorithm></vector></iostream>…

Web Navigation #include <iostream> #include <string> #include <vector> using namespace std; int main() { string current = "http://www.acm.org/"; vector<string> backward, forward; while ( true ) { string c; cin >> c; bool ignore = false; if ( c == "BACK" ) { if ( backward.e</string></vector></string></iostream>…

The Same Game懐かしい。 C++だとTLE、G++で900MS。通ったから良しとしよう……。 #include <iostream> using namespace std; const int W = 15; const int H = 10; void cluster( char b[W][H], int c[W][H] ); void fall( char b[W][H] ); int main() { int n; cin >> </iostream>…

ID Codes #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string code; while ( cin>>code, code!="#" ) if ( next_permutation( code.begin(), code.end() ) ) cout << code << endl; else cout << "No Successor" << endl; return 0; }</algorithm></string></iostream>

Cipher各文字は一定の周期で移動する。サンプルインプットの (4 5 3 7 2 8 1 6 10 9) ならば、 1,4,7 は 1→4→7→1 と周期３で 2,5 は 2→5→2 と周期２で巡回する。 kを周期で割った余りだけ動かして計算時間を短縮する。時間制限がけっこう厳しい。 #include <stdio.h> </stdio.h>…

Department複雑だけど問題文の通りに書くだけ。１秒ごとにシミュレートしても間に合う。エレベータを特殊な部屋とみなしたり入退室の処理は固定時間なので省いたりして多少はコードがすっきりした。出力はエージェントのコード順にソートするように指示され…

Tester Program一意な最短経路が存在する場合に経路を返す関数を作る。出力をそのまま関数に与えて入力と同じ経路が返ってきて、なおかつどの壁を消去しても入力と異なる経路が返ってくれば正しい答えである。最短経路が一意かどうかの判定は幅優先探索中に…

The Fun Number System下位ビットから順に計算していく、Nのiビット目が1ならば、より上位のビットがiビット目に影響することはないので、出力も1となる。 #include <iostream> #include <string> using namespace std; int main() { int t; cin >> t; while ( t-- > 0 ) { int</string></iostream>…

Packing Unit 4D Cubes４次元にビビらされるけど難しくはない。どれか１つのキューブの位置を適当に決めて、整合性をチェックしながら、隣接するキューブの位置を求めていく。 #include <iostream> #include <vector> using namespace std; struct CUBE { int id; // id int ne</vector></iostream>…

Anniversary Cakeバックトラック。余りが出ないようにという条件があるので、各深さでは最初に見つけたケーキの残りを切り取ればよい。 #include <iostream> #include <numeric> using namespace std; int s; // ケーキサイズ bool cake[99][99]; // ケーキ int piece[11]; // </numeric></iostream>…

Number Sequence入力 i に対して、i が含まれるグループを Sk とすると、k もグループ Sk の長さ |Sk| も O(√i) 程度である。x の桁数を digit(x) として、 |Sx| = |Sx-1| + digit(x)が成り立つことから k を求める。グループ１つに対してならば n 番目の数…

Communication System帯域幅を変えながら、その帯域幅以上で最安の製品を選んでいく。 #include <iostream> #include <vector> using namespace std; struct MAN { int B, P; }; int main() { int t; cin >> t; for ( int i=0; i<t; i++ ) { // 読み込み int n; cin >> n; vector<vector<MAN> > man( n ); for ( int j=0; j<n; j++ ) { int m; cin >> m; </n;></vector<man></t;></vector></iostream>…

2D-Nim #include <iostream> #include <vector> #include <algorithm> using namespace std; struct XY { int x, y; XY() {} XY( int x_, int y_ ) : x(x_), y(y_) {} bool operator<( const XY &a ) const { return x</algorithm></vector></iostream>

Packets1x1と2x2の隙間をカウントしながら大きい順に置いていく。 #include <iostream> using namespace std; int main() { while ( true ) { int p[7]; for ( int i=1; i<=6; i++ ) cin >> p[i]; int num = 0; int s1 = 0; int s2 = 0; // 6 num += p[6]; // 5 num +=</iostream>…

Numbers That Count #include <iostream> #include <string> using namespace std; string invent( string w ); int main() { string w; while ( cin >> w && w != "-1" ) { string seq[16] = { w }; for ( int i=1; i<=15; i++ ) seq[i] = invent( seq[i-1] ); int j, k; for </string></iostream>…

Jury Compromise動的計画法の使い方がわかってきた。 D(J)-P(J) の取り得る値が高々±20nなので、m人の候補を組み合わせて D(J)-P(J)=i となりうるかどうかを表の i 番目のセルに持つ。複数ある場合は D(J)+P(J) が最大となるようにすることで、最適な組み合…

Dividing与えられたビー玉を組み合わせて合計の半分の価値にできるか、ということと等価。 ビー玉の価値の合計が高々120000ということに着目して動的計画法で解く。価値m以下のビー玉を組み合わせて価値iを作れるかどうかを表に持つ。そのまま実装すると制限…

Counterfeit Dollar12枚のコインそれぞれが軽い・重いと仮定し、矛盾がないか調べる。 #include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; string info[] = { "down", "even", "up" }; for ( int i=0; i<n; i++ ) { string weight[3][3]; for ( int j=0; j<9; j++ ) cin >> weight[0][j]; for ( char c=</n;></string></iostream>…

Faulty Odometer 要は、012356789の9文字を使った9進数を読み込むだけ。 #include <iostream> #include <string> using namespace std; int main() { int map[] = { 0, 1, 2, 3, 0, 4, 5, 6, 7, 8 }; string s; while ( cin >> s && s[0] != '0' ) { int mile = 0; for ( int i</string></iostream>…

Joseph とりあえず書いてみたプログラムだとTLEになるけどkの幅が小さいので、↓のプログラムで全ての場合を計算し、 #include <iostream> #include <vector> using namespace std; int main() { for ( int k=1; k<14; k++ ) //int k; //while ( cin >> k && k > 0 ) { int m; f</vector></iostream>…

Sticks Time Limit Exceedを回避することができず、諦めてカンニング。ShortCoding本に載っていた。著者のサイトにも250Bまでは。書き方は違うけど、やっていることは同じだよなと首を捻ったが、バグで一部枝刈りが働いていなかった。 枝刈り 長い順に試して…