SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2011-04-08SRM502 Div1
- 250:219.90, 500:150.00(+125), score:494.90, rank:63, rating:2108(+48)
- 500に時間かけすぎた。でも通って良かった。
SRM502 Div1 250 TheLotteryBothDivs
コーディングフェーズ
一瞬包除原理かと思ったが全然違った
他の要素がsuffixになっている要素を削除するだけだった
少し時間を使い過ぎたが適当に書いて提出
ソースコード
class TheLotteryBothDivs { public: bool suff(string a, string b) { if(b.size()>=a.size()) return false; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); for(int i=0; i<(int)b.size(); i++) { if(a[i]!=b[i]) return false; } return true; } double find(vector <string> gs) { double res=0; sort(gs.begin(), gs.end()); gs.erase(unique(gs.begin(), gs.end()), gs.end()); int n=gs.size(); for(int i=0; i<n; i++) { double p=1; for(int j=0; j<(int)gs[i].size(); j++) p*=.1; res+=p; for(int j=0; j<n; j++) { if(i==j) continue; if(suff(gs[i], gs[j])) { res-=p; break; } } } return res; } };
SRM502 Div1 500 TheProgrammingContestDivOne
コーディングフェーズ
何となくだが、問題aとbのどちらを先に解くかの比較としては、
aを先に持ってきた場合の総減点と、bを先に持ってきた場合の総減点を比較すれば良い気がする
何か怪しいがとりあえず書いてみる
サンプル合った
・・・
けどこれは明らかにダメだな
減点が少ないが得点が高く、目一杯時間を使いきらないと解けないような問題が反例になる
解く問題のセットが決まれば、上記の順位付けでとりあえずは書けそうだが・・・
セットを決めようとすると2^50とかになってしまう・・・どうするんだ・・・
・・・
(結構長く悩む)
・・・
よく考えたら、逆に考えれば良いのか
全体の順序を先に決めて、その中でどの要素を使うかを決めても同じ結果になる・・よね・・
ってことは普通に上記順序付けでソートしてDPするだけで良かったりする?
書けた
提出
もう一度見直す
あ、、微妙にDPの更新間違っとる!(泣
どうせ提出時198点とかだし今更再提出しても大して変わらんか・・・
再提出
すぐ出し直したのに150点とか。今更だが再提出の10%ペナルティってどういう意味なんだ
チャレンジフェーズ
これってサンプル相当弱いから、適当なGreedyとかでも通るよなぁ・・
と思いつつ、インターミッションの間にいくつかテストケースを用意する
皆さんの回答見るとちゃんとDPしてるから皆頭いいなーと思った
でもよく見ると最初のソートの仕方が皆けっこう適当だな
maxPointsでソートとか、pointsPerMinuteでソートとか、すぐ反例思いつくような・・不注意だなあ
3つ撃墜(コード読み違えて1回失敗)
ラッキーでした
ソースコード
DPの更新がつぎはぎだらけで汚いです
vector <int> maxp, ppm, rt; int n; bool less_p(int a, int b) { ll ra=(ll)rt[a]*ppm[a]+(ll)(rt[a]+rt[b])*ppm[b]; ll rb=(ll)rt[b]*ppm[b]+(ll)(rt[a]+rt[b])*ppm[a]; return ra<rb; } int dp[100010][52]; class TheProgrammingContestDivOne { public: int find(int T, vector <int> maxp_, vector <int> ppm_, vector <int> rt_) { int res=0; maxp=maxp_; ppm=ppm_; rt=rt_; n=maxp.size(); vector <int> vi(n); for(int i=0; i<n; i++) vi[i]=i; sort(vi.begin(), vi.end(), less_p); memset(dp, 0, sizeof(dp)); for(int i=0; i<T; i++) { for(int j=0; j<n; j++) { int nt=i+rt[vi[j]]; dp[i][j+1]=max(dp[i][j+1], dp[i][j]); if(nt>T) continue; int inc=0; if(maxp[vi[j]]>(ll)nt*ppm[vi[j]]) inc=maxp[vi[j]]-(ll)nt*ppm[vi[j]]; if(inc>0) dp[nt][j+1]=max(dp[nt][j+1], dp[i][j]+inc); res=max(res, dp[nt][j+1]); } } return res; } };
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110408
リンク元
- 67 http://topcoder.g.hatena.ne.jp/
- 6 http://topcoder.g.hatena.ne.jp/diarylist
- 2 http://www.google.co.jp/url?sa=t&source=web&cd=4&ved=0CDMQFjAD&url=http://topcoder.g.hatena.ne.jp/jackpersel/20110408/1302270883&rct=j&q=srm502 div1&ei=0iKjTRuLrLoDiP3E9AQ&usg=AFQjCNGaCiCTFYHx1v9XKHFZO6MEVrLrVQ&cad=rja
- 1 http://www.google.co.jp/search?hl=ja&rlz=1G1GGLQ_JAJP270&q=TheProgrammingContestDivOne&aq=f&aqi=&aql=&oq=
- 1 http://www.google.co.jp/search?sourceid=chrome&ie=UTF-8&q=SRM502
- 1 http://www.google.co.jp/url?sa=t&source=web&cd=1&ved=0CBwQFjAA&url=http://topcoder.g.hatena.ne.jp/jackpersel/20110408&rct=j&q=topcoder 502 sigmar&ei=UTyhTdS9LI-4vQOxyaT9BA&usg=AFQjCNHPx8MFDp1nEfSNJ5qqIARUGbjEiA
- 1 http://www.google.co.jp/url?sa=t&source=web&cd=4&ved=0CDMQFjAD&url=http://topcoder.g.hatena.ne.jp/jackpersel/20110408/1302270883&rct=j&q=srm502 div1&ei=--GiTZHvOoOovQOBk6GVBQ&usg=AFQjCNGaCiCTFYHx1v9XKHFZO6MEVrLrVQ&cad=rja
- 1 http://www.google.co.jp/search?hl=ja&safe=off&q=theprogrammingcontestdivone&aq=f&aqi=&aql=&oq=
- 1 http://www.google.com/search?hl=&q=theprogrammingcontestdivone&sourceid=navclient-ff&rlz=1B3WZPB_enUS326US327&ie=UTF-8
- 1 http://www.google.com.tr/search?client=opera&rls=en&q=TheLotteryBothDivs&sourceid=opera&ie=utf-8&oe=utf-8&channel=suggest
500点問題なら,再提出するたびに50点減点され,それが最高点の30%の150点を下回ると,150点になります.
いつ提出しても10%ペナルティは結構きついんですね。。