Codeforces Round #342 (Div. 2) D. Finals in arithmetic

暴力解法なのであくまで参考程度に。

左端と右端から同時に 1 桁ずつ決定していく桁 DP を行う。

「左側 i+1 桁目で桁上げしている」を carryLeft フラグ、「右側 i 桁目で桁上げしている」を carryRight フラグと呼ぶことにする。

i+1 桁目を決定することを考えよう。簡単のために左側から i+1 桁目を D[i+1]、右側から i+1 桁目を D[-i-1] と表すことにする。このとき D[i+1] と D[-i-1] は次の条件を満たさなければならない。

i 桁目の決定にまだ確定していない左側から i+1 桁目の桁上げを仮定するのがポイント。後は DP 復元で答えが求まる。

n/2 桁目あたりで若干面倒なことが起こるので注意しよう。

（追記 2016/02/08）

再帰で書いてみたら復元の手間が省けた。

来週まで期末試験があるので、今週は更新が控えめになると思います。