Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 149 C問題 Avoid Prime Sum

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を満たすような二重添字整数列  A=(A_{i,j})_{1 \leq i,j \leq N} を一つ求めよ.

  •  1 \leq A_{i,j} \leq N^2 である.
  •  k=1,2, \dots, N^2 に対して,  A_{i,j}=k となる整数の組  (i,j) が唯一存在する.
  •  N N 列のマスにおいて, 上から  i 行目, 左から  j 行目に整数  A_{i,j} を書き込んだ場合, どの上下左右に隣接する2つのマスに書かれている整数の和も素数ではない.

制約

  •  3 \leq N \leq 1000

解法

 N \geq 6 とする.

 A_{i,j}=1 となる  (i,j) は1回しか登場しないことから, 和が偶数ならばそれは必ず  3 以上の偶数であるから, 素数ではない. また, 2つの整数の和が偶数になるということは, 両方とも奇数か, 両方とも偶数である.

このことから, 奇数と偶数をそれぞれ同じ様な場所にまとめると多くの和のパートを偶数で乗り切ることが出来る.

そこで,  N \times N のマス目のうち, 上半分を奇数, 下半分を偶数にすると, 奇数と偶数の境界を除けば全て和が偶数になっている. よって, 後はこの境界部分をクリアできればよいことになる.

さて, これまでは  2 の倍数を目指したので, 次は  3 の倍数を目指すことにする. 今  N \geq 6 であるから, 1 以上  N^2 以下の整数の中に,  3 の倍数であるような奇数, 偶数はそれぞれ  N 個以上存在する. よって, 3の倍数であるような奇数と偶数をそれぞれ  N 個ずつ選び出し, これらを境界部分にあるマス目に配置すれば, 境界部分の和が  9 以上の  3 の倍数となり, これは素数ではない.

よって, 全ての和を  3 以上の  2 の倍数または  9 以上の  3 の倍数にすることができたので, これで目標を達成できた.

なお,  N=3,4,5 の場合は 1 以上  N^2 以下の整数の中に,  3 の倍数であるような奇数, 偶数が  N 個存在せず, 上の  3 の倍数を目指す方法がそのままでは適用できないが, このような場合でも和が  3 の倍数になるような奇数と偶数の組を自力で見つけることによって目標を達成できる.