脳log[20220601]

2022年06月01日 (水) [AtCoder] 精進。ABC131-E「Friendships」(水 diff)。苦しんでいた時間の半分以上で木を構築しようとしていた。そうではなく、自己辺と多重辺がないグラフでいい。つい先日(20220526)「Tr/ee」を解くのにキャタピラ木を構築していたのに引きずられている。最短距離が２の頂点ペアが最も少なくなるのが直線状の木で、最も多くなるのが星型の木なんだけど、木は条件じゃあなかった。(木に限らない)グラフが構築できる上限は星型の木と同じだったけど、下限はゼロであり存在しなかった。■提出 #32150851 (AC / 522 Byte)。根本的な軌道修正はできなかった。当初の方針通り三角数と K の値を見比べて星型と直線状のバランスを取りながら頂点を１つずつくっつけていった。「Tr/ee」を解いたのと同じ方針。judge.rb27 を書いたのも同じ。■「Ruby でのすべての提出」を見ると一番短いのがこちら>提出 #6356157 (193 Byte)。すごく単純な二重ループ。■この問題は完全グラフをスタート地点にするのがわかりやすい。全頂点間の距離が１の状態をスタートにする。ここで A-B 間を直接つなぐ辺を取り除くと A-B 間の最短距離がどうなるか。ほぼ完全グラフなのであらゆる経路あらゆる距離が考えられるけど、距離１だけが実現できない。という感じで、グラフが連結を保つための最低限の辺を残すことに注意しながら、任意の２頂点間を結ぶ辺を K 本取り除けば答えが出る。■提出 #32158282 (AC / 234 Byte)。思いついてから実装完了まで 10 分 15 分でバグも無し。昨日４時間以上苦しんでいたのはなんだったのか。■「という感じで」とか書いて雰囲気で流してしまったけど、星型のハブになる頂点を選びそこに繋がる辺を残すようにうまいこと辺を取り除かないと最短距離２が保証できなくなるっぽい。さっきの提出が AC になったのは頂点ペアの持ち方、取り除き方の２つの偶然が重なった結果なのかも。参考「競プロ参戦記 #53 Friendships | ABC 131 - Qiita」