TopCoder SRM 829 : Div1 Easy Div2 Hard SnookerScoring

不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=17558&rd=19218

問題

Snookerは、以下のルールで行うビリヤードの1形態である。
R個の赤いボールと、C個の色付きボールがある。
赤いボールは1個穴に入れると1点、C個の色付きボールは、ボールごとに2～(C+1)点のものが1個ずつある。

自分のターンでは、以下のようにボールを穴に落としていく。
失敗したらその場で終了である。

• 赤いボールが残っているとき、まず赤いボールを1つ落とす。成功すると1点を得る。
  • 次に、色付きボールを1つ選んで落とす。成功するとボールに対応する点を得る。その後、落とした色付きボールは元の位置に戻す。
• 赤いボールが残っていないとき、色付きボールを2点から順に落とす。成功するたび、ボールに対応する点を得る。その際、落としたボールは元の位置に戻らない。

このゲームはターン制なので、自身のターンに来た時、赤いボールは全部ないかもしれない。
1ターンでN点を得る手順を1つ答えよ。

解法

以下のケースのうち、N点を得る手順を愚直に探索しよう。

• 赤ボールを(n+1)回、その間に色付きボールをn回落とす。
• 赤ボールをn回、その間に色付きボールをn回落とす。その後、2～(C+1)点のボールのprefixをいくつか落とす。

class SnookerScoring {
	public:
	vector <int> scoreN(int N, int R, int C) {
		vector<int> V;
		int i,j,x;
		for(i=1;i<=R;i++) {
			{
				int mi=i+2*(i-1);
				int ma=i+(C+1)*(i-1);
				if(mi<=N&&N<=ma) {
					FOR(j,i) {
						V.push_back(1);
						V.push_back(2);
					}
					V.pop_back();
					N-=i*3-2;
					FOR(j,i-1) {
						int x=min(C-1,N);
						V[j*2+1]+=x;
						N-=x;
					}
					return V;
				}
			}
			{
				int mi=i+2*i;
				int ma=i+(C+1)*i;
				if(mi<=N&&N<=ma) {
					N-=i*3;
					FOR(j,i) {
						V.push_back(1);
						V.push_back(2);
					}
					FOR(j,i) {
						int x=min(C-1,N);
						V[j*2+1]+=x;
						N-=x;
					}
					return V;
				}
			}
		}
		
		for(i=0;i<=R;i++) {
			int mi=i+2*i;
			int ma=i+(C+1)*i;
			int sum=0;
			for(x=2;x<=C+1;x++) {
				sum+=x;
				if(mi+sum<=N&&N<=ma+sum) {
					N-=sum;
					FOR(j,i) {
						V.push_back(1);
						V.push_back(2);
					}
					N-=i*3;
					FOR(j,i) {
						int x=min(C-1,N);
						V[j*2+1]+=x;
						N-=x;
					}
					for(i=2;i<=x;i++) V.push_back(i);
					return V;
				}
			}
		}
		
		
		
		
		
		return V;
		
	}
}

まとめ

コーナーケース対応が面倒なだけで面白さを感じられない…。