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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

GCJ Round 1B Problem B. Close Match

https://code.google.com/codejam/contest/11254486/dashboard#s=p1

問題

桁がところどころ ? で伏せられている 2 つの整数 C, J が与えられる。? に好きな数字を入れていいので C と J の差の絶対値を最小化せよ。

  • 1≦|C|,|J|≦18

解法

左から数字を決定していく。

左から 4 つまで一致していて 5 つ目で差ができたとする。

92535***
92534***

このとき *** の部分をどのように決めても差は正になる。極端な例としては次のような場合があるが、これも差は正である。

92535000
92534999

したがって一度不一致になったら上はできるだけ小さく、下はできるだけ大きくするのが最適である。


DFS した。

GCJ Round 1B Problem B. Close Match

GCJ の Round 1 で桁 DP はないだろうと思って別解法を取った。ところで僕は 2015 年の GCJ しか知らないのでこの推測は怪しい。