C. Industrial Nimそれぞれのダンプの石の数の排他的論理和を計算し、0ならば後手が勝ち、0以外の場合は先手が勝つという定理がある。例えば問題文の最初の例はトラックの石の数が2, 3, 4で2^3^4=5≠0なので先手の勝ち。 今回はトラックの数が非常に多くなり…

ThirteenDiv1 Mediumとの違いは、経路上の任意の２駅間ではなく最初の駅からの任意の駅までの時間のみが13の倍数にならないこと。 駅の番号と、その駅に到達する時刻を13で割った余りを合わせて１つのノードとした最短経路問題。 #include <string> #include <vector> #inclu</vector></string>…

B. Laser2(移動可能な幅+1)(移動可能な高さ+1)のチョコレートが溶かされる。２つのレーザーが重なる場合にはその分を引く。 n = input() for i in range(n): n,m,x1,y1,x2,y2 = [int(x) for x in raw_input().split()] rx = n-abs(x1-x2) ry = m-abs(y1-y2) …

A. Cottage Village両端が他の家に接している場合を２重に数えないようにする。 n,t = [int(x) for x in raw_input().split()] h = [] for i in range(n): h += [[int(x) for x in raw_input().split()]] h.sort() c = 0 for i in range(n): if i == 0 or 2*…

サーバーが不安定でノーコンテスト。

EllysPlaylists動的計画法。長さkで最後の曲がiであるプレイリストの数をnum[k][i]とすると、 num[k][i] = num[k-1][j1] + num[k-1][j2] + ……。 ただし、j1, j2, ……はi番目の曲の先頭3文字と末尾3文字が一致する曲の番号。 #include <string> #include <vector> using namesp</vector></string>…

PrimeContainers class PrimeContainers { public: int containerSize( int N ); }; int PrimeContainers::containerSize( int N ) { int c = 0; for ( ; N>1; N/=2 ) { bool f = true; for ( int i=2; i*i<=N && f; i++ ) f = N % i != 0; if ( f ) c++; } …

ThirteenHard今3番目の駅に居るとして、 (T1+T2+T3)%13=a, (T2+T3)%13=b, (T3)%13=c, とすると、 (T1+T2+T3+T4)%13=(a+T4)%13, (T2+T3+T4)%13=(b+T4)%13, (T3+T4)%13=(c+T4)%13, である。 駅の番号と、各駅からその駅までの距離を13で割った余りのビット表現…

PrimeSequences問題文の通りに調べるだけ。素数かどうかの表さえ事前に計算しておけば充分間に合う。 #include <vector> using namespace std; class PrimeSequences { public: int getLargestGenerator( int N, int D ); }; int PrimeSequences::getLargestGenerato</vector>…

サーバーが落ちてノーコンテスト。残念。

ActivateGame貪欲にアクティブにしていけば良い。 プリム法 - Wikipedia #include <string> #include <vector> using namespace std; class ActivateGame { int number( char c ); public: int findMaxScore( vector <string> grid ); }; int ActivateGame::findMaxScore( vector <string> gr</string></string></vector></string>…

動的計画法。 i番目の囚人の位置をp[i]として、i番目の囚人とj番目の囚人を解放した後、i番目とj番目の間に居る囚人を解放するのに要するコインをcoin[i][j]とすると。coin[i][j] = mini

ホタルの初期位置と移動速度の平均が重心の初期位置と移動速度になる。 時刻tでの重心の距離を求めて、微分が０になるtがtmin。 ただし、重心が移動しない場合と、tminが負となる場合にはtmin=0。 T = input() for t in range(T): v = [0.0]*6 N = input() f…

先頭から順になるべく小さい数字を割り当て、割り当てた数字の個数を基数とする。 ただし、 先頭に0はダメ 基数は2以上、"1"という入力は2になる。 T = input() for t in range(T): m = raw_input() d = {} v = [] for c in m: if c not in d: d[c] = 1 if l…

LinearTravellingSalesman #include <vector> #include <algorithm> using namespace std; class LinearTravellingSalesman { public: int findMinimumDistance( vector <int> x, vector <int> y ); }; int LinearTravellingSalesman::findMinimumDistance( vector <int> x, vector <int> y ) { retu</int></int></int></int></algorithm></vector>…

DrawingLines既に引かれている線分同士の交点、既に引かれている線分とこれから引く線分の交点、これから引く線分同士の交点に分けて考える。既に引かれている線分の本数をmとする。 既に引かれている線分同士の交点数はO(m2)で求められる。 これから引く線…

DoorsGame最適戦略は、以下の順番。 自分の邪魔になっていて相手の邪魔になっていない色があるなら開く 自分にも相手にも邪魔になっている色があれば開く 自分にも相手にも邪魔になっていない色があれば開く 自分の邪魔になっていなくて相手の邪魔になってい…

Easy (250) 156.52 Medium (500) 235.51 Hard (1000) 0 Challenge +50 MediumでO(n2)の方がいたので最大ケースで撃墜。結果 1672 → 1827 最近調子が良い。

TheMoviesLevelTwoDivOne深さ優先探索。ある組み合わせの映画を観ることができるならば、どの順番で観ても以降の映画に影響が無いので、最初に現れた（辞書順最小の）ときのみ調べる。 #include <vector> #include <algorithm> using namespace std; class TheMoviesLevelTwoDiv</algorithm></vector>…

TheMoviesLevelOneDivOne並んで座れない席を数える。 #include <vector> #include <utility> #include <set> using namespace std; class TheMoviesLevelOneDivOne { public: long long find( int n, int m, vector <int> row, vector <int> seat ); }; long long TheMoviesLevelOneDivOne::f</int></int></set></utility></vector>…

TheMoviesLevelTwoDivTwo並べ方を全て試す。 #include <vector> #include <algorithm> using namespace std; class TheMoviesLevelTwoDivTwo { public: vector <int> find( vector <int> length, vector <int> scary ); }; vector <int> TheMoviesLevelTwoDivTwo::find( vector <int> length, vector <int> sca</int></int></int></int></int></int></algorithm></vector>…

TheMoviesLevelOneDivTwo #include <vector> using namespace std; class TheMoviesLevelOneDivTwo { public: int find( int n, int m, vector <int> row, vector <int> seat ); }; int TheMoviesLevelOneDivTwo::find( int n, int m, vector <int> row, vector <int> seat ) { vector<vector<bool> > </vector<bool></int></int></int></int></vector>…

旅行中のため不参加。