Codeforces #347 Div1. B. International Olympiad

一応正解したけど面倒な問題。
http://codeforces.com/contest/663/problem/B

問題

1989年から行われるコンテストがある。
X年に行われたコンテストの略称はIAO'Yと呼ぶ。
Yはこれまでの開催で使われていないXのsuffixとする。

逆にYが与えられるとき、対応するXを求めよ。

解法

自分のは想定解とは違うかな。
まず120000年程度まで順次略称を列挙し、Yが３桁以下のものは全探索してしまおう。

入力値の略称表記がABCDEFとする。
F,EF,DEF,... と略称表記のsuffixに対応する年代を順次求めていこう。
略称がABCDEFとなるのは、ABCDEF,1ABCDEF,2ABCDEF, .... とsuffixがABCDEFでその頭に小さい順に数字を付けていった年代のいずれかである。
そのうち、F,EF,DEF,CDEF,BCDEFとABCDEFのsuffixの略称に該当しない最初のものを回答すればよい。

int N;
int M[5][10100];
set<ll> did;

ll get(string v) {
	ll p=1;
	int i;
	FOR(i,v.size()) p*=10;
	ll a=atoi(v.c_str());
	FOR(i,1010) {
		if(v[0]=='0' && i==0) continue;
		ll v2=a+i*p;
		if(did.count(v2)==0) return v2;
	}
	assert(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1989;i<=123456;i++) {
		x=i;
		int p=1;
		int v=0;
		for(y=1;i>=p;y++) {
			if(y>4) break;
			v+=i/p%10*p;
			if(M[y][v]==0) {
				M[y][v]=i;
				break;
			}
			p*=10;
		}
	}
	
	FOR(i,N) {
		cin>>s;
		s=s.substr(4);
		y=atoi(s.c_str());
		did.clear();
		for(x=1;x<=s.size();x++) {
			if(x<=4) {
				did.insert(M[x][atoi(s.substr(s.size()-x).c_str())]);
			}
			else {
				did.insert(get(s.substr(s.size()-x)));
			}
		}
		cout<<*did.rbegin()<<endl;
	}
	
}

まとめ

よくこんなややこしい問題思いつくな。