B - Simplified mahjong
- この段落、問題読み間違い
- 考えたこと
- これはペアの偶奇が違うので、ペアとは二部グラフのマッチングだから最大二部マッチングかな
- でも頂点が10^5もあるのは大丈夫なのかな
- 複数個同じ数字のカードがあっても、単に容量を増やせばいいだけではある
- 公式解説
- 線形オーダーの解がある
- やはり最大二部マッチングではダメか
- 問題読み間違いに気づいた
- 差の絶対値が「1以下」なので、差が0の時もペアになる
- これを踏まえて小さい方から考える
- 3つまでの塊はどう取っても結果が同じ
- 4つの時、縦に取ると損なパターンがある(左)
- では常に横に取るのを優先したらいいか？それも6の時に反例がある(右)
- 両方のパターンに共通する良くない振る舞い「一番左のペアを取った時点で1個に孤立するカードがある」
- では「孤立するものがないように端から詰めて取る」ならOKか？
- これがOKであることを証明すべきなんだがコンテスト中なら実装してテストケースで試しちゃいそう
- 公式解説: 枚数が非ゼロの区間に分割すると、上記の方法で最大値が最大1枚余るだけであり、それより良い取り方がないことが示せる
- 端から埋める