ABC 401-500/ABC402F - Path to Integer - 競技プログラミング用 知識集積所【6/9更新】

---

問題

ABC402F

必要知識

B以下レベルの内容は省略

• 半分全列挙（未作成）
• 二分探索（未作成）

考え方

まず、愚直にやることを考えてみる。
最大のn=20の場合、各ルートごとに39桁の数ができ、しかもルート数がComb(38,19)≒3.5×10^10通りくらいあり、全く間に合わない。
そこで、半分全列挙（未作成）を使って左上と右下から半分ずつを考え、対角線（右上-左下）上の各マスで合流することを考える。

例えば入力例2の場合、

1	2	3
3	5	8
7	1	2

左上から左下へは13700、左上から中央へは12500と13500、など。
右下からはちょうど対角線上にあるものをダブって足さないように、左下から右下へは12、中央から右下へは12と82、など。

すると、ルート数は2^19でおよそ5.2×10^5、を2セットで済むので数を作ること自体は余裕で間に合う。
さらに、数を連結するのではなく、最初に全マスを

10000	2000	300
3000	500	80
700	10	2

のように10の何乗かを掛けてmで割った余りに加工しておくことで、連結がただの和の計算で済むしlong long型からあふれる心配もしなくてすむ。
（入力例2だとmが10万なので、余りにする計算が見た目に現れないが……）

あとは合流した各地点で最大値を探す話だが、これも愚直にやるとTLEする。
というのも、中央付近だとComb(19,10)の2乗で8.5×10^10くらいのパターンがあるから。
そこで、左上からと右上からそれぞれ、同じマスに到達する各ルートの値をmで割った余りを全てソートし、二分探索（未作成）を利用する。

左上からの各値についてループを回し、右下からの値で足してギリギリmを超えない値を探し、それらの和を最大値候補にする。
また、ギリギリ2mを超えない値、つまり両方の最大値を加えてmを引いた値も最大値候補に加える。
全地点でそれを行い、全ての中での最大値を答えればよい。

解答例

解答例

注意点

n=1の場合に注意

右下から計算していくときに初期条件で右下マスの値を入れると、n=1のときにWAする。
n=1のときは右下は対角線上なので加えてはいけない。
初期条件の工夫が必要。

別解