Gifts贈り物・王・王妃の間の最短距離を予め求めておく。位置と持っている贈り物を状態として、動的計画法。ある地点xで贈り物を拾わない場合は、xを通らなかったとみなせる。 #include <string> #include <vector> using namespace std; class Gifts { int countbit( int n </vector></string>…

RoadOrFlightHard動的計画法。何回離陸したかと直前が陸路か空路か、それぞれの最小所要時間を記憶しておく。 #include <vector> #include <algorithm> #include <limits> using namespace std; class RoadOrFlightHard { public: long long minTime( int N, int roadFirst, int roadPro</limits></algorithm></vector>…

T9辞書のサイズが小さいので、辞書内の単語それぞれについて与えられたキーストロークの数字部分で入力できるか調べる。 #include <string> #include <vector> #include <numeric> #include <algorithm> using namespace std; class T9 { public: string message( vector <string> part, vector <string> dict, ve</string></string></algorithm></numeric></vector></string>…

RoadOrFlightEasy #include <vector> #include <numeric> #include <algorithm> #include <functional> using namespace std; class RoadOrFlightEasy { public: int minTime( int N, vector <int> roadTime, vector <int> flightTime, int K ); }; int RoadOrFlightEasy::minTime( int N, vector <int> roadTime, ve</int></int></int></functional></algorithm></numeric></vector>…

Easy (250) 122.27 辞書をソートすることに気づかずに、悩んだのが痛い。Medium (500) 317.96 Hard (1000) 0 challenge 0結果 1580 → 1672

MazeOnFire火と同じようにキャラクタを増殖させて、キャラクタが居なくなったステップを返す。キャラクタが生存していて状態が変化しなくなったら、キャラクタは死なない。 #include <string> #include <vector> using namespace std; class MazeOnFire { vector<string> propagate( </string></vector></string>…

オンライン整数列大辞典に訊いたところ、n+kCk+1だった。 Javaを覚えるか、多倍長整数のライブラリを準備しておくかしないと、この手の問題を戦えない……。追記： 法が素数の場合は除算もできるらしい。知らなかった。SRM467 - cafelier@SRM - TopCoder部 #in…

LateProfessor教授がlateTime未満の遅れなら許容するというのは、教授が遅れを全く認めなくてJohnがlateTime早く返ってくるということと同じ。教授が来る可能性がある時間帯のうちJohnが居ない時間を求める。Johnは同じ行動を繰り返すので、waitTime+walkTim…

ShorterSuperSum #include <numeric> using namespace std; class ShorterSuperSum { public: int calculate( int k, int n ); }; int ShorterSuperSum::calculate( int k, int n ) { int SS[15][15]; for ( int i=0; i<=k; i++ ) for ( int j=1; j<=n; j++ ) SS[i][j</numeric>…

寝坊した。

Obsession with RobotsRRUULLDでもBUGと返さなければいけない。スタート地点から１つ上に行けばゴール地点。 path = raw_input() pos = (0,0) visit = set() visit.add(pos) for c in path: if c == "L": t = (pos[0]+1,pos[1]) if c == "R": t = (pos[0]-1,…

Train and Peter import re x = raw_input() y = raw_input() z = raw_input() m1 = re.search(y+".*"+z,x) m2 = re.search(z[::-1]+".*"+y[::-1],x) if m1 and not m2: print "forward" if not m1 and m2: print "backward" if m1 and m2: print "both" if …

Aをノーミス、Bを1ミスで解いて、レーティング1622。

Theater Square n,m,a = [int(x) for x in raw_input().split()] print ((n+a-1)/a)*((m+a-1)/a)

IdealString #include <string> #include <numeric> using namespace std; class IdealString { string BT( int length, string w ); public: string construct( int length ); }; string IdealString::construct( int length ) { return BT( length, "" ); } string IdealStr</numeric></string>…

makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズはてなブックマークの１行に書けるように短くしてみた。100文字とあるけど半角なら300文字までいける。 x=256,y=65793;char*t,s[99];f(i…

makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズこの問題に挑戦してみた。１時間くらい

MatrixGame行の交換と列の交換は独立している。任意の回数交換して良いので、任意の並べ替えができる。幅と高さが最大8なので並べ替えは高々40320通り。 列の並び替えを全て試して、行を辞書順に整列。得られた行列のうち辞書順最小のものを返す。 #include <string></string>…

LotteryPyaterochka1〜5がwinning numbersと仮定しても結果は変らない。1〜5の全ての並べ方のうち、少なくとも3つが同じ行に含まれる場合が何通りか考える。1〜5の全ての並べ方は5NC5。 5つ全部が同じ行に含まれる場合は、どの列かでN通り、1〜5の並べ方が5!…

LotteryCheatingたいていの数nはある整数pが約数なら、n/pも約数となるので、偶数個の約数を持つ。約数が奇数個となるのはnが平方数の場合のみ。この時はp=√nでp=n/pとなる。 10桁以下の平方数は105個しかない。 #include <string> #include <cstdio> using namespace std; c</cstdio></string>…

LotteryTicket #include <string> using namespace std; class LotteryTicket { public: string buy( int price, int b1, int b2, int b3, int b4 ); }; string LotteryTicket::buy( int price, int b1, int b2, int b3, int b4 ) { for ( int i=0; i<16; i++ ) if (</string>…

Easy (250) 190.17 Medium (500) 398.83 Hard (1000) 0 challenge -25結果 1439 → 1580黄色に戻った。同室だったrng_58氏が撃墜しまくっていた。もっと上に行くためには撃墜できなければ。

WeirdTimesi番目の時間をhとしたときにi+1番目以降の時間の選び方の数をCi,hとする。 Ci,h = Σj=h23Ci+1,j（分が進んでいる場合）, = Σj=h+123Ci+1,j（進んでいない場合） の動的計画法でCi,hが求まる。 最初の時間はΣi=0hC0,i≦K＜Σi=0h+1C0,iが成り立つよう…