SRM diary(Sigmar)

• 300:201.68, 550:255.68, 900:Opened, score:457.36, rank:135, rating:2312(+38)
• 解くのが遅すぎる
• 後100点くらい足りなかった。精進が必要

TCO2012 Round2B 300 BlurredDartboard

TopCoder Open | 17:55 |

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;
	}
};

TCO2012 Round2B 550 HeavyBooks

TopCoder Open | 17:55 |

Problem Statement

コーディングフェーズ

うーん

一番重いのを押し付けあうとしか思えない

それより軽いのを渡しても得する場面が全く思いつかない

一番重いのを押し付けあうとすると、最初に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;
	}
};