今日解いた競プロの問題。

ABC229-F: 観覧車みたいな形のグラフを切って二部グラフにしろという問題。

最初は各辺を切っていく方針で考えていたが、「頂点0, i, i+1の為す三角形のどこかを切る」だけでは必ずしも二部グラフにならないことに気付く。例えばNが奇数の場合、全ての頂点(0, i)の辺を切っても二部グラフにならない。切っていく方針でちゃんと考えようとすると、これまで切ってきた辺の全体を把握しなければいけなくなってくる。これは厳しい。

そこで、各頂点を塗り分ける感じの方針で行くことにする。こうすれば各頂点について、既に色を決めた隣接頂点と色が同じなら切る、違うなら切らない、とするだけで間違いなく二部グラフになってくれる。

二部グラフは辺よりも頂点に着目した方が良いということを学んだ。この前の競プロ典型90問-83とかもそうだが、対等な立場であるはずのもの(今回はグラフの頂点)に無から属性を見出して振り分けるようなやつはどうも慣れない。

---

本当に何にもタスクが進まないまま一日が終わっていく。よく寝て、食事もとっているつもりなのに。