srm div.1 デビュー戦 while 中間テスト
Opened Unopened Unopened
0.0pt 339th(?)
1239 -> 1246 (+7) (Highest)
誤差とはまさにこのことなり
デビュー戦が275点問題で自動レート上昇ってどうなのよ…
SRM557 Div.1Easy
リハビリにちょっと。
単純問題だったけどさすがに頭なまってて一発ACできなかった
class FoxAndMountainEasy { public: string possible( int n, int h0, int hn, string history ) { string yes="YES", no="NO"; int hl = history.length(); int cm = n - hl; int minmove = 100001, move = 0; for (int i=0; i<hl; i++) { if (history[i] == 'U') { move++; } else { move--; minmove = min(minmove, move); } } // i歩は上に行った時 for (int i=0; i<=cm; i++) { if (h0+i+move<0||h0+i+minmove<0) continue; int hnext = i - (cm - i) + move; if (h0 + hnext == hn) return yes; } return no; } };
SRM558Div.1Easy
DPくさくて、DPで、しかも考え方が複雑すぎるDP。
辿りつけなかった…
ちなみにがんばってDPじゃなく解こうとした爪あとが以下
class Stamp { public: string dc; vector<P> vc; int sc, pc, code[50]; int getMinimumCost( string desiredColor, int stampCost, int pushCost ) { int n = desiredColor.length(); dc = desiredColor; sc = stampCost; pc = pushCost; bool flag = false; for (int i=0; i<n; i++) { if (dc[i] == 'R') code[i] = 0; else if (dc[i] == 'G') code[i] = 1; else if (dc[i] == 'B') code[i] = 2; else { code[i] = -1; flag = true; } } vec.push_back(P(code[0], 1)); int mcost = INT_MAX; for (int i=1; i<n; i++) { if (vec[vec.size()-1].first==code[i]) vec[vec.size()-1].second++; else { mcost = min(mcost, vec[vec.size()-1].second); vec.push_back(P(code[i], 1)); } } int res = INT_MAX; if (flag) { deque<P> deq; for (int i=0; i<vec.size(); i++) deq.push_back(vec[i]); while (deq.size()>1&&deq[0].first==-1) { deq[1].second += deq[0].second; deq.pop_front(); } while (deq.size()>1&&deq[deq.size()-1].first==-1) { deq[deq.size()-1].second += deq[deq.size()-2].second; deq.pop_back(); } for (int i=1; i<=n; i++) { int cnt = 0; for (int j=0; j<deq.size(); j++) { if (deq[j].first!=-1) { cnt += deq[j].second / i; int x = i - deq[j].second % i; deq[j].second = x; } } vector<P> vec2; vec2.push_back(P(deq[0].first==-1, deq[0].second)); for (int j=1; j<deq.size(); j++) { if (vec2[vec2.size()-1] == (deq[j].first==-1)) vec2[vec2.size()-1] += deq[j].second; else vec2.push_back(P(deq[j].first==-1, deq[j].second)); } vec2. } return res; } else { for (int i=1; i<=mcost; i++) { int cost = i * sc; for (int j=0; j<vec.size(); j++) { cost += ((vec[j].second+i-1)/i * pc); } res = min(res, cost); } return res; } } };
雑多なこと
今日はテストがとてーも楽で、なんか気が抜けて色々やってました。
あんま自由な時間ってもう持てないしUbuntu12.10にアップグレードしてみたりしてたんだけども…
terminatorとcinnamonが使えなくなっててちょっと残念。。。
もうちょい整備しないとあれですね、使いにくい。
あとrepository弄ってるからかなんか変なふうに…
あぁ・・・Webアプリ作ってみたい・・・
大学入ってから(そのころには時代遅れになってる可能性大w