メモ化再帰するだけ。 #include <sstream> #include <vector> using namespace std; class ContestSchedule { public: int n; double cache[55]; vector<int> start; vector<int> end; vector<double> winExp; double rec(int lastContest) { double &r=cache[lastContest]; if(!(r<0)) return r</double></int></int></vector></sstream>…

class LotteryPyaterochka{ public: double chanceToWin(int N) { double n=N; return (10.0*(5*n-5)*(5*n-6)/2+5*(5*n-5)+1.0)*n*120/((5*n)*(5*n-1)*(5*n-2)*(5*n-3)*(5*n-4)); } };

axis-aligned box that contains all the object's squares #include <algorithm> #include <sstream> #include <string> #include <stack> #include <utility> #include <vector> #include <iostream> using namespace std; class PlayerExtraction { public: int bottom,ceil,left,right,S,h,w,k; vector<string> photo; …</string></iostream></vector></utility></stack></string></sstream></algorithm>

最短距離＝BFS #include <algorithm> #include <cstring> #include <map> #include <queue> #include <string> #include <vector> #include <iostream> using namespace std; class CornersGame { public: int cache[36][36][36][36]; int countMoves(vector<string> board) { memset(cache,-1,sizeof(cache)); int mv[4][2]={{0…</string></iostream></vector></string></queue></map></cstring></algorithm>

０：何種類の数字を使うか決める １：二個つかう数字の余りを決める（組み合わせを求める） ２：一個使う数字の余りを決める（同上） ３：一個使う方は大きい方を使うか小さい方を使うかがある #include <algorithm> #include <cstring> typedef long long LL; using namespace s</cstring></algorithm>…

メモ化再帰すればいい。 だけど、 rec(m,b,o)でm=oかつm=unitsPerRoundな状態になると無限ループするので、途中で中断するように if(r==-3) return r=(1<<28); r--; を入れておいた。 #include <algorithm> #include <cstring> using namespace std; class BarracksEasy { public</cstring></algorithm>…

差を保存するところまでは思いついたのに、残念。 #include <cstring> #include <vector> #define TOWER_MAX 250000 using namespace std; class EqualTowers { public: int n; vector<int> bricks; int cache[TOWER_MAX+1][50]; int rec(int dif,int k) { if((k==n && dif!=0) || </int></vector></cstring>…

全探索で大丈夫だけど、 かなりTLEしやすいので引数をグローバルにしたりして定数項を落とさないといけない。 メモ化したほうがいい。 #include <string> #include <vector> #include <iostream> using namespace std; class Mafia { public: int n,mine; int responses[16][16]; vector<int></int></iostream></vector></string>…

分からない上に、公式の解説がないので諦める。

DPではない。 最初の行と最初の列だけビットで全探索すればあとは左上を見るだけで全部決められる。 #include <string> #include <vector> using namespace std; class LightedPanels { public: int h,w; vector<string> board,tmp; int popCount(int _mask) { int r=0; for(int i=0;i</string></vector></string>…

５時間かかったorz #include <sstream> #include <string> #include <vector> using namespace std; class IncompleteBST { public: char tree[(1<<20)]; bool rec(int cur,char bottom,char ceil) { if((1<<20)<=cur || tree[cur]=='#') return true; if(tree[cur]</vector></string></sstream>

意味わかんない。階乗/2…why。 Login - TopCoder Wiki ↑に解説が書いてあるのだろうけどもう気力がマイナス。分かったから解説してみる。 マスが５個の場合： こんなふうに互いに交換可能なマスを一列に並べて番号をつける。 ４番のところと０、１，２，３は…

どの人が食べられるケーキにするかをビットで管理して全探索する。 #include <algorithm> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; class BirthdayCake { public: set<string> fruit; int s2i(string s) { return (int)distance(fruit.begin(),fruit.find</string></vector></string></sstream></set></algorithm>…

無向グラフだからUNIONFINDで連結成分を分解できる。 後、テストケース３の {"1 2,2 3,3 4,4 5,5 3,1 3,6 7,7 8,6 8,8 9,9 1",←ここと ここが→ "0,10 11,11 9,12 13,14 15,15 16,16 17,14 17,14 16"} つながって10になる #include <cstring> #include <sstream> #include <string> #inc</string></sstream></cstring>…

図を書いて１つ１つ考えれば難しくない。 …3回くらいresubmitしたけどね。 #include <algorithm> #include <vector> using namespace std; class MostLikely { public: int likelyRank(vector <int> sc, int low, int high) { vector<int> rank(55,0); sc.push_back(1000000000+1); sc.pus</int></int></vector></algorithm>…

点数が高い順にソートして貪欲に取っていけばOK。 pair使うのが面倒だったのでバブルソートしてみた。 #include <algorithm> #include <string> #include <vector> using namespace std; class PalindromeGame { public: int getMaximum(vector <string> front, vector <int> back) { int n=front.siz</int></string></vector></string></algorithm>…

難しい。分からん。 if(happiness[now]==-3) return now; でなんで-3なのかの自分なりのイメージ図。 #include <algorithm> #include <cstring> #define LIMIT 5000000 typedef long long LL; using namespace std; class ExtendedHappyNumbers { public: int K; int happiness[L</cstring></algorithm>…

ソース31行目以降の説明 if(numbers[j]+numbers[j+1]<numbers[j+1]+numbers[j]) swap(numbers[j],numbers[j+1]); ↑の理由 97799999と999とか前の部分(977と999）が等しくない場合 ーーーーー明らかに999のほうが前 33355555と333とか前の部分(333)が等しい場合 ーーーーー並べ方は２通りしかないんだから試せばいい バブルソートっていうところがミソ分からなかったんだけどTopCoder Statisticsで分かった #include <algorithm> #include </numbers[j+1]+numbers[j])>

幾何＋DP。 問題文見て「あ、幾何や。やめとこ。」と思い、すぐに解説を探したけど幾何の部分も大したことはなかった。 DPも大したことはないけど、１点だけ注意が必要。 それは頂点[0]と頂点[n-1]は隣り合っているので同時に使ってはいけないという点。 参…

メモ化再帰。 rec(残っているマーブル、今使っているバッグの残り容量、まだ使っていないバッグ）をメモ化。 #include <cstring> #include <vector> using namespace std; class CollectingMarbles { public: int m,bC; vector<int> mW; int cache[(1<<13)][21][10]; int rec(int m</int></vector></cstring>…

メモ化再帰するだけ。 rec(s)でs以降のデータを送るときの最小のパケット数を求める。 実際はオフセットデータも送らないといけなんじゃね。 #include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <vector> #include <utility> typedef long long LL; using namespace std; clas</utility></vector></cstring></cstdio></climits></algorithm>…

一応ACするけど、すごく頭の悪いコード。 practice roomのrngさんのコードを見たほうがいいと思う。 でも一応解説。 １：まずマスの１つ１つを頂点としてグラフを作る。 ２：このとき隣接リストで持たないとTLEする。（理由：各頂点から出る枝は多くても４本…

全探索。 a,c,i,n,tは必ず学ばなければならないので別にして、他の文字はbitで探索。 ACRushさんは for(int set=mask;1;set=(set-1)&mask) って書いてた、賢い。 #include <string> #include <vector> using namespace std; class Teaching { public: int popCount(int n) { </vector></string>…

久しぶりに１発で通した。 4000*4000のメモリーは確保できないのでうまいこと節約しませう。 #include <algorithm> using namespace std; class MarblesInABag { public: double DP[2][4000+1]; double getProbability(int redCount, int blueCount) { for(int R=0;R<=r</algorithm>…

えらく簡単だった。 0 #include <string> #include <vector> using namespace std; class Squares { public: int countSquares(vector <string> field) { int ans=0,h=field[0].size(),w=field.size(),n=55; for(int x1=0;x1</string></vector></string>

惜しかった。もうちょっと粘れば正解にたどり着けたかもしれない。 わからなかったのはこの部分 for(int next=startIndex.back()+1;0<=left-next && next<=(length-left+1);next++) この文があると左から埋めていったときに穴ができる可能性を減らせるから。…

全く歯が立たない。 探索だった。div2hardで初めて見た。 藪から棒だ。亀も木から落ちる。 #include <cmath> class SumAndProduct { public: int smallestSet(int S, int P) { if(S==P) return 1; double s=S,p=P; for(int n=2;n<=100;n++) if(p</cmath>

最小全域木を求める。 存在しなかったら空のvectorを返す。 存在したら道の本数がMになるまで付け足す。 UNIONFINDのコードはコピーしたので集合のサイズを求める機能が付いてる。 #include <utility> #include <set> #include <vector> #include <algorithm> #include <string> using namespace std; </string></algorithm></vector></set></utility>…

愚直にレシピをn^2回更新すればよい。 #include <iostream> #include <map> #include <sstream> #include <string> #include <vector> typedef long long LL; using namespace std; class MakingPotions { public: int getCost(vector <string> marketGoods, vector <int> cost, vector <string> recipes) { int n=recipes.</string></int></string></vector></string></sstream></map></iostream>…

nCrはパスカルの三角形で求められる。 あとオーバーフローするので C[i][j]=min(k+1,C[i-1][j]+C[i][j-1]); としなくてはならない。 #include <string> typedef long long LL; using namespace std; class TheDictionary { public: LL C[110][110]; string find(int </string>…