2009-01-01から1年間の記事一覧

PKU 1146 ID Codes

PKU

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>

SRM456 Div1 Midium(450) CutSticks

CutSticks二分法。最初ループの条件を while((b-a)>1e-10) としていたら、無限ループになるテストケースがあった。参加した方のブログを見るに、二分法のループ回数は定数にするものらしい。 今回の問題は、最初の幅が高々109、求められている精度が10-9で、…

SRM456 Div2 Easy(250) AppleWord

AppleWord長さnのアップルワードは apn-3le。 #include <string> #include <ctype.h> using namespace std; class AppleWord { public: int minRep( string word ); }; int AppleWord::minRep( string word ) { int n = (int)word.length(); if ( n < 5 ) return -1; int c = </ctype.h></string>…

SRM456 Div1 Easy(250) SilverDistance

SilverDistanceスタートとゴールがチェス盤でいう違う色のマスならば少なくとも1手前に進む必要がある。同じ色のマス間の移動ならば、前に動く必要は無い(斜めのみの移動でも同じ手数)。 #include <algorithm> using namespace std; class SilverDistance { public: </algorithm>…

SRM456

Easy (250) 0簡単だと思ったのに、abs()忘れてシステムテスト落ち。もったいない。Medium (450) 0二分探索という手があったか。Hard (1050) 0見てない。結果 1435 → 1349orzこれはひどい。

PKU 1026 Cipher

PKU

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

PKU 1025 Department

PKU

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

SRM455 Div2 Medium(500) EasySequence

EasySequenceAの先頭N個と同じ数列が出てくれば以降は同じ数列が生成されるので検索を打ち切る。N≦7なのでAは長くとも107程度にしかならない。 #include <vector> #include <numeric> using namespace std; class EasySequence { public: int find( vector <int> A, vector <int> B ); b</int></int></numeric></vector>…

SRM455 Div2 Hard(1000) DonutsOnTheGrid

DonutsOnTheGridEasyと付いているDiv1の問題のほうが簡単……かと思いきや、問題サイズが大きくなっていてO(n4)では終わらない。 000000 0..... 000000 0....0 000000 0....0 000000 000000 ← y ^ ^ x1 x2左端がx1、右端がx2、下端がyのドーナツの個数は、yよ…

SRM455 Div2 Easy(250) SpidersOnTheGrid

SpidersOnTheGrid #include <string> #include <vector> using namespace std; class SpidersOnTheGrid { public: int find( vector <string> A ); }; int SpidersOnTheGrid::find( vector <string> A ) { int w = (int)A[0].size(); int h = (int)A.size(); vector<string> c( h+2, string( w+2, 'o'</string></string></string></vector></string>…

SRM455 Div1 Medium(550) ConvexHexagons

ConvexHexagons元の正三角形から小さな正三角形を切り出し、その正三角形の頂点を切り落として六角形を作ると考える。 サイズNの正三角形に含まれるサイズtの正三角形の個数は(N-t+2)(N-t+1)/2。サイズtの正三角形から上・左下・右下の切り取る幅をそれぞれu…

SRM455 Div1 Easy(300) DonutsOnTheGridEasy

DonutsOnTheGridEasy動的計画法。num(x1,y1,x2,y2)を(x1,y1)-(x2,y2)の長方形が含むドーナツの個数とすると、 num(x1,y1,x2,y2) = min( num(x1+1,y1,x2,y2), num(x1,y1+1,x2,y2), num(x1,y1,x2-1,y2), num(x1,y1,x2,y2-1), num(x1+1,y1+1,x2-1,y2-1)+1, (こ…

SRM455

Easy (300) 0チャレンジで落とされた。Practiceで確認してみたらTimeLimitExceedだった。Medium (550) 0時間切れ。Hard (900) 0見てない。結果 1460 → 1435一旦落ち着いてみれば普通に解ける気もするんだけど、本番中はどうしても焦ってしまう。次も点数が落…

PKU 1024 Tester Program

PKU

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

PKU 1023 The Fun Number System

PKU

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>…

PKU 1022 Packing Unit 4D Cubes

PKU

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

PKU 1020 Anniversary Cake

PKU

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

PKU 1019 Number Sequence

PKU

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

PKU 1018 Communication System

PKU

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>…

PKU 1021 2D-Nim

PKU

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>

SRM454 Div2 500 WordsGame

WordsGame行ごと列ごとの交換なので、他の行・列に文字を移すことはできない。例えば、↓の例で s と c は常に異なる行・列に含まれる。各行と列を独立に考えて目的の単語を作る最小手数を答える。 sdf bca hgf貪欲に交換していっても最小手数が求まるのだが…

SRM454 Div2 Easy(250) MinimalDifference

MinimalDifference #include <algorithm> using namespace std; class MinimalDifference { int sum( int n ); public: int findNumber( int A, int B, int C ); }; int MinimalDifference::findNumber( int A, int B, int C ) { int diff = 999; int X; for ( int i=A;</algorithm>…

SRM454 Div1 Medium(500) NumbersAndMatches

NumbersAndMatches動的計画法。a 本のマッチを加えつつ k 本のマッチを動かして残り d 桁の数字から得られる数字の個数を t[d][k][a] とする。数字 x を y に書き換える際に動かすマッチの本数を ux,y、加える(負数で取り除く)マッチの本数を vx,y とする…

SRM454 Div1 Easy(250) DoubleXor

DoubleXor問題文の通りに計算するだけ。 class DoubleXor { public: int calculate( int N ); int dxor( int a, int b ); }; int DoubleXor::calculate( int N ) { int ans = N; for ( int i=N-1; i>0; i-- ) ans = dxor( ans, i ); return ans; } int Doubl…

SRM454

250点問題 187.55いろいろ悩んだけど、単純に計算して充分間に合うのかよ orz 109と106を区別できるようにならねば。500点問題 0方針は立ったけど、時間切れ。1000点問題 0見てない。結果 1490 → 1460 イエローコーダーにはなれず。無念。

SRM453.5 Div2 Hard(1000) TheProduct

TheProduct動的計画法。最後が numbers[i] である k 個の数字の積が取りうるのは、最後が numbers[i-maxDist]〜numbers[i-1] である k-1 個の数字の積に numbers[i] を乗じた値。各マスでは正負それぞれ絶対値が最小・最大であるものだけ記憶しておけばよい…

SRM453.5 Div2 Medium(500) MazeMaker

Div 1の250と同じ。

TopCoderプラグイン導入

クラス定義とか入力例をコピペするのが面倒になってきたので、プラグインを導入した。定番らしいCodeProcessor+TZTester+FileEdit。テンプレートはこんな感じ。 #include <iostream> #include <string> #include <vector> using namespace std; class $CLASSNAME$ { public: $RC$ $METH</vector></string></iostream>…

SRM453.5 Div2 Easy(250) ToolsBox

ToolsBox #include <sstream> #include <vector> #include <set> using namespace std; class ToolsBox { public: int countTools( vector<string> need ) { set<string> tool; for ( int i=0; i<(int)need.size(); i++ ) { stringstream s( need[i] ); string t; while ( s >> t ) tool.insert( t </string></string></set></vector></sstream>…

SRM453.5 Div1 Medium(450) PlanarGraphShop

PlanarGraphShop動的計画法。c 個のグラフで n コインとなるなら、c+1 個のグラフの組み合わせで n+1, c+8, c+9, c+27, ……コインを作れる。 グラフが平面グラフとなる条件はWikipediaより、 Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3。X=2…