2011-04-01から1日間の記事一覧

SRM304 div2 hard

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

SRM397 div2 hard

メモ化再帰。 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>…

SRM367 div2 hard

メモ化再帰するだけ。 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>…

SRM368 div2 hard

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

SRM427 div2 hard

全探索。 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>…

SRM408 div2 hard

久しぶりに1発で通した。 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>…

SRM332 div2 hard

えらく簡単だった。 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>

SRM405 div2 hard

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