ABC 402 F — Path to Integer

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Path to Integer の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: meet-in-the-middle・半分全列挙

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: meet-in-the-middle・半分全列挙

      • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題