ステージ１： ４番を爆破したとする。すると１番も開けることができる。 このような連鎖関係で箱を分ける。 このグループの数が爆弾の数より少ないならすべての箱を開けることができる。 そのようになる箱の分け方の場合の数を求めて(箱の数)!で割ればいい。…

rec(直前の色、直前の色は何個続いたか、Aの個数、Bの個数、Cの個数)をメモ化再帰。 場所は全体の長さ-(Aの個数+Bの個数+Cの個数)で求められる。 #include <algorithm> #include <vector> using namespace std; int cache[3][4][50+10][50+10][50+10]; class BoxesArrangement {</vector></algorithm>…

解説見ました。 Login - TopCoder Wiki class PuyoPuyo { public: int theCount(int L, int N) { memset(DP,0,sizeof(DP)); DP[0][0]=1; for(int i=0;i

無理やり感が否めない。基本的にシンボルとパターンを総当りでぶつけていく。 でも、どの電球が生きているのかはパターンすべての中で一回でもついたことのある電球だけ。 パターンiとシンボルjをぶつけるときに、 パターン[i][k]=='1' && シンボル[j][k]=='…

cache[y][x][何個訪れた][最後に訪れた番号]でメモ化再帰。 #include <cstring> #include <vector> #include <cstdio> using namespace std; int field[60][60]; int cache[60][60][60][60]; class CountPaths { public: int rec(int y,int x,int v,int l) { if(y<1 || x<1 || v<0) re</cstdio></vector></cstring>…

めんどくさい。 #include <queue> #include <string> #include <vector> using namespace std; class FixImage { public: int h,w; int image[60][60]; int color() { for(int i=0;i</vector></string></queue>

頑張った。long long をintに変えるとちょっと実行時間が短くなる。 #include <vector> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; int offset=8; int cache[17+5][(1<<17)]; class HexagonalBattlefield { public: int N; int field[17+5][17</cstring></cstdio></vector>…

なんかそんなに状態ないんじゃねと思ってメモ化した。 rng_58さんのコードを見るとAが10以上のときは0らしい。 #include <map> typedef long long LL; using namespace std; class MegaCoolNumbers { public: int N,A; map<LL,LL> cache; LL rec(int pos,int diff,int gr</ll,ll></map>…

どっかでやったことがあるような気がする。 メモ化再帰。 #include <vector> #include <map> using namespace std; class QuickSort { public: map<vector<int>,double> cache; double rec(vector<int> L) { double r; if(L.size()<2) r=0.0; else if(cache.find(L)!=cache.end()) return c</int></vector<int></map></vector>…

しんどい。 やることはただのBFS。でも状態をmapでメモしとかないと無限ループに落ちる。 #include <string> #include <vector> #include <queue> #include <map> using namespace std; int mv[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; class PiecesMover { public: int nP; bool check(vector<int></int></map></queue></vector></string>…

頭がDPでこちこちになってた。 #include <vector> using namespace std; class CandyBox { public: vector <double> expectedScore(int C, vector <int> score, int S) { int n=score.size(); vector<double> ans(score.begin(),score.end()); for(int time=0;time<S;time++) { vector<double> tmp=ans; for(int i=0;i</s;time++)></double></int></double></vector>

ACRushさすが。 #include <set> #include <vector> typedef long long LL; using namespace std; class ConstructBST { public: int n; LL ans; LL C[30][30]; set<int> se; int rec(int pos) { if(se.find(pos)==se.end()) return 0; else { int left=rec(pos*2); int right=r</int></vector></set>…

お金が500しかないところがなんだかDP臭いのでDPだろうと思って考える。 だいたい出来るけど11の倍数っていう制約が厄介。 "11の倍数"で検索すると a*1000+b*100+c*10+dという数(a,b,c,dは９以下)があったとき (a-b+c-d)%11==0なら11の倍数らしい。 それ分か…

ワーシャルフロイドして一番長い２点間最短距離を返せばOK。 #include <vector> using namespace std; int chain[50+10][50+10]; class EscapingJail { public: int n; int getMaxDistance(vector <string> _chain) { n=_chain.size(); for(int i=0;i</string></vector>

rec(0)=(rec(1)+cells[1]+......+rec(6)+cell[6])/6 rec(1)=(rec(2)+cells[2]+......+rec(7)+cell[7])/6 のような連立方程式を解けばいいのは分かったのだけど、そんなの分からない。というわけで別の方法を考えた。 再帰の深さが１増えるたびに1/6されるか…

動物的直感でAC。 #include <algorithm> #include <cstdio> #include <cstring> #include <utility> #include <vector> using namespace std; class IntervalSubsets { public: int n; int cache[55]; vector<pair<int,int> > interval; int rec(int p) { int &r=cache[p]; if(r!=-1) return r; else { r=0; int ss=inter</pair<int,int></vector></utility></cstring></cstdio></algorithm>…

40^5でDP。 #include <vector> using namespace std; double DPJ[40+10][40+10][40*40+10]; double DPB[40+10][40+10][40*40+10]; class TheFansAndMeetingsDivOne { public: double find(vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB, int k) { int n=m</int></int></int></int></vector>…

一番下の列を決めたら全部決まる。 一番下の列の要素は{1,5,10,10,5,1}倍された和がtopに等しくなる。 これは二項係数。 じゃあナップサックできるじゃん。 ここでオーダーを下げきれずにTLE。 どの要素も正なのでbaseLengthがある程度大きくなったら弾いち…

#include <algorithm> #include <string> #include <vector> typedef long long LL; using namespace std; class PrefixFreeSubsets { public: LL cantPrefFreeSubsets(vector <string> words) { int n=words.size(); LL ans[60]; ans[n]=1; sort(words.begin(),words.end()); for(int i=n-1;0<=</string></vector></string></algorithm>…

テストケース見たら最大でも288通りしかないことがわかったので、深さ優先で全探索。 数字が埋まっていても数独としては成り立っていない場合を忘れ一回resubmit。 #include <string> #include <vector> using namespace std; class SillySudoku { public: vector<string> group; vec</string></vector></string>…

#define LIM 3500000 が大事。 3^6+9^6×6=3189375 なので範囲外アクセスを起こさない。 #include <cstring> #include <cstdio> #define LIM 3500000 typedef long long LL; using namespace std; LL cache[LIM]; class ExtendedHappyNumbers { public: int K; LL S(LL n) { LL</cstdio></cstring>…

ひどいソースだ。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> typedef long long LL; using namespace std; class IntegerPalindrome { public: LL findByIndex(int K) { LL t[30],u[30]; t[1]=t[2]=9; for(int i=3;i<30;i++) t[i]=t[i-2</cstdio></sstream></iostream></vector></string></algorithm>…

貪欲でOK。 usは小さい方からthemの大きい方と比較。 #include <algorithm> #include <vector> using namespace std; class ChessMatchup { public: int maximumScore(vector <int> us, vector <int> them) { int n=us.size(),ans=0; vector<int> usUsed(n,false); vector<int> themUsed(n,false); s</int></int></int></int></vector></algorithm>…

DP[r][b]=max(r-b,赤を引く確率*DP[r+1][b]+黒を引く確率*DP[r][b+1])でDP。 そのままメモリに取るとMLEするので、r+1またはb+1しかない性質を利用してメモリを節約。 #include <algorithm> using namespace std; class RedIsGood { public: double getProfit(int R, in</algorithm>…

map便利。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <map> typedef long long LL; using namespace std; int ABS(int n) { return (0<n)?n:-n; } class FoxStones { public: int getCount(int N, int M, vector <int> sx, vector <int> …</int></n)?n:-n;></map></cstdio></sstream></iostream></vector></string></algorithm>

ループの中にあるかどうかを調べて、あとは数えるだけ。 #include <string> #include <vector> #include <iostream> #include <sstream> #include <algorithm> #include <cstdio> using namespace std; class RoundAboutCircle { public: int loopSize[200010]; int nextCell[200010]; int DFS(int k) { if(loopSize</cstdio></algorithm></sstream></iostream></vector></string>…

#include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> using namespace std; class ToastXToast { public: int bake(vector <int> uT, vector <int> oT) { int n=uT.size(),m=oT.size(),i,j,ans=0; vector<int> uG(n,-1); vector<int> oG(m,-1); for(i=0;i…</int></int></int></int></cstdio></sstream></iostream></vector></string></algorithm>

タイプミスで落とす。 #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; class KingdomXCitiesandVillages { public: int n,m; double dist[100][100]; double determineLength(vector <int> cityX, vector <int> cityY, …</int></int></algorithm></cmath></cstdio></sstream></iostream></vector></string>

いまどのプラントが稼働しているかを状態としてダイクストラ。 #include <algorithm> #include <queue> #include <string> #include <vector> using namespace std; int popCount(int _mask) { int r=0; for(int i=0;i<28;i++) if(_mask & (1<</vector></string></queue></algorithm>

”DP[何ラウンド目][前に何ドルかけた（※）][今何ドル持っている]＝確率”でDP。 ※２の指数、前に勝った場合は10とした。 #include <cmath> class TestBettingStrategy { public: double DP[55][11][2010]; double winProbability(int initSum, int goalSum, int roun</cmath>…