308.1

二部グラフマッチングだと信じていたのに...。

1000

ボルトの大きさが与えられる。大きさNのボルトには大きさNのナットが存在することが分かっているが、大きさN-1とN+1のいずれのナットもマッチする。この状況下で適当にマッチさせた結果、マッチしないボルトの可能な最大数を答えよ、という問題。

NとN+1とN+2があったときに、NとN+1をN+1とN+2をマッチさせると1つ余る。後はこれを最大化するだけの問題。三つ組の最小値がNとMの二つの三つ組があったとすると、N=M+1やN=M-1のような三つ組は両立しない。N=M+2やN=M-2のような三つ組だと、共有するものの数が上限になってうまく組めないことがある。後はこれをDPでテーブル埋めて、最大値求めるだけ。