PerfectSequences各要素を書き換えてperfect sequenceにできるかどうか調べる。 #include <vector> #include <string> using namespace std; class PerfectSequences{public: string fixIt( vector <int> seq ) { int n = (int)seq.size(); if ( n == 1 ) return "Yes"; for ( int</int></string></vector>…

SentenceCapitalizerInator #include <string> #include <cstdlib> using namespace std; class SentenceCapitalizerInator{public: string fixCaps( string paragraph ) { paragraph[0] = toupper(paragraph[0]); for ( int i=2; i<(int)paragraph.length(); i++ ) if ( para</cstdlib></string>…

SetMultiples閾値Tより小さい値は１個ずつSに含まれるかどうかを調べる。閾値T以上の値は、[A,B], [C,D]の範囲から、[(A+1)/2,B/2],[(C+1)/2,D/2],[(A+2)/3,B/3],[(C+2)/3,D/3],……,[(A+k-1)/k,B/k],[(C+k-1)/k,D/k]を除いた範囲の長さを調べる。T以上と[A,B]…

CubeRollスタートとゴールの間に穴があったら到達不可能。スタート・ゴールの両側に穴があったら、立方体の移動範囲は狭いので、動的計画法。それ以外の場合はスタートとゴールの距離に着目する。距離が平方数なら１手。距離が平方数の和なら２手。距離が平…

CubeAnts #include <vector> using namespace std; class CubeAnts{public: int getMinimumSteps( vector <int> pos ) { int D[] = { 0, 1, 2, 1, 1, 2, 3, 2 }; int ans = 0; for ( int i=0; i<(int)pos.size(); i++ ) ans = max( ans, D[pos[i]] ); return ans; }};</int></vector>

CubePacking幅＜高さ＜奥行き として、幅と高さを全探索。間に合う。幅と高さをどちらもLにすれば、ceil(総体積/(L*L))の立方体には収まるので、答えはそれ以下。 #include <algorithm> using namespace std; class CubePacking{public: int getMinimumVolume( int Ns, </algorithm>…

CubeStickers同じ色は２回まで使える。順番も関係無いので、２回までで取っていって、取れるかどうか。 #include <string> #include <vector> #include <map> using namespace std; class CubeStickers{public: string isPossible( vector <string> sticker ) { map<string,int> F; for ( int i=0; i<6</string,int></string></map></vector></string>…

Easy (250) 228.26 Medium (500) 159.71（再提出） Hard (1000) 0 Challenge +50 結果 1853 → 1927500は、w≦Nb*L+αくらいまでしか探索していなくて再提出。痛いけどミスに気付けただけマシか。

SlimeXResidentSlimeスライムが10匹以上ならクリアは不可能。スライムが9匹以下ならば事前に距離を求めておくことで、順番を全通り試すことができる。問題文中のプレイヤーが死んだスライムの上に乗るとスライムが生き返るという記述は、その直後に改めてス…

ComplementMachine2D 00 01 01 11このようになっていたら、この４マス全部が消去可能な部分マトリックスに含まれることはない。各部分マトリックスについて、このような４マスを含まないかどうか調べる。 #include <string> #include <vector> using namespace std; class Co</vector></string>…

CoinMachinesGameneed[i]-give[i]が小さいマシンから順に使っていけば良い。 #include <vector> using namespace std; class CoinMachinesGame{public: int maxGames( int coins, vector <int> need, vector <int> give ) { int n = (int)need.size(); int ans = 0; while ( tr</int></int></vector>…

AllButOneDivisor11*12*13*14*15=360360。ここまで調べれば充分。全探索しても間に合う。 #include <vector> using namespace std; class AllButOneDivisor{public: int getMinimum( vector <int> divisors ) { int K = (int)divisors.size(); for ( int i=0; i<=360360; </int></vector>…

SlimeXGrandSlimeAutoそれぞれの車をどの移動に使うかという割り当て問題。最小費用流で解ける。 #include <string> #include <vector> using namespace std; // 全点対間最短路（Warshall-Floyd法） vector<vector<int> >warshall_floyd(vector<vector<int> >E) { int n=(int)E.size(); for(int i=0;i</vector<int></vector<int></vector></string>

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

http://www.topcoder.com/stat?c=problem_statement&pm=11372:FoxIntegerLevelThreed(n) = (n-1)%9+1であるから、xはrepresentable ⇔ x/kがkの倍数となるようなk(1≦k≦9)が存在する。gcd(1*1,2*2,……,9*9) = 6350400なので、xがrepresentableかどうかは6350400…

Revenge of the Hot Dogs位置PにV個のホットドッグ屋がある時、それらを間隔Dで並べてさらに他のグループとも間隔Dなので、V*Dの幅の板を重ならないように、かつなるべく元の位置から動かさないように敷き詰めるイメージ。秒数が与えられたなら、なるべく左…

RPI問題文の通りに実装。OWPは相手のWPのうち自分との試合の分を除く必要がある。 T = input() for case in range(T): N = input() A = [raw_input() for i in range(N)] WP = [0.0]*N C = [0]*N for i in range(N): for j in range(N): if A[i][j]!=".": C[…

A small large B small large B small を通して、75点、122位。Round2進出(`･ω･´)

KindAndCruel動的計画法。それぞれの位置に到達可能かどうかを覚えておく。同じ位置にK*C秒後に居ても意味は無いので、K*Cで少なくとも１マスは進むはず。K*C*n秒後にも右端に到達できなければ到達不可。 #include <string> #include <vector> using namespace std; class Ki</vector></string>…

BlackWhiteMagicWの個数をwとして、creatures[0..w]に含まれるBの個数をcとすると、少なくともc回は交換が必要。位置が間違っているものを、ソート後のWとBの境目に近いものから順に交換していけば、c回でソート可能。 #include <string> #include <algorithm> using namespace </algorithm></string>…

TheTicketsDivTwo動的計画法。列の人数とm番目の友人の位置ごとに確率を覚えておく。 class TheTicketsDivTwo{public: double find( int n, int m, int k ) { // [ダイスを投げた回数][列の人数][m番目の人の位置] double T[11][11][11] = {{{0}}}; T[0][n][…

TheJackpotDivTwo #include <vector> #include <algorithm> using namespace std; class TheJackpotDivTwo{public: vector <int> find( vector <int> money, int jackpot ) { for ( int i=0; i</int></int></algorithm></vector>

TheJackpotDivOne全員が同じ金額になったら1ドルずつ配るだけなので、まとめて計算できる。全員の金額の合計はlong longに収まりきれないので対策が必要。人数をnとして、nで割った商と余りで計算するとか。Javaを覚えるか多倍長整数クラスを用意するべきな…

TheNumbersWithLuckyLastDigit1の位が4と7の数を何個足し合わせるかを考える。10以上の位は適当に辻褄を合わせられる。ただし、4と7を加えてnを超える場合は無理。 #include <algorithm> using namespace std; class TheNumbersWithLuckyLastDigit{public: int find( in</algorithm>…

不参加。

SquareSeries?以降の部分から逆算して?の部分の最後の正方形の色ごとに必要なサイズを求める。あるサイズ・色の正方形を得るの辞書順最小の系列を覚えておき、動的計画法。 #include <string> #include <vector> using namespace std; class SquareSeries{public: string com</vector></string>…

FoxListeningToMusic時刻ごとに曲が終わる確率を動的計画法で求め、t秒後にT-tより長い曲が選ばれる確率を足し合わせる。 #include <vector> using namespace std; class FoxListeningToMusic{public: vector <double> getProbabilities( vector <int> length, int T ) { int n = </int></double></vector>…

MinimumLiars嘘つきの人数を0〜N人で仮定してみて妥当かどうかを調べる。無理なら-1を返す。 #include <vector> using namespace std; class MinimumLiars{public: int getMinimum( vector <int> claim ) { int N = (int)claim.size(); for ( int i=0; i<=N; i++ ) { int </int></vector>…

Easy (250) 243.35 Medium (600) 416.16 Hard (1000) 0 Challenge 0 結果 1784 → 1853予選突破(`･ω･´)

SlimeXSlimeRancher2 #include <vector> #include <numeric> #include <algorithm> using namespace std; class SlimeXSlimeRancher2{public: int train( vector <int> a ) { return *max_element(a.begin(),a.end())*(int)a.size() - accumulate(a.begin(),a.end(),0); }};</int></algorithm></numeric></vector>