Codeforces Round #540 C Palindromic Matrix 〜解法編〜
問題概要
n2個の数が与えられる。 それらの数をちょうど一度ずつ使って、上下左右に対称な正方行列を作れるか判定し、作れるならばそのような行列を出力せよ。
いろはすの解法
まず、行列が作れるとして、そのような行列では同じ数がいくつずつ必要なのかを考える。
nが偶数の場合、明らかに、行列に現れる全ての要素は4つずつセットになっている。 すなわち、種類の数(重複があっても良い)がそれぞれ4個ずつ必要になる。
問題はnが奇数の場合で、こっちは少しだけややこしい。 サイズが奇数ということは、行と列にそれぞれ「真ん中」が存在する。真ん中の行と真ん中の列が。 よって、
真ん中の行にも真ん中の列にも属さない要素: 種類×4個
真ん中の行、もしくは真ん中の列のいずれか一方のみに属する要素: 種類×2個
真ん中の行と真ん中の列の両方に属する要素: 1種類×1個
もちろん、これらを合計するとn2になることが確かめられる。
一々偶数奇数で分けるのも煩わしいので、まとめて「種類の数(重複があっても良い)が個ずつ必要」と書く(j=1,2,3)。 ただし、
である。
あとは、与えられた数の列を適切に分配してやればよい。数が個ずつ与えられている(i=1,...,r)とすると、問題は次のように変形できる:
「大きさのブロックが個ずつ(j=1,...,3)と、各々の大きさがの箱i=1,...,rがある。全てのブロックを隙間なく箱に収めることは出来るか、できるならその収め方を示せ」
もとの問題を見るとブロックと箱が逆のように見えるが、こちらの方が理にかなっている。 数jは必ず個ずつないと駄目で、個でワンセットだから「ブロック」なのである。 また与えられた数は必ずしも個ずつでまとめる必要はなく、別々のところに分配することが可能であるから、むしろこちらが「箱」と考える方が筋が良い。
さて、この問題は、次のアルゴリズムで貪欲的に解くことができる。
を優先度付きキューに入れる
大きさが最も小さい箱をキューから取り出す
かつ(箱に入らず)残っている最大のブロックを探す。無ければ終了
ブロックを箱iに入れる
ならば をキューに入れる
キューが空でないなら1.に戻る。空なら終了
これを実装したのが以下のコードになる。
Submission #50215161 - Codeforces
今回はここまで。次回は証明編。