いろはすの競プロ反省会

主に反省してます。たまに役に立つことも書くかも?

Codeforces Round #540 C Palindromic Matrix 〜解法編〜

問題概要

n2個の数 a_1, ... a_{n^2}が与えられる。 それらの数をちょうど一度ずつ使って、上下左右に対称な正方行列を作れるか判定し、作れるならばそのような行列を出力せよ。

いろはすの解法

まず、行列が作れるとして、そのような行列では同じ数がいくつずつ必要なのかを考える。

nが偶数の場合、明らかに、行列に現れる全ての要素は4つずつセットになっている。 すなわち、 (n/2)^2種類の数(重複があっても良い)がそれぞれ4個ずつ必要になる。

問題はnが奇数の場合で、こっちは少しだけややこしい。 サイズが奇数ということは、行と列にそれぞれ「真ん中」が存在する。真ん中の行と真ん中の列が。 よって、

  • 真ん中の行にも真ん中の列にも属さない要素:  (\lfloor n/2 \rfloor)^2種類×4個

  • 真ん中の行、もしくは真ん中の列のいずれか一方のみに属する要素:  2\lfloor n/2 \rfloor種類×2個

  • 真ん中の行と真ん中の列の両方に属する要素: 1種類×1個

もちろん、これらを合計するとn2になることが確かめられる。

一々偶数奇数で分けるのも煩わしいので、まとめて「 m_j種類の数(重複があっても良い)が d_j個ずつ必要」と書く(j=1,2,3)。 ただし、

 d_1=1, d_2=2, d_3=4

である。

あとは、与えられた数の列を適切に分配してやればよい。数 c_i k_i個ずつ与えられている(i=1,...,r)とすると、問題は次のように変形できる:

「大きさ d_jのブロックが m_j個ずつ(j=1,...,3)と、各々の大きさが k_iの箱i=1,...,rがある。全てのブロックを隙間なく箱に収めることは出来るか、できるならその収め方を示せ」

もとの問題を見るとブロックと箱が逆のように見えるが、こちらの方が理にかなっている。 数jは必ず d_j個ずつないと駄目で、 d_j個でワンセットだから「ブロック」なのである。 また与えられた数 c_iは必ずしも k_i個ずつでまとめる必要はなく、別々のところに分配することが可能であるから、むしろこちらが「箱」と考える方が筋が良い。

さて、この問題は、次のアルゴリズムで貪欲的に解くことができる。

  1.  (c_i, k_i) (i=1,...,r)を優先度付きキューに入れる

  2. 大きさ k_iが最も小さい箱 (c_i, k_i)をキューから取り出す

  3.  k_i \geq d_jかつ(箱に入らず)残っている最大のブロック j=j^*を探す。無ければ終了

  4. ブロック j^*を箱iに入れる

  5.  k_i > d_jならば  (c_i, k_i-d_i)をキューに入れる

  6. キューが空でないなら1.に戻る。空なら終了

これを実装したのが以下のコードになる。

Submission #50215161 - Codeforces

今回はここまで。次回は証明編。