Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-05-13TCO2012 Round2B

TCO2012 Round2B 300 BlurredDartboard

| 17:55 | TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

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;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120513