CS Academy #23 (Div. 2 only) No Prime Sum

Sに含まれる数を頂点とし、その和が素数になるような2値の間に辺を張ったグラフを考える。すべての辺について、端点の少なくとも一方にある数は使わない。いいかえると、使わない数の集合はすべての辺の端点の少なくとも一方を含む。これは頂点被覆。

使わない数を最小にしたいのであった。よって、最小頂点被覆問題が解ければいい。最小頂点被覆問題は簡単に解ける場合がある。二部グラフの最小頂点被覆問題は、二部グラフの最大マッチングをフローで解いたときの残余グラフから簡単に解ける。作ったグラフが二部グラフになっていることを示す。

与えられた数はすべて異なるので2値の和は1+2=3以上であり、3以上の素数は奇数。2値の和が奇数になるのは、一方が奇数であり他方が偶数出る場合に限る。なので、辺の端点の一方は偶数、他方は奇数。