Codeforces Round #342 (Div. 2) D. Finals in arithmetic
暴力解法なのであくまで参考程度に。
解法
左端と右端から同時に 1 桁ずつ決定していく桁 DP を行う。
- dp[ 両端 i 桁が確定 ][ 左側 i+1 桁目で桁上げしている ][ 右側 i 桁目で桁上げしている ] := この状態に到達できるか
「左側 i+1 桁目で桁上げしている」を carryLeft フラグ、「右側 i 桁目で桁上げしている」を carryRight フラグと呼ぶことにする。
i+1 桁目を決定することを考えよう。簡単のために左側から i+1 桁目を D[i+1]、右側から i+1 桁目を D[-i-1] と表すことにする。このとき D[i+1] と D[-i-1] は次の条件を満たさなければならない。
i+1 桁目の和が n[i+1] と一致する。
(D[i+1]+D[-i-1]+nextCarryLeft) mod 10 = n[i+1]-i-1 桁目の和が n[-i-1] と一致する。
(D[i+1]+D[-i-1]+carryRight) mod 10 = n[-i-1]carryLeft フラグ条件と矛盾しない。
D[i+1]+D[-i-1]+nextCarryLeft ≧ 10 == carryLeft
i 桁目の決定にまだ確定していない左側から i+1 桁目の桁上げを仮定するのがポイント。後は DP 復元で答えが求まる。
n/2 桁目あたりで若干面倒なことが起こるので注意しよう。
Codeforces Round #342 (Div. 2) D. Finals in arithm ...
(追記 2016/02/08)
再帰で書いてみたら復元の手間が省けた。
Codeforces Round #342 (Div. 2) D. Finals in arithm ...