読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #182 Div1. C. Yaroslav and Algorithm

Codeforces

これ、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;
}

まとめ

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

広告を非表示にする