解けなっかた人が解説しても仕方がないのでぐぐればいいと思うよ。 全探索。 #include <vector> using namespace std; class DrawingLines { public: double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) { vector<int> ceil(n,-1); int m=startDot.size</int></int></int></vector>…

全部一箇所に集めればいい。 マンハッタン距離ではxとyは分離できるので 集める場所のx座標の候補は初期位置のx座標 集める場所のy座標の候補は初期位置のy座標 で全探索。 #include <limits.h> using namespace std; class TournamentPlan { public: int ABS(int n) {</limits.h>…

TopCoder Statistics ↑のテキトー日本語訳 最終的にグラフはそれぞれに一つずつmarkedを含む部分グラフに分けられる。 markedな頂点A,B(AとBの間には他のmarkedな頂点はない)を考える。 AとBを分けるときに使う辺はAとBの間で最もコストの小さい辺である。 #…

map,得点>でメモ化再帰。 どちらの番かという情報は”どの頂点が残っている”から得ることができる。 #include <map> #include <vector> #include <float.h> #include <cmath> using namespace std; int n; double point[(1<<13)]; map<int,double> cache; int popCount(int _mask) { int r=0; for(int i</int,double></cmath></float.h></vector></map>…

一番高いビルから入れていく。 一番左に入れると左から見えるビルが一つ増える。 一番右に入れると右から見えるビルが一つ増える。 それ以外の場所に入れても見えるビルは増えない。 #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL cac</cstring></cstdio>…

何個のサイコロがvを出すかの組み合わせで分ける #include <algorithm> using namespace std; double cache[2500+10][50+10]; class Conditional { public: int v; int maxSide; double C[55][55]; double rec(int sum,int nD) { if(sum<=0) return 1.0; else if(nD==0)</algorithm>…

分からへんかった。 class MagicalSpheres { public: int count(int n,int p) { int r=0; while(n>1) { r+=n/p; n/=p; } return r; } bool check(int s,int f,int g) { for(int i=2;1

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

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