脳log[20220614]

2022年06月14日 (火) [AtCoder] 精進。第１回PAST-J「地ならし」。たぶん緑 diff から水 diff くらいの位置づけだと思うし、PAST は A から始まって K、L 問題あたりまでは順当に解きたいと思っているのだけど、この J 問題は解けずに残っているうちの１問。■最初に考えたのは、中継地点までの最短経路を求めてから、その経路上の任意の１点を始点にしてゴールまでの最短距離を求める方法。だけどたとえば３点のちょうど中間にあるような地点を経由するルートが、２点間距離を考える上では最短ではないけど、総合的には得をするケースがあるような気がする。一度通った道を再度通るときにはコストがかからないからそうなる。スタートとゴールの最短経路を求めてから中間地点に寄り道するように順番を入れ替えても状況は同じ。では盤面の任意の点を始点にして３点までの最短距離を求める場合はどうか。ここまでは過去にも考えている。そのときわからなかったのは、３点までのルートが同じマス目を共有するケースのコストをどう計算するか。■提出 #32470566 (AC / 574 Byte / 95 ms)。AC に至れた今日の気づきは、３点への最短経路のうち２本が共有地点を持つ場合は、その共有地点を始点にした方が(２点への距離に関して)得をするということ。常にどれか２つの最短経路が共有地点を持つ３すくみの状態に陥いって正しいコストが計算できなくなったりしない理由は、やっぱりよくわかっていない。■たぶん詰めて考えれば、３すくみの２つの状況を取り上げて２つの分岐点が異なる点だと仮定すると最短経路だと思っていたものが実は最短経路でないことがわかってじゃあどこに間違いがあったのかを考えれば２つの分岐点が異なる点だと仮定したところにあったりしてなんだ心配していた状況は起こりえない状況だったんだね良かった良かったとなる気がするんだけど、詰めて考えることができないし、直観でありえないと否定もできない。■次は第６回の G「一日一歩」が解きたいなー。第９回までの F 問題まではすでにコンプリートしていて、G、H、I、J のそれぞれに１問だけ解き残しがある。G 問題は解き残しのなかで最弱……のはずなんだけど、過去に何度も解けたと思ったあとで「1 日に複数本の道を使うことはできないことに注意してください」に阻まれている。それを言われてしまうと厳しい制約の三重苦のもとでどういう状態管理が許されるのかわからなくなるんよ。