AtCoder Regular Contest 080 - F - Prime Flip

F: Prime Flip - AtCoder Regular Contest 080 | AtCoder

メモ

a_{i}x_{i}のところだけ1で、他は0の数列。 b_{i} = a_{i} \oplus a_{i-1}とする。

[l,l+p)を反転するとb_{i}上ではb_{l}, b_{l+p}の2点の反転となる。 よって。 なので

  • b_{i}上での距離が素数の2点は1回の操作で同時に反転できる。
  • b_{i}上での距離が偶数の2点はゴールドバッハの予想より2回の操作で同時に反転できる(ゴールドバッハの予想は少なくとも10^{7}以下の数では成り立つので)
  • b_{i}上での距離が奇数の2点は、1回の操作で距離が偶数の2点に変換できるので、3回の操作で反転できる。

まず、距離が素数になるペアをなるべく多く作る、これにはコスト1かかる。 残った点の中で偶数座標の点同士、奇数座標の点同士でペアを組む、これにはコスト2かかる。 最後に偶数座標と奇数座標が1つずつ残っていたらペアを組む、これにはコスト3かかる。

トータルでかかったコストが答えとなる。 間に合うかどうかしらないが、最小費用流でも解けそう。

感想

自力では全く解けなかったが面白かった。 本番ではずっとa_{i}のまま考えていて、b_{i} = a_{i} \oplus a_{i-1}と変換する発想が全く無かった。 この前作ったPushRelabelの最大流ライブラリがverifyできた。Dinicよりメモリ使用量が多いうえに遅かったが。

gist.github.com