解法(素朴な解法から現時点のBest解法(7L)まで)
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
解法1(参考:17L)
各桁ごとに足すことを考える。
+の左(左辺の最小桁)の情報(1 or 0)を右端(右辺の最小桁)に持って行く。
右端で足し算(インクリメントの方法は別の問題#0010 Incrementを参照)。
右端で処理済みの桁は処理しないようブロックする必要がある。
# インクリメント 1c:c0 0c:1 c:1 . # 情報を右端に持って行く a1:1a a0:0a . # 足し算(1+1のケースのみインクリメントする(cを生成)) 1aa:1cb 1a:1b 0aa:1b 0a:0b . # 右辺に桁が足りない場合 aa:d1 a:d0 . # 処理済みの桁をブロックする 1b:d1 0b:d0 . # 左辺の最小桁の情報を移動用文字に変換 1+:+aa 0+:+a . # 不要となった文字を消去 d: +:
解法2(参考:12L)
求めたい値は左辺と右辺の足し算。
右辺の数だけ、左辺をインクリメントすればよい。
処理ごとに右辺をデクリメント・左辺をインクリメントして右辺が無くなったら終了することを考える。
+の左にインクリメント用文字、右に移動用文字を生成して、移動用文字は右端に移動したらデクリメント用文字に変換する。
# 移動用文字を右端に移動 b1:1b b0:0b . # 右辺が無くなった(移動用文字が移動しなかった)ら、終了 a+b:: . # 移動用文字をデクリメント用文字に変換 b:c . # デクリメント処理 1c:0 0c:c1 c1: . # インクリメント処理 0a:1 1a:a0 a:1 . # +の左右に処理用文字を生成(右辺の最上位桁が0なら消去) +0:+ +:a+b
解法3(参考:8L)
行数を減らすには使用する文字の種類を減らすのが良い。
今使用している文字は以下の3種類。
- インクリメント用文字
- デクリメント用文字
- 移動用文字
デクリメント用文字を使わないことを考える。
デクリメントを言い換えると(-1)を加算しているということになる。
(-1)は2の補数で表現することができる。
右辺の処理は、2の補数で表現された(-1)を加算することで代替することができて、デクリメント処理を省略することができる。
(-1)を2の補数表現すると、111111のような、各桁が1の2進数になる。
これを右辺に加算するにはどうすればよいか考える。
各桁をインクリメントすれば同等の処理ができる。
移動用文字が、移動しながら各桁にインクリメント用文字を撒くことで実現できる。
右辺の最上位桁が1の場合、確定で桁あふれするので、あらかじめ消しておく必要がある(処理用文字を生成する際に同時にできる)。
右辺の最上位桁が0の場合は存在しない(そのような場合はそもそもインクリメント処理で繰り上がりらないので、1をあらかじめ消しておくのが効いてくる)。
# 各桁にインクリメント用文字を撒きながら移動 b1:1ab b0:0ab . # 不要となった移動用文字を消去 b: . # インクリメント処理 1a:a0 0a:1 a:1 . # 処理用文字を生成(右辺の最上位桁は桁あふれすることが確定なのであらかじめ消しておく) +1:a+b . # 不要となった文字を削除 +:
解法4 2021/10/2現在判明しているbest解法。解法3を推し進めたもの。(参考:7L)
行数を減らすには使用する文字の種類を減らすのが良い。
今使用している文字は以下の2種類。
- インクリメント用文字
- 移動用文字
移動用文字を使わないことを考える。
#0010 Increment を解くときに使った手法がそのまま使えそうなので、その方針で考える。
そのまま方針を適用すると、
移動用文字兼インクリメント用文字となる文字(処理用文字)が、一回の処理あたり2回右辺を移動することになる。
すると、左辺が1回インクリメントされる間に右辺が2回デクリメントされてしまう。
ところがこのとき、右辺の右端にインクリメント用文字が完成しているため、右辺が勝手にインクリメントされる。
結果的に左辺が1回インクリメントされる間に右辺が1回デクリメントされて、辻褄が合う。
処理中に一時的に2回デクリメントされる必要があるため、最後のインクリメントが上手くいかないように思える?
最終の状態としては
100101+1
のような状態になり、ここで処理用文字を生成すると
100101a+a
のような状態になり、これ以上処理が進まないため、インクリメントが上手くいかない。
ところがこのとき、終了処理である 「+:」によって+が消去され、自動的にインクリメント用文字が完成し、最後のインクリメントが成功して辻褄が合う。
# インクリメント処理 0aa:1 1aa:aa0 aa:1 . # 処理用文字(a)が移動しながらインクリメント用文字(aa)を撒く a0:0aaa a1:1aaa . # 処理用文字(a)を生成(右辺の最上位桁は桁あふれすることが確定なのであらかじめ消しておく) +1:a+a . # 終了処理と同時に最後のインクリメントを完成させる +: