RUPC B, AOJ-2282: B問題 (Problem B)

問題概要

[0,M]内におけるA[i](i

考えたこと

• 問題文が長くてうげー。
• 最初入力勘違いしていて一人が受け持つ問題が複数あると思ってた。
  • それでも整数の分割でサイズが小さければ解けそう。
• ひとり一問なら単なるシミュレーションでよい。
• 最後の一人を特別扱いしなくちゃいけないかとちょっと思ったけど、その必要は無いことに気づいた。
• あとは愚直に書く。RE。why?
• 怪しげなところをassertの代わりにfor(;;);はさんだり入力をiostreamに変えたりしたけどREがとれない。
• 最後の手段としてJavaで書き直した。これでもRE。
• と思ったらこのREはパッケージ名が入っていたせいだった。取り除いたら無事AC。
• その後ClarやTwitter見たらNの上限が変わっていたらしかった。
• ここで心が折れてコンテストを途中退場した。

本番で通るはずだったコード

#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 1000;
const int INF = 1<<29;

int N, M;
int as[MAX_N];

int solve(){
	int mini = INF, key = INF, ans = -1;
	bool hope = false;

	for(int i=0; i<N; i++){
		vector<int> ts;ts.reserve(M+1);
		for(int j=0; j<=M; j+=as[i]){
			ts.push_back(j);
		}

		vector<int> escp; escp.reserve(ts.size());
		for(int j=0, T = ts.size(); j<T; j++){
			int tme = ts[j];
			if( tme > mini || (tme == mini && as[i] >= key) ){
				escp.push_back(tme);
			}
		}

		//逃れられる
		if(!escp.empty()){
			int tme = escp[0];
			if(tme == mini && as[i] == key){
				hope = true;
			}
		}

		//逃れられない
		else{
			hope = false;
			mini = ts.back();
			key = as[i];
			ans = i;
		}
	}

	return hope ? N : ans + 1;
}

int main(){

	while(scanf("%d%d",&N, &M), N){
		for(int i=0; i<N; i++){
			scanf("%d", as+i);
		}
		printf("%d\n", solve());
	}
	return 0;
}