ARC 201-300/ARC208D - Symmetric Matrix - 競技プログラミング用 知識集積所

---

問題

ARC208D

必要知識

簡単な内容は省略

• 考察問題

考え方

考察問題。
条件を満たすをNxNサイズの方陣を作れというもの。

条件は、数式で書かれているのを日本語に直すと

• 各マスの値は1以上N以下である
• 左上と右下を結ぶ対角線で対称
• 同じ行の中身は全て異なる（対称条件から、行にも同じことが言える）
• 各行、指定の位置に1が入っている

というもの。

まず、できないパターンの考察。

明らかにできないものとして、1の位置が対称性を満たしていない場合。
これは、Yのi番目がjなら、Yのj番目がiになっているかどうかを全て確認すればよい。
このとき、i=jであるものは、ただ対角線上にいるだけなので、存在してもかまわない。
Yの値にかぶりがあるケースはここに全て含まれる。

また、少し考えないといけないものとして、Nが奇数でありながら、対角線上の1指定が1ヶ所以外の場合がある。
Nが奇数の場合、数kの個数も奇数である。
しかし、対角線上以外にある数は、全て2個1組になっているはずである。
つまり、どの数も対角線上に1つずつという形でなければ対称性が成り立たない。
よって、対角線上の1指定が1ヶ所以外の場合は不可能である。

以上に該当しない場合は、必ず構成できる。
このとき、最初から1の位置を完全に合わせる必要はない。
というのは、1からNまでの順列であるfに対して、「i行目をf[i]行目に、j列目をf[j]列目に移動」とすると、対称性を崩さず、対角線上の1の個数が変わらない範囲で1を自由な位置に移動できるから。
つまり、対角線上の1の個数だけあっているものを構成できれば、あとは適切なfを用いてそれを少し作り替えることで、1の位置が全てあっているものを簡単に構成できる。

ということで、対角線上に指定個数1があるものの作り方。

まず、Nが奇数の場合。
この場合、指定個数は必ず1である。
i行j列（0-indexで）のマスを(i+j+1)%N+1とすれば完了。
右上から左下にかけての対角線上に1が並ぶので、fも作りやすい。
これで奇数の場合は達成。

次に、偶数の場合。（後でN=6の例も掲載）
この場合、指定個数は必ず偶数である（対角線上にkが奇数個だと、全体でもkが奇数個になってしまう）。

まず、以下のようなもの（tmpとする）を作る。

• 右上から左下にかけての対角線上に1が並ぶ
• 左上から右下にかけての対角線上に並ぶ数が、上からと下からで対称

Nを可能な限り2で割って、最後に残る奇数をdとする（n=2のs乗*dの形にする）。
dxdサイズの方陣を、奇数のときの方法で作成する。
次に、2dx2dサイズの方陣を、次の手順で作る。

• 右上と左下の1/4ずつには、上で作ったdxdサイズのものをそのまま配置
• 左上と右下の1/4ずつには、上で作ったdxdサイズのものに、全てにdを足して配置

以下、4dx4dサイズ、8dx8dサイズ、とNxNになるまで繰り返して拡大していく。
ここまでの作業は、諸々の考察を重ねると、iとjをそれぞれdで割った商と余りを使って

tmp.at(i).at(j) = (qi^qj^((1<<s)-1))*d + (ri+rj+1)%d + 1;

で一発で作れる。
最後に、tmpの中心と右下角を結ぶ線分上にあるdxdサイズの方陣を、すべて180度反転する。
（実装上、上の計算の前にrを書き換えてしまうのがやりやすい）
これは、各dxdごとに独立性の高い方陣になっていることにより可能になっている。

これで、tmpは作れた。
そして、1を対角線上に移動する。
tmpの中心から対角線上を等距離行った位置（正方形をなす）の4点の値は斜め同士一致しているので、これら4点の値を逆にしても対称性は崩れない。
したがって、対角線上に2m個の1が必要な場合、その入れ替えをmセットやればよい。
これで偶数の場合も達成。

ということで、Nが奇数の場合も偶数の場合も、指定個数の1が対角線上にあるものは作れた。
あとは前述のとおり、適切なfを用意して、1が適切な位置に来るようにすればよい。

N=6の場合は、以下のようになる。
まず、6/2=3なので、3x3サイズのものを用意する。

2	3	1
3	1	2
1	2	3

（0-indexとして）左上は0行0列なので、0+0+1=1を3で割った余りに1を足して、2。
右中央は1行2列なので、1+2+1=4を3で割った余りに1を足して、2。
という感じ。
これを、2倍サイズにする。

5	6	4	2	3	1
6	4	5	3	1	2
4	5	6	1	2	3
2	3	1	5	6	4
3	1	2	6	4	5
1	2	3	4	5	6

3x3サイズを、右上と左下の3x3（青色）にはそのまま、左上と右下（赤色）には3を足して配置する。

そして、中央から右下方向にある3x3を、180度反転する。

5	6	4	2	3	1
6	4	5	3	1	2
4	5	6	1	2	3
2	3	1	6	5	4
3	1	2	5	4	6
1	2	3	4	6	5

もし、左上と右下を結ぶ対角線上に1が4個必要なら、対角線上の4点を使った正方形を2つ選び、頂点上の数を逆にする。

5	6	4	2	3	1
6	1	5	3	4	2
4	5	1	6	2	3
2	3	6	1	5	4
3	4	2	5	1	6
1	2	3	4	6	5

入力が

6
1 2 3 4 6 5
（0-indexで0 1 2 3 5 4）

だった場合は、対角線に1を用意できた場所に0から3を、対称位置に1がある組に4と5の組を割り当てるようにfを作ればよい。
つまり、例えばf[0]=4, f[1]=0, f[2]=1, f[3]=2, f[4]=3, f[5]=5とすればよい。
tmpの0行0列は実際の結果の4行4列に、tmpの2行4列は実際の結果の1行3列に、と配置換えをすればよい。

1	5	3	4	6	2
5	1	6	2	4	3
3	6	1	5	2	4
4	2	5	1	3	6
6	4	2	3	5	1
2	3	4	6	1	5

これで完成。

解答例

解答例

注意点

別解

round-robin方式を使う

これは、実はある面白い問題と同等である。
それは、以下の問題。

N人のプレイヤーが1対1での総当たり戦を行う。
全N回戦を行い、各プレイヤーは他のn-1人と1回ずつ戦い、1回は休みである。
何回戦目に誰と誰を対戦させるか決定せよ。
ただし、1回戦の組み合わせは指定のものとせよ。

この問題の行列のi行j列の値がkであることを、i番の選手とj番目の選手がk回戦に対戦する（i==jならk回戦は休み）ことと読み替えれば同一である。

これは、以下の方法で解ける。

Nが奇数の場合。
N人全員を円形に並べる。
ある1人を休みとし、その人から見て「左1人目と右1人目」「左2人目と右2人目」……という組み合わせで対戦させる。
これを、だれを休みにするかでN通りやると、条件を満たす。
1回戦目が指定の組み合わせなのは、人の並び順の決め方で対応すればよい。

Nが偶数の場合。
まず、1回戦は指定の通りにとりあえずやってしまい、2回戦からN回戦までを考える。
ある1人を除いたN-1人を円形に並べる。
除かれた1人が、N-1人の中から対戦相手を指名し、その組で対戦させる。
さらに、指名された人から見て「左1人目と右1人目」「左2人目と右2人目」……という組み合わせで対戦させる。
ただしこのとき、対戦カードが1戦目で行われたものと同一だった場合、両者を休みとする。
除かれた1人が誰を指名するかでN-1通りやると、条件を満たす。
解答例