sedによる$10$進数の$1$進数化はよく使われるのでパターン化しているが、その逆をしたのは始めてだった。

solution

$\operatorname{ans} = \max \{ x-1, n-x \}$.

implementation

sed 147byte (%20さんのものを参考に修正したあと縮めたやつ)

https://beta.atcoder.jp/contests/abc040/submissions/774918

参考にしたのは%20さんのこの提出(https://beta.atcoder.jp/contests/abc040/submissions/774828)で、特にその$1$進数からの逆変換を借りた。 加えて、y/123456789b/012345678-/のbと-の部分が自明に無駄だったのを指摘してもらった。ありがたい。

#!/bin/sed -f

# make numbers unary
:
s/[1-9]/&-/g
y/123456789/012345678/
s/-0/9-/
t

# calculate the answer
## (n, x) -> (n-x, x-1)
s/-\(-*\) 0*-\1$/ \1/
## min
s/0*\(-*\)-* \1-*/0\1/

# make it a decimal
:1
s/-/<<123456789-01>/
s/\(.\)<.*\1\(-*.\).*>/\2/
t1

解読

:
s/-/<<123456789-01>/
s/\(.\)<.*\1\(-*.\).*>/\2/
t

について。これは0------------のような$1$進数表現から1234のような$10$進数表現への変換。先頭に0がないものからでも変換はできるが、それが$0$である場合は結果は空 になる。0000------------みたいなのや0---0---からでも上手く動く。

単体の-からは以下のように変化する。$2$回目で<を\1にcaptureし、最右の<の次の文字である1が残る。正規表現は貪欲というのが効いている。

-
<<123456789-01>
<<123456789<<123456789-01>01>
1

9からは以下のように進むので、これは繰り上がりになる。

9-
9<<123456789-01>
-0