競技プログラミング用 知識集積所
ABC448F - Authentic Traveling Salesman Problem
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
Moアルゴリズム※は、複数の区間クエリを並べ替え、隣り合うクエリ間で処理中の区間の移動量を小さくすることで高速化するアルゴリズム。
今回はその移動を決めるアルゴリズムがそのまま使える。
すなわち、領域の横幅をM等分し、1番目を上から、2番目を下から、3番目を上から、……、と回収していけばよい。
今回はその移動を決めるアルゴリズムがそのまま使える。
すなわち、領域の横幅をM等分し、1番目を上から、2番目を下から、3番目を上から、……、と回収していけばよい。
このときの移動時間の合計の最悪値は領域を一辺Lとして、
- 縦方向の移動がML秒
- 横方向の点の間の移動がNL/M秒
- 隣の領域に移動する分L秒
- スタート地点に帰ってくる分L秒（Mが偶数の場合）
の合計である。
これは相加平均と相乗平均の大小関係よりMが√Nのときに最小値2L√N+2L秒となる。
今回の制約ではこれはおよそ9.84*10^9となり、ぎりぎり制限範囲内となる。
これは相加平均と相乗平均の大小関係よりMが√Nのときに最小値2L√N+2L秒となる。
今回の制約ではこれはおよそ9.84*10^9となり、ぎりぎり制限範囲内となる。
もちろんこれではスタート地点が1にならない場合もあるが、巡回路なので先頭が1になるように順送りすればいいだけである。
