AGC003B

https://gyazo.com/3776cb4be722fd46b0626492d7a6a6c3

この段落、問題読み間違い

考えたこと

でも頂点が10^5もあるのは大丈夫なのかな

複数個同じ数字のカードがあっても、単に容量を増やせばいいだけではある

公式解説

線形オーダーの解がある

やはり最大二部マッチングではダメか

問題読み間違いに気づいた

差の絶対値が「1以下」なので、差が0の時もペアになる

偶奇で二部グラフにするのは根本的に間違ってる

これを踏まえて小さい方から考える

3つまでの塊はどう取っても結果が同じ

4つの時、縦に取ると損なパターンがある(左)

https://gyazo.com/f9ca41f0dc1100449c1b4af2a65967c0

では常に横に取るのを優先したらいいか？それも6の時に反例がある(右)

両方のパターンに共通する良くない振る舞い「一番左のペアを取った時点で1個に孤立するカードがある」

では「孤立するものがないように端から詰めて取る」ならOKか？

これがOKであることを証明すべきなんだがコンテスト中なら実装してテストケースで試しちゃいそう

公式解説: 枚数が非ゼロの区間に分割すると、上記の方法で最大値が最大1枚余るだけであり、それより良い取り方がないことが示せる