メモ化再帰。 数字の処理がややこしい＋コピペミスで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さんを丸パクリ参考にさせていただ…

メモ化再帰するだけ。 #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 ↑に解説が書いてあるのだろうけどもう気力がマイナス。分かったから解説してみる。 マスが５個の場合： こんなふうに互いに交換可能なマスを一列に並べて番号をつける。 ４番のところと０、１，２，３は…

下手ですみません #!/bin/bash #solved_probrem.sh for f in `find . -name "*.cpp" | grep SRM` do dir=`echo $f | sed -e 's:.*SRM\(.*\)/\(.*\)[.]cpp:\1-\2:'` cla=`cat $f | grep class | sed -e 's:class *\([[:alpha:]]*\)[ {]*:\1:' | sed -n '$p'` …

どの人が食べられるケーキにするかをビットで管理して全探索する。 #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>…

「"+y」ーーーーー*じゃないって:h clipboardに書いてあった

図を書いて１つ１つ考えれば難しくない。 …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]は隣り合っているので同時に使ってはいけないという点。 参…