kojingharangの日記

SRM 602 Div1 250 TypoCoderDiv1

16:15 |

• 数値 X から始めて N ゲームする。ゲーム i で数値を ±D[i] 変えられる。0未満になったら0になる。2連続で2200以上にならない条件で, 2200以上と2200未満を最大何回変えられるか？
• 1≦N≦50, 0≦D[i]≦1,000,000,000, 0≦X≦2199

• dp[i回目(終了後)][数値] == 最大変化回数 ... だと 50 * 10^9 かかりそうなので工夫しろということか

• 2連続で2200以上にならないヒントをどう使うか

• 2200以上になったら、その次の次で 2200 未満に戻って来れないときは捨てていいので 0〜2199 まで持っておけばよさげ
• 更新式は
• 新しい数値＜2200 なら dp[i+1][新しい数値] max= dp[i][元の数値] (変化回数は変化なし)
• 新しい数値≧2200 かつ 次の次がある かつ 次の次に減らしたら 2200 未満になるなら dp[i+2][次の次まで足した数値] max= dp[i][今の数値] + 2

• 最後は
• 2200 未満で終わる場合は dp[N][数値] (数値＜2200)
• 2200 以上で終わる場合は「N-1ゲーム終了時点で 2200 未満で N ゲーム後に 2200 以上」なので dp[N-1][数値]+1 (数値＜2200 and 数値 + D[N-1]≧2200)

• デバッグに時間がかかる

• accepted

int dp[51][2210];
class TypoCoderDiv1 {
	public:
	int getmax(vector <int> D, int X) {
		int minf=-(1<<29);
		int N=D.size();
		REP(i, N+1) REP(v, 2201) dp[i][v]=minf;
		dp[0][X]=0;
		REP(i, N) {
			REP(v, 2200) {
				if(dp[i][v]==minf) continue;
				for(int k=-1;k<=1;k+=2) {
					int nv = max(v+k*D[i], 0);
					if(nv>=2200) {
						if(i+1<N) {
							int nnv = max(nv-D[i+1], 0);
							if(nnv < 2200) {
								// 2200未満に戻ってこれるなら更新
								dp[i+2][nnv] = max(dp[i+2][nnv], dp[i][v]+2);
							}
						}
					} else {
						dp[i+1][nv] = max(dp[i+1][nv], dp[i][v]);
					}
				}
			}
		}
		int ans = 0;
		REP(v, 2200) ans=max(ans, dp[N][v]);
		// 最後で 2200 を超える場合
		REP(v, 2200) if(dp[N-1][v]!=minf && v+D[N-1]>=2200) {
			ans=max(ans, dp[N-1][v]+1);
		}
		return ans;
	}
};

• あとで
• そうか 2200 以上の状態を入れても 50 * 4400 個だから map を使えばもっと簡潔に書けるのか。
• accepted in practice

class TypoCoderDiv1 {
	public:
	int getmax(vector <int> D, int X) {
		int N=D.size();
		map<int, int> dp[52];
		dp[0][X]=0;
		REP(i, N+1) FOR(e, dp[i]) for(int d=-1;d<=1;d+=2) {
			int v=e->first;
			int nv = max(0, e->first + d*D[i]);
			int change = v<2200&&nv>=2200 || v>=2200&&nv<2200;
			if(e->first>=2200 && nv<2200 || e->first<2200)
				dp[i+1][nv] = max(dp[i+1][nv], change + e->second);
		}
		int ans=0;
		FOR(e, dp[N]) ans=max(ans, e->second);
		return ans;
	}
};

ツイートする