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>

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

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

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

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

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

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

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

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

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

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, （こ…

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

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>

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

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

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

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…

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

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

Div 1の250と同じ。

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

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

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…