昨日解いた競プロ典型90問-083について頭でちょっと整理した。

どの頂点も、「更新」時にある程度頑張ることには変わりがない。では2通りの頂点で何が違うのかというと、自分の色の「取得」を「自力で頑張る」か、「周囲の更新に押し付ける」かのどちらかという部分が異なる。

「自力で頑張る」頂点が多すぎると、次数の多い頂点の取得が繰り返されたときに苦しくなる。一方「周囲の更新に押し付ける」頂点が多すぎると、更新時に苦しくなる。そういうトレードオフだ。

「自力で頑張る」頂点は次数が少ないところ、「押し付ける」頂点は多いところにした方が良いということになる。ここで、ぶっちゃけどの頂点も次数があまり多くなければ全ての頂点で自力で頑張ってしまっていい。「押し付ける」必要のある頂点が一つもなければこんな場合分けは要らない。

自分が一番分からなかったのが「√Mよりも少なければ」という条件にする発想にどうしたら自然に至れるのかというところだったのだが、「押し付ける」必要のある頂点は絶対に少ないはずでありその根拠を探し出せ、という思考回路で行けば自然な発想なのかなと思った。その結実として「辺の本数はM本なのだからB本以上の次数を持つ頂点はM/B個以下である」という話が出てくる。