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

pekempeyのブログ

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

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

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

codeforces.com

解法

左端と右端から同時に 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 ...

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