差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0113_keyence2019 [2019/01/24] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0113_keyence2019 [2019/04/17] (現在) – [解法] ikatakos | ||
|---|---|---|---|
| 行 36: | 行 36: | ||
| * 各都市につき、自分から繋ぎにいく候補道路は、多くとも左右それぞれ1本ずつでよい | * 各都市につき、自分から繋ぎにいく候補道路は、多くとも左右それぞれ1本ずつでよい | ||
| - | | + | * あくまで「自分より規模の小さい都市」の中の話で、他の規模の大きい都市から自分が繋がれる対象になることはある |
| + | | ||
| * 理由は以下 | * 理由は以下 | ||
| * 次の2つを念頭に置く | * 次の2つを念頭に置く | ||
| 行 46: | 行 47: | ||
| * なので、最長は、$w$ から出る2本の内のどちらか。この2本の比較で長い方は使われない | * なので、最長は、$w$ から出る2本の内のどちらか。この2本の比較で長い方は使われない | ||
| * これを任意の2都市でやっていくと、結局はその中でコスト最小の辺しか使われない | * これを任意の2都市でやっていくと、結局はその中でコスト最小の辺しか使われない | ||
| + | * 右も同様 | ||
| で、規模の小さい都市から更新しつつ区間の最小値を求めるにはセグメント木を使えば良いのだが、Pythonではそれでも遅い。 | で、規模の小さい都市から更新しつつ区間の最小値を求めるにはセグメント木を使えば良いのだが、Pythonではそれでも遅い。 | ||
| 行 53: | 行 55: | ||
| 証明がよくわかっていない。 | 証明がよくわかっていない。 | ||
| - | サンプル4などを、実際にどの都市とどの都市が結ばれるのかやってみると、面白い結果になる。 | + | サンプル4などを、実際にどの都市とどの都市が結ばれるのかやってみると、特徴的な結果になる。 |
| , | , | ||
| 行 86: | 行 88: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | 数学問題? | + | 数学問題? |
| - | 解説の解法は、読めば簡単に理解出来るくらい単純ですごい！綺麗！となるんだけど、自力ではどうすれば浮かんでくるものか。 | + | 解説の解法は、読めば簡単に理解出来るくらい単純ですごい！綺麗！となるんだけど、思いつかんわ……。 |
| $H,W$ が大きいので、1マス毎に数えるのは、動的計画法などを使っても無理。 | $H,W$ が大きいので、1マス毎に数えるのは、動的計画法などを使っても無理。 | ||
