WARush

SRMの結果とか、解けた問題のコードを書いていきます

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" );
}