脳log[20221203]

2022年12月03日 (土) [AtCoder] 精進。今日あったデンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)-F「Pay or Receive」(青 diff)。ヒント、というかほぼ答えを見ました。「へえFってベルマンフォードじゃなくてweighted unionfindってやつ使うのか ルジャンドルも知らなかった」「F: 初見ベルマンフォードかなと思ったけど、制約で間に合わないので却下。辺のコストからポテンシャル定義できることに気づいて、ポテンシャル付きUnionFindを着想。無限にできるかは、閉路ができた時の相対高さで判断できる」 一応自分でも UnionFind の可能性が頭をかすめていたけど、構成する辺のコストの和が非ゼロになるサイクルがあるときでも、サイクルから伸びた腕の中では inf 以外の答えが定義されるような気がして、強連結成分分解が必要だと考えてしまった。解ける可能性はなかった。■提出 #37002677 (AC / 758 Byte / 433 ms)。バグなしで完成してびっくり。UnionFind と言いながら公開関数は U(nite) 関数と DD 関数の２つ。F(ind) 関数は内部でしか使わないので非公開。DD 関数を difference between distances from a root から命名したんだけど、ルートからの距離(D)とは別に２点間距離をあらためて D(istance) と命名しても良かったなとどうでもいい後悔をしている。うまくすれば場合分けが省けるかなと期待して負の無限大を値として使用したけど、無限大と無限大の差から NaN を作ってしまうしょうもないバグを踏みそうで結局 if/finite?/infinite? による場合分けが避けられなかったのが残念。