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

ParkAmusement足場iからちょうどKステップでEにたどり着く確率をP[i]とするとベイズの定理から、足場iからスタートした確率はP[i]/ΣP[i]。 #include <string> #include <vector> #include <algorithm> #include <numeric> using namespace std; class ParkAmusement { public: double getProbabil</numeric></algorithm></vector></string>…

NumberPyramids下段が全部1でも頂上は2baseLength-1なので、baseLengthは1000000以下と書いてあるけど、そんなに大きくはならない。 下段を決めればピラミッドが一意に定まる。下段をx[0], x[1], ……, x[baseLength-1]、c[i] = Comb(baseLength-1,i)とすると…

Inequalitiesxの範囲が狭いので、xの値を変えて成り立つ不等号を数える。 #include <string> #include <vector> #include <sstream> #include <algorithm> using namespace std; class Inequalities { public: int maximumSubset( vector <string> inequalities ); }; int Inequalities::maximumSubset( v</string></algorithm></sstream></vector></string>…

RecursiveFigures #include <cmath> using namespace std; class RecursiveFigures { public: double getArea( int sideLength, int K ); }; double RecursiveFigures::getArea( int sideLength, int K ) { double PI = acos(-1.0); double l = sideLength; double </cmath>…

Easy (250) 219.89xを0.5刻みで動かしてたら、他の人はCを2倍にしていた。doubleでビクビクするよりそのほうが良いな。Medium (500) 0やられた、baseLengthは1Mまでと書いてあるけど解があるときはそんなに大きくならないのか。Hard (1000) 0見てない。結果 …

BouncingBallsボールを区別しなければ反射も透過も同じ動き、とTwitterに書いてあった。初期位置とT秒後の位置で左右が入れ替わっていれば、２つのボールは衝突している。 #include <vector> using namespace std; class BouncingBalls { public: double expectedBou</vector>…

Desertification #include <string> #include <vector> using namespace std; class Desertification { public: int desertArea( vector <string> island, int T ); }; int Desertification::desertArea( vector <string> island, int T ) { int h = (int)island.size(); int w = (int)island</string></string></vector></string>…

忙しかったので不参加。

NewCoinsDP。値段rの製品を1とp以上の価値のコインc枚で払えるならば、dをpの約数として、価値dのコインを加えればc-r%p/d*d+d枚のコインで払える。pで払いきれなかった余りr%pのうちr%p/d*dをd枚のコインで払えるので。 実行時間がちょっと怖い。私のプログ…

人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか30分くらい。 知らなければなかなか解けない問題だし仕事でこういうプログラム書くことは無いんだろうな、とは思う。 maze = open("input.txt","r").read().splitlines() w = len(maze[0]) h = …

TheTriangleBothDivs時計の表示を全て生成して、timeとの整合性を調べ、最小の時刻を返す。 #include <string> #include <stdio.h> using namespace std; class TheTriangleBothDivs { bool check( string t1, string t2 ); public: string fix( string time ); }; string The</stdio.h></string>…

Easy (250) 0"GMT-0"の排除を忘れてた。"00:00 GMT-?"という場合に"00:00"を返してしまう。Medium (500) 0a%n==b%nとなる組が7個の数字の中にいくつあるかだけに着目すれば良いと試合中に気付いたが時間切れ。Hard (1050) 0見てない。結果 1349 → 1314また0…

TheHexagonsDivTwo0≦t＜kを隣り合ったセルが異なるように配置する。それぞれの配置について、tが書かれたセルにはi%k=tとなる数字を置く場合の数を計算する。 #include <algorithm> using namespace std; class TheHexagonsDivTwo { long long put( int n, int k, int h</algorithm>…

TheSquareDivTwo #include <string> #include <vector> #include <algorithm> using namespace std; class TheSquareDivTwo { public: vector <string> solve( vector <string> board ); }; vector <string> TheSquareDivTwo::solve( vector <string> board ) { int n = (int)board.size(); vector<int> R; for ( int i=0; …</int></string></string></string></string></algorithm></vector></string>

TheHexagonsDivOne7個の数字を選びルールに従って配置するとき、a%n==b%nが成り立つ組が同数であれば並べ方の通りも同じである。例えばn=10のとき、{1,2,3,4,5,6,11}と{4,5,6,7,8,9,19}はa%n==b%nが成り立つ組が１つなので、どちらも並べ方は同数。 ↓のプロ…