人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

AtCoder Regular Contest 035:D - 高橋くんとマラソンコース

問題

D - 高橋くんとマラソンコース

N 個のチェックポイントが平面上の座標の点にあるとき,走者はチェックポイントを 1, 2, ... , N の順番に,チェックポイント間は最短距離になるように好きな経路を取る.このとき,「k 番目のチェックポイントを (x, y) に移動する」「チェックポイント a -> b と c -> d の経路のどちらが通り数が大きいか」のクエリに答える問題.

解法

区間の通り数は掛け算によって表され,問題の制約 10^6 では通り数がとても大きくなってしまうので,log を取ることを考える.そうすれば,通り数が小さく済み.通り数も足し算で表すことが出来る.前処理で各区間の通り数を Combination を使って計算し,BIT に入れておく.チェックポイントを移動させるクエリでは,変更したチェックポイントの前後の区間の通り数を更新すればよい.通り数を比較するクエリでは,それぞれの区間の通り数の log の和を BIT で取得すればよい.O(Q log N).

解答

Submission #3221586 - AtCoder Regular Contest 035

7 WA した(区間和を取得する際のミス).

f:id:babcs2035:20180919065423p:plain