脳log[20230208]

2023年02月08日 (水) [AtCoder] 精進。埋めきれずに穴が空いていた ABC035-D「トレジャーハント」(水 diff)。ちょっと考えて気が付いてほしいんだけど、滞在する町は１つに決めていい。複数の町に滞在する理由はない。あとは往路と復路に分けて町１からの最短距離がわかればいいのでダイクストラ法を２回やる。えっと、なんで埋められなかったの？>過去の自分■提出 #38710483 (AC / 1026 Byte / 480 ms)。■もちろん経験からつまずきポイントを３つまで挙げることができる。１つ目は「なんで滞在する町を１つに決めていいの？」 たとえば町１を出て町１に返るパスが与えられたとして、滞在する町はパスにある町のうち１分あたりの報酬が最高の町一択になるでしょう。２つ目の疑問は「そうはいってもどのパスが答えになるかはわからないじゃない？」 視点を変えて、ある町に滞在すると決めてからその町での滞在時間を最大化するパスを考える。それはグラフでおなじみ最短経路問題になる。３つ目の疑問は「町 A に滞在すると決めて最短経路を求めたら経路にある町 B の滞在報酬の方が大きかったりしそうなんだけど？」 それは町 B に滞在すると決めたときに考える範囲なので無視して大丈夫。４つ目の疑問は「すべての町について町１に返る最短距離を求めると時間がかかりすぎるんだけど？」 辺の向きを逆にしたもうひとつのグラフで町１を始点にした最短距離を１回だけ求める。■たぶん１年半前の自分は３番目の疑問に答えられなくて分割した問題が解けなかったのだと思う。別の問題に対する感想だけど「難しいなこれ。ある時点のループにおいてベストを求めなくていいし不正確でもいいということを見極めて受け入れるのは」「自分はこの手の見極めが苦手みたいだ」と書いたように、問題を分割したにもかかわらず分割した枠の外にあるより良い解に目移りしてしまって問題が解けなくなってしまうところが８か月前までの自分にはあった。