SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2012-05-13TCO2012 Round2B
- 300:201.68, 550:255.68, 900:Opened, score:457.36, rank:135, rating:2312(+38)
- 解くのが遅すぎる
- 後100点くらい足りなかった。精進が必要
TCO2012 Round2B 300 BlurredDartboard
TopCoder Open | |
コーディングフェーズ
300とか嫌な予感しかしない
と思ったが珍しくやるだけの予感
見えてる中で最高得点の的と見えない的の平均値で比較していい方を採用する
見えない方は最後の余りは平均でなく小さい方から選ぶことになることに注意する
書いた
例外が発生しました: Integer division by zero
サンプル親切・・・!
直した
合わない
やっぱ300だしこんな単純じゃなかった?/(^o^)\ナンテコッタイ
分からん
デバッガ起動
添字誤りだった
本当につまらないミスが多い・・・
提出
ソースコード
class BlurredDartboard { public: int minThrows(vector <int> points, int P) { int res; int n=points.size(); int maxscore=0; for(int i=0; i<n; i++) maxscore=max(maxscore, points[i]); if(maxscore>0) res=(P+maxscore-1)/maxscore; else res=1000000001; int zerocnt=0; vector <int> zero; int used[52]={0}; for(int i=0; i<n; i++) if(points[i]) used[points[i]]=1; for(int i=1; i<=n; i++) if(!used[i]) zero.push_back(i); zerocnt=zero.size(); if(zerocnt>0) { int tot=0; for(int i=0; i<zerocnt; i++) tot+=zero[i]; int tres=P/tot*zerocnt; int rem=P%tot; int inc1=0; if(maxscore>0) inc1=(rem+maxscore-1)/maxscore; else inc1=1000000001; int inc2=0; int sum=0; for(int i=0; i<zerocnt; i++) { if(sum>=rem) break; inc2++; sum+=zero[i]; } tres+=min(inc1, inc2); res=min(res, tres); } return res; } };
TCO2012 Round2B 550 HeavyBooks
TopCoder Open | |
コーディングフェーズ
うーん
一番重いのを押し付けあうとしか思えない
それより軽いのを渡しても得する場面が全く思いつかない
一番重いのを押し付けあうとすると、最初にTomekがどの本を入れるか決めるだけの問題
重い順に見ていけばどちらが持つかは一意に決まるので、重い順に本を採用するかしないかでDPすればOKかな
書こうとする
添字とDPの更新条件式がカオスになる
デバッグで最終的に40分もかかった
提出
ソースコード
DP更新条件式のカオスなところは直しました
今回はpairを使えば比較的ラクに更新ができる気がする
本番でもpairを使っていたのになぜカオスになったんだ・・・
const int INF=1000000000; class HeavyBooks { public: vector <int> findWeight(vector <int> books, vector <int> moves) { vector <int> res; int n=books.size(); int m=moves.size(); vector <int> b(moves[0], 1); for(int i=1; i<m; i++) { int idx=0; for(int j=0; j<moves[0]; j++) { if(b[j]==(i&1)) { b[j]=1-b[j]; idx++; if(idx==moves[i]) break; } } } pair <int, int> difsum[52][52]; for(int i=0; i<52; i++) for(int j=0; j<52; j++) { difsum[i][j]=make_pair(-INF, 0); } difsum[0][0]=make_pair(0, 0); sort(books.begin(), books.end(), greater <int>()); for(int d=0; d<n; d++) { for(int bi=0; bi<moves[0]; bi++) { pair <int, int> cand; cand=difsum[d][bi]; difsum[d+1][bi]=max(difsum[d+1][bi], cand); if(b[bi]) { cand=difsum[d][bi]; cand.first+=books[d]; cand.second+=books[d]; difsum[d+1][bi+1]=max(difsum[d+1][bi+1], cand); } else { cand=difsum[d][bi]; cand.first-=books[d]; cand.second+=books[d]; difsum[d+1][bi+1]=max(difsum[d+1][bi+1], cand); } } } pair <int, int> best(-INF, 0); for(int i=0; i<=n; i++) { best=max(best, difsum[i][moves[0]]); } res.push_back((best.second-best.first)/2); res.push_back((best.first+best.second)/2); return res; } };
コメントを書く
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120513