考察
pathが通るcell(i,j)のdigitは最終decimal numberで10^{2N-i-j}の位を占めるため、各path scoreは通過cell weightの和mod Mになる。
任意pathは反対角線i+j=N+1をちょうど一cell通る。そこまでの前半と以後の後半は各O(2^{N})通りで独立に列挙できる。
採用する候補: 反対角線でmeet-in-the-middleし、cell別の前半/後半剰余集合をsortして最大mod和を探す
棄却する候補: 全start-to-goal pathを列挙してdecimal値を計算する
N=20でも約C(38,19)が大きく、中央分割を使わないと間に合わない。
10冪mod Mでcell weightを作る。DFS/DPでstartから各反対角cellまでのsum residue、goalから同cell直後までのsum residueを列挙する。後半listをsortし各前半xへlower_bound(M-x)直前または末尾を組み合わせてmaxを取る。
典型の発動条件
meet-in-the-middle on lattice paths
発動条件: path長が約40で全path列挙は重いが中央layerで二分できるとき。
反対角線cellごとに前後path residueを列挙する。
maximum modular pair sum
発動条件: 二集合から(x+y) mod Mの最大を求めるとき。
wrap直前のyをbinary searchする。
問題固有の要素
decimal連結を逐次value更新する代わりに各cellの固定place valueへ展開すると、前後pathの寄与が加法的になりmeet-in-the-middleできる。
別の問題へ持ち帰る視点: path上で順序依存に見える数値も、位置がpath長で固定なら重み付き和へ変換する。
正当性
中央cellのweightは前半側だけへ含め、後半側から除外して二重加算を防ぐ。 固定xに対し(x+y) mod M最大は、y<M-xの最大があればそれ、なければS2最大である。 全path数C(2N-2,N-1)を、各半分O(2^{N-1})へ分割し、各xに対する最適yをbinary searchしてO(N2^N)程度で処理できる。
実装上の注意
- 中央cellを前半/後半どちらか一方だけに含める。M-x=0のlower_bound境界、N=1の空後半を扱う。
復習の核
- N≤6で全pathを列挙し、Mが小さくresidue重複が多いcase、wrap有無、N=1を比較する。
計算量と制約
時間
O(N2ᴺ)、半path列挙・後半sort・各前半lower_bound。
空間
O(2ᴺ+N²)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 20; 2 \leq M \leq 10^9; 1 \leq A_{i,j} \leq 9; All input values are integers.
出典