頑張った。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>…

メモ化再帰。 数字の処理がややこしい＋コピペミスで150点。 #include <algorithm> #include <cstring> using namespace std; typedef long long LL; class NumbersAndMatches { public: int len; int number[20]; int addMatch[10][10]; int moveMatch[10][10]; LL cache[20][30</cstring></algorithm>…

桁ごとに考えて足すだけ。 typedef long long LL; LL S(LL num) { num++; LL r=0; for(LL digit=0,i=10;digit<15;digit++,i*=10) { LL l=num; r+=l/i*45*(i/10); l%=i; for(LL j=0;0

実装。 ”starting with the note that has the highest pitch , then the note with the second -highest pitch , and so on .” この文を見逃したので時間がかかった。 #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; class StringsAndTabs </vector></string></iostream></algorithm>…

昇順にソートすると簡単になる。 rec(今何番目のサイコロ、最低でも出さなければいけない目)をメモ化。 #include <algorithm> #include <cstring> #include <vector> typedef long long LL; using namespace std; class DiceGames { public: int n; LL cache[50][50]; vector<int> sides; LL r</int></vector></cstring></algorithm>…

最初のarray[a]=xとする xがarray[a]にあるか、それ以外にあるかで確率を保持する。 一度swapするたびに １：array[a]==xのとき xが選ばれない確率は(nC2-n+1)/nC2 xが選ばれる確率は(n-1)/nC2 ２：array[a]!=xのとき xがarray[a]に移動する確率は1/nC2 xがa…

ここより先に見たほうがいいところ： SRM467 - cafelier@SRM - TopCoder部 Login - TopCoder Wiki - 解けなかった。 だからSuperSum(n,k)は で表を変形して こうなる。 だから答えは n+kCk+1 あとMODのライブラリはcafelierさんを丸パクリ参考にさせていただ…