SRM 556 500pt : LeftRightDigitsGame2

雑記 TopCoder

問題概要

n(<50)毎のカードA[i]があり、0~9の数字がかかれている。n桁の整数lowerBoundが与えられるので、a=(空文字列)からスタートしてa=a~A[i]またはa=A[i]~aをi=0から順に作用させてlowerBound以上の数を作りたい。そのような数の中で最小のものを求める問題。無理なら指摘する。

解法

ソースコード中に書いたコメントの焼き直し。

  • minStr[i] = {digits[0:i]の順序を入れ替えて作ることのできる最小の文字}
  • geq[i][j] = {digits[0:i]の順序を入れ替えて作ることのできるlowerBound[j:j+i]以上の文字で最小のもの}
  • ge[i][j] = {digits[0:i]の順序を入れ替えて作ることのできるlowerBound[j:j+i]より大きい文字で最小のもの}

とする。「順序を入れ替えて作ることのできる」というのは問題文に書かれた手順に従って、という意味。この状態を持つことに気づけば更新式は超簡単。
計算量はO(n^3)。

考えたことなど

コンテスト中に考えたこと
  • ちょっと毛色の違う辞書順最小の構成？
  • 先頭から順に確定させていけばうまく生きそう。
  • ただし小さいiで確定させてしまうとそれ以降は必ず後ろに付けないといけなくなって制約がきつくなるので、なるべく小さいのをなるべく後ろから選べばよい。
    • この部分が嘘なんだけどなかなか気づけなかった。
終わってから考えたこと
  • この問題を見たときにいつもの辞書順最小のアレを思い出すのは自分にとってとても自然なことで、次同じ問題に当たっても同じ間違いをやらかしかねない。
  • 今回使ったdpの状態の取り方は個人的にあまり見たことがない。こういうのを自力で思いついたときはかなり爽快ではあるんだけどコンテスト中に、というのは厳しい。
  • 個人的な好みの話をすると、問題を既知のパターンに分解するような解き方は結構好きで、逆にアドホックな頭使う問題(SRMのeasyとかそういうの多い)には苦手意識がある。
  • 好みの話を抜きにするとしても、「上手いこと思いついた」という経験の大半はただの勘違いなので、コンテスト中はなるべくベタに浅く広く考えることを意識している。
  • で、結局自分がコンテスト中にこの問題を解くためには何が必要だったんだろう…。

acceptされたコード

#include <string>
using namespace std;

const int MAX_N = 50;

/*
 * minStr[i] = {digits[0:i]の順序を入れ替えて作ることのできる最小の文字}
 * geq[i][j] = {digits[0:i]の順序を入れ替えた文字がlowerBound[j:j+i]以上となる最小の文字}
 * ge[i][j] = {digits[0:i]の順序を入れ替えた文字がlowerBound[j:j+i]より大きくなる最小の文字}
 */
string minStr[MAX_N + 1];
string geq[MAX_N + 1][MAX_N + 1];
string ge[MAX_N + 1][MAX_N + 1];

void updateGeq(string& old, const string& x, const string& sub) {
	if (x.length() == sub.length() && x >= sub && (old.empty() || old > x)) {
		old = x;
	}
}

void updateGe(string& old, const string& x, const string& sub) {
	if (x.length() == sub.length() && x > sub && (old.empty() || old > x)) {
		old = x;
	}
}

struct LeftRightDigitsGame2 {

	string minNumber(string digits, string lowerBound) {
		const int n = digits.length();

		for (int i = 0; i <= n; ++i) {
			for (int j = 0; j < i; ++j) {
				minStr[i] = min(digits[j] + minStr[i], minStr[i] + digits[j]);
			}
		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j + i < n; ++j) {
				const string sub = lowerBound.substr(j, i+1);

				//末尾に追加する場合
				{
					const string x = geq[i][j] + digits[i];
					const string y = ge[i][j] + digits[i];

					updateGe(ge[i+1][j], x, sub);
					updateGe(ge[i+1][j], y, sub);
					updateGeq(geq[i+1][j], x, sub);
					updateGeq(geq[i+1][j], y, sub);
				}

				//先頭に追加する場合
				{
					if (digits[i] == lowerBound[j] ) {
						const string x = digits[i] + geq[i][j+1];
						const string y = digits[i] + ge[i][j+1];

						updateGe(ge[i+1][j], x, sub);
						updateGe(ge[i+1][j], y, sub);
						updateGeq(geq[i+1][j], x, sub);
						updateGeq(geq[i+1][j], y, sub);
					}
					else if (digits[i] > lowerBound[j]) {
						const string x = digits[i] + minStr[i];
						updateGe(ge[i+1][j], x, sub);
						updateGeq(geq[i+1][j], x, sub);
					}
				}
			}
		}

		return geq[n][0];
	}

};