Codeforces #182 Div1. C. Yaroslav and Algorithm

これ、Codeforcesでは珍しい問題。
一見問題文が長いけど、よく見ると簡単。
本番みんな避けてたのでD行ったけど、これやればよかったな…。
http://codeforces.com/contest/301/problem/C

問題

最大25桁の自然数を表す文字列がN個与えられる。
これらの数値に対して以下の手順でルールを適用する場合、各数値をインクリメントするようなルールを返せ。

• i番目のルールはS[i]>>W[i]またはS[i]<>W[i]の形で与えられる。SおよびWは数値か"?"で構成される0～7文字の文字でなければならない。
• ルール適用の際、順にルールを見ていき、文字列がS[i]にマッチするならW[i]に置き換える。
  • 置き換えた際、ルールがS[i]<>W[i]の形ならそこで終了。
  • 置き換えた際、ルールがS[i]>>W[i]の形なら、置換後の文字列についてまた先頭からルールを適用する。

解法

実はこの問題は数値の内容に関係なく同じルールを返せばよい。
以下のルールの組み合わせで処理できる。

• まず、文字列の最後尾を探すため、以下のルールで文字列"??"を頭に挿入
  • ">>??"
• 次に、文字列"??"を末尾まで運ぶルールを作る。
  • "??1>>1??"
  • "??2>>2??"
  • "??3>>3??"
  • "??4>>4??"
  • "??5>>5??"
  • "??6>>6??"
  • "??7>>7??"
  • "??8>>8??"
  • "??9>>9??"
  • "??0>>0??"
• 末尾にたどり着いたら、"??"を"?"に変換
  • "??>>?"
• あとは、"?"の直前の文字をインクリメントして終了。ただし?の直前が9の場合は"?"を上に伝搬していく。
  • "0?<>1"
  • "1?<>2"
  • "2?<>3"
  • "3?<>4"
  • "4?<>5"
  • "5?<>6"
  • "6?<>7"
  • "7?<>8"
  • "8?<>9"
  • "9?>>?0"
• 99999のような数字の時は、最後に1が繰り上がって終了
  • "?<>1"

あとは上記ルールを順番に気を付けて並べればよい。

void solve() {
	
	_P("??1>>1??\n");
	_P("??2>>2??\n");
	_P("??3>>3??\n");
	_P("??4>>4??\n");
	_P("??5>>5??\n");
	_P("??6>>6??\n");
	_P("??7>>7??\n");
	_P("??8>>8??\n");
	_P("??9>>9??\n");
	_P("??0>>0??\n");
	_P("??>>?\n");
	_P("0?<>1\n");
	_P("1?<>2\n");
	_P("2?<>3\n");
	_P("3?<>4\n");
	_P("4?<>5\n");
	_P("5?<>6\n");
	_P("6?<>7\n");
	_P("7?<>8\n");
	_P("8?<>9\n");
	_P("9?>>?0\n");
	_P("?<>1\n");
	_P(">>??\n");
	
	return;
}

まとめ

面白い問題だけど、珍しいスタイル。