脳log[20230124]

2023年01月24日 (火) [AtCoder] 精進。ABC286-G「Unique Walk」(黄 diff)。おめでたいことがあったらしいです。「bk_cocoaさんのウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)での成績：248位 パフォーマンス：2111相当 レーティング：1140→1283 (+143) :) Highestを更新しました！ #AtCoder #ウルシステムズプログラミングコンテスト2023(ABC286) https://t.co/043KXpCjAX」。A-EG の６完らしい。G 問題の AC 抜きでも「終了 30 秒前にようやっと５完を確保した」自分では勝負にならない。F も G も問題を読む時間さえ作れなかった時点で負けが確定している。素直にすごい。F がダメでもあわよくば G を狙うという姿勢がなければ望めない結果ですよ。■提出 #38290988 (AC / 456 Byte / 374 ms)。必ず１回だけ通らなければいけない辺がある。No になる条件は何か。最小の例はたぶん４頂点３辺の星型のグラフですべての辺を一度だけ通らなければいけないもの。条件付きの辺を一旦とりわけてその他の辺が作るグラフとの関係を考える。１回だけの辺が結ぶ２頂点が同じ連結成分に属するなら代替経路があるということで、その辺はあってもなくてもいい存在であり１回だけ通ることも自由にできる(通った後で元の頂点に戻ってくることで通った結果をキャンセルできるので)。異なる連結成分を結ぶならその辺は橋であり代替経路が存在しない。ただし代替となる橋が存在する可能性はある。ひと筆書きできるかどうかは頂点の次数の偶奇を見ればわかるというのは有名な話>「ケーニヒスベルクの七つの橋問題」。解けると信じて臨んだ結果解けました。負けないっ。