はまやんはまやんはまやん

hamayanhamayan's blog

Best Matched Pair [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : A]

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_a

N個の数列がある。
これから2つ選んで積をとる。
その中で、文字列として見た時に、連続で増加している積の中で最大のものは?
連続で増加している例))2, 23, 56789
連続で増加していない例) 21, 334, 135, 89012

1 <= N <= 10^3
1 <= a[i] <= 10^4

考察

1. Nが10^3で全てのパターンを試してもO(N^2)なので大丈夫そう
2. 総当りして試してチェックすればいい
3. 文字列に変換とかするとTLEするかも(これくらいならしないかも)

実装

http://jag2016autumn.contest.atcoder.jp/submissions/863699

int N;
int a[1010];
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) cin >> a[i];
 
	int ans = -1;
	rep(i, 0, N) rep(j, i + 1, N) {
		int mul = a[i] * a[j];
		
		int check = mul;
		bool ok = true;
		int prev = check % 10;
		check /= 10;
		while (0 < check) {
			int m = check % 10;
			if (prev - 1 != m) ok = false;
			prev = m;
			check /= 10;
		}
		
		if (ok) ans = max(ans, mul);
	}
	cout << ans << endl;
}