1117

M本氏に感謝ｗ 解けーた。

既に和の部分が求まっていて、x+y=nのxとyが未知な覆面算として解いた。しかし、覆面算と言っても4桁の場合なら

  A B C D
+   B C D
---------

  A B C D
+   A C D
---------

  A B C D
+   A B D
---------

  A B C D
+   A B C
---------  

多くてもこの四つのパターンに限られる。後は繰り上がりを考慮しつつそのままバックトラックで探索。再帰の状態に桁を抜いたという情報を持っておくと、一度桁を抜いたらもう抜くことは無いのでXi=Yi=Ni/2という計算をひたすら繰り返すだけで済む。しかもNの一の位が奇数の場合はXの一の位を取り除いた物をYとするしかない等の枝刈りが出来るため状態数は少なめ。

ショートコーディング:
しようと思ったけど、東大の人の370Bを見て愕然ｗ根本的にやり方を変えないと短くできなさそう。強いっす。。