既存投稿一覧ページへのリンク
雑記
C問題はBFS問題、D問題は解法知ってるか問題なので、後回し。
2時間くらいやって、Youtube解説見て、ようやく解法が見えてきたけど、最後の詰めが試せてない。。。(2025年6月21日22時30分現在)
正確には、解法は分かるけれど、総当たり対策だから、まずTLEするだろうなぁ～ってパターン。
まぁ、ここらへんは、10問くらい類題解けばパターンが見えて来ると思うので、忘れない間に解法を記録しておきます。
E問題解法アプローチ
例1（下記の入力例）
7 16
4 7 13
1 5 10
6 5 13
5 7 12
3 6 4
1 4 12
6 7 4
3 4 11
1 6 4
5 4 19
7 1 20
4 2 1
6 4 15
7 2 16
6 2 4
2 3 13
1 1 2 4 4
3 3 5 5 7
→ 解：32
まず、前述のグラフを可視化すると、下記の様になります。
で、最小パスの重みの中から、決められた範囲の最大の重みを求めろという問題なので、
先に最小パスを求めておきます。
【Step01】
ここらへんは、最小全域木やUnionFindでさんざんやった問題だし、手作業でトレース出来る問題にしているので、下記のように求めます。
蛇足ですが、手でトレース出来るようにしておくと、アルゴリズムの理解が100倍くらい早く出来ますね。
【Step02】
残った木の中から、
Startポイント[1 1 2 4 4]
Endポイント[3 3 5 5 7]
をいい感じに組み合わせて、パスの重みが最大になるよう設定しろという問題ですね。
ノードが7つくらいであれば、目視で出来るし、目視で出来るということは、総当たりで解答を求められるはずなのですが、まぁTLEするでしょうな。
UnionFindを使えば解けるっぽいので、「理解できるまで繰り返す」の精神で何パターンか類題といて対策することにします。
なんだかんだと今週ずっとこの問題と相対していたような気がするので、また後日。解答方針さえ目処が付けば後は、繰り返しとパターン発見で乗り切れるはずっ！