HUPC 2019 Day1 E: 最短経路の復元
0 likes174 views
2019/7/14 北海道大学プログラミング合宿 Day1 (北大セット) E 問題 ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
HUPC 2019 Day1 E: 最短経路の復元
- 1. HUPC 2019, 07/14 北大合宿 2019 Day 1 E: 最短経路の復元 原案: tsukasa_diary 問題文: kazu 解答: monkukui，kazu，tsutaj，tsukasa_diary 解説: kazu
- 2. HUPC 2019, 07/14 問題 - グラフGが与えられない． ?Gの頂点数 N と 二頂点 s と t が与えられる． - G中の二頂点間の最短距離を質問ができるので，適 切に質問を行い，s-t 最短パスを一つ出力せよ． - 質問の回数は高々 5N 回しか行えない． 制約: 1 ≤ N ≤ 500 !2
- 3. HUPC 2019, 07/14 最短路の性質 - s-t 最短路をP = (s, u1, …, t) とする． - s-t 最短路を最短路中の頂点uに対して，s-u 路と u-t 路 に分割すると，それぞれ最短路になる． - なので，dist(s, u) = 1，dist(u, t) = dist(s, t) - 1を満たす 頂点uを見つければ，uは最短路に含まれる． ?この考え方を拡張しよう！！ !3
- 4. HUPC 2019, 07/14 想定解法 !4 s t この分類は2(N - 2)回の質問で構築可能
- 5. HUPC 2019, 07/14 想定解法 !5 s t 全部確かめるとO(N2)回の質問になるため， 全部は確かめられない
- 6. HUPC 2019, 07/14 想定解法 !6 s t この3本だけ確かめる．
- 7. HUPC 2019, 07/14 想定解法 !7 s t この1本だけ確かめる．
- 8. HUPC 2019, 07/14 想定解法 !8 s t この4本だけ確かめる．
- 9. HUPC 2019, 07/14 想定解法 !9 s t この2本だけ確かめる．
- 10. HUPC 2019, 07/14 Writer解，統計 - writer解: ?kazu (c++, 44行) ?monkukui (c++, 53行) ?tsukasa_diary (c++, 26行) ?tsuta_j (c++, 65行) ?tsuta_j (python, 45行) - 統計情報: ?AC 率 ( 58 / 102 ) ?First Accept on-line hamayanhamayan (23:24) on-site hupc_homunokoibito (65:53) !10