脳log[20220629]

2022年06月29日 (水) [AtCoder] 精進。第10回PAST-O「3-順列」。やりたいことは比較的わかりやすいと思う。グラフがあって、二部グラフとそうでないものがある。N 個の３の剰余があって、０と１、２ がある。０はどんなグラフにも当てはめられるけど、特に二部グラフでないものには剰余が０になる数しか割り当てられない。なのでまず余りが１と２になる数を最大限二部グラフに割り当てる。孤立した頂点にも１と２を割り振る。１と２を使い切って残りが０だけになったら、残ったグラフに割り当てて答えは Yes。二部グラフでないものに１か２を割り振るようでは答えは No。■提出 #32841134 (AC / 1176 Byte / 301 ms)。実装が難しかった。二部グラフに１と２を割り当てる方法。使った１と２の数で二次元二値の DP をして、使った個数の和を最大化すればいい。それがわかってもいざ実装すれば３つも４つもバグり散らかしていてデバッグに大変苦労した。