Codeforces #182 Div2 E "Yaroslav and Algorithm"
問題
http://codeforces.com/contest/302/problem/E
訳
ヤロスラフはアルゴリズムが好きである。
その中でも彼が特に好きなものをひとつ説明する。
1. そのアルゴリズムの入力は1つの文字列である。この文字列を a とする。 2. そのアルゴリズムはいくつかのコマンドで構成されている。 i番目のコマンドは「s_i>>w_i」もしくは「s_i<>w_i」のどちらかであり、 s_iとw_iは0~9の数字と"?"からなる、長さ0~7の文字列である。 (空文字でもよい事に注意せよ) 3. コマンドを走査する際、a に s_iが部分文字列として含まれる、 最小のiを見つける。もし、そのようなコマンドがなければ、 アルゴリズムは終了する。 4. 見つけたコマンドの番号をkとする。a の中の、最初の部分文字列 s_k を、 w_k で置換する。そして、そのコマンドが 「s_k>>w_k」であれば、 アルゴリズムは実行し続け、またコマンド走査が始まる。 そうでなければアルゴリズムは終了する。 5. アルゴリズムが終了する際に、その時の a が出力される。
ヤロスラフはnこの正の整数のセットを持っており、
彼は、上記のアルゴリズムを使用して、
セットの各整数を1増加させたいと思っている。
より正確には、セットの各整数を10進数表記の文字列と考え、
各文字列を入力としてアルゴリズムを実行したときに、
その出力の文字列が、入力の文字列と比べ、
10進数表記で1増加されたものであるようにしたい。
そのようなアルゴリズムのコマンドを出力せよ。
制約(入力)
1 <= n <= 100
1 <= セットの整数 <= 10^25
制約(出力)
コマンド数 <= 50
1回の実行におけるコマンドの走査数 <= 200
ACしてるソースコードをカンニング
やりたい事
今着目している数字が0~8だったら、インクリメントして即終了
123456 ^ ↓ 123457(END)
今着目している数字が9だったら、
その数字を0にして着目する数字を左に1つずらして続行
123459 ^ ↓ 123450(CONTINUE) ^
最初の数字のさらに左にきてもまだ終わってない場合は1を追加して終了
99 ^ ↓ 90 ^ ↓ 00 ^ ↓ 100(END)
?をポインター代わりに
どこに ? を挿入するかだが、
s >> wのs, wは空文字でもよいため、
コマンドを「>>?」とすることで、どんな文字列でも?を先頭に挿入できる。
123 → 「>>?」→ ?123
まずは右端の数字を着目させたいので、
そこから ? を一番右に移動させればよい。
しかしこのままだと、
その数字に着目しているのか、単なる移動中なのか判断できないため、
最初に「>>??」で ?? を追加して、?? ならば移動中であるとする。
移動の為に以下のコマンドを追加する
??0>>1?? ??1>>1?? ??2>>2?? ??3>>3?? ??4>>4?? ??5>>5?? ??6>>6?? ??7>>7?? ??8>>8?? ??9>>9??
例) 123 → 「>>??」→ ??123 ??123 → 「??1>>1??」→ 1??23 1??23 → 「??2>>2??」→ 12??3 12??3 → 「??3>>3??」→ 123??
一番最後に移動できたら?を1つ削除する
これで、?の前の数字に着目していることを表現でき、
ポインターのように扱える。
123?? → 「??>>?」→ 123?
着目している数字が0~8の時
インクリメントして即終了
123? → 「3?<>4」→ 124(END)
そのためのコマンド
0?<>1 1?<>2 2?<>3 3?<>4 4?<>5 5?<>6 6?<>7 7?<>8 8?<>9
着目している数字が9の時
0にしてポインタを左に
129? → 「9?>>?0」→ 12?0(CONTINUE)
ポインタが左端にきてた
1を追加して即終了
99? → 「9?>>?0」→ 9?0(CONTINUE) 9?0 → 「9?>>?0」→ ?00(CONTINUE) ?00 → 「?<>1」→ 100(END)
あとはコマンドの順番に注意!
事後
面白い問題!
だけど題意を理解する事が出来なかった・・・
ソースコード
int main() { for( int i = 0; i <= 9; i++ ){ printf( "??%d>>%d??\n", i, i ); } printf( "??>>?\n" ); for( int i = 0; i <= 8; i++ ){ printf( "%d?<>%d\n", i, i+1 ); } printf( "9?>>?0\n" ); printf( "?<>1\n" ); printf( ">>??\n" ); }