GCJ2018 Qual D 考察

原点が立方体の中心だと面倒なので立方体の頂点において問題を次のように定式化する:

Minimize/Maximize Area(Span({O, Ce1, Ce2, Ce3, C(e1+e2), C(e2+e3), C(e3+e1), C(e1+e2+e3)}))
Subject to
  B: 3x3 signed orthogonal matrix
  C = [1 0 0; 0 1 0] * B

ここで上記の頂点のうちいずれか一つは凸包の内部にある(正確には、それを取り除いても凸包が変わらない位置にある)。そこで対称性よりそれが原点の射影である場合のみ考えればよい。すなわち:

Minimize/Maximize Area(Span({Ce1, Ce2, Ce3, C(e1+e2), C(e2+e3), C(e3+e1)}))
Subject to
  B: 3x3 signed orthogonal matrix
  C = [1 0 0; 0 1 0] * B
  cross(Ce1, Ce2) >= 0
  cross(Ce2, Ce3) >= 0
  cross(Ce3, Ce1) >= 0

このとき凸包は六角形で、これは原点を基準に3つの平行四辺形の面積の和として以下のように書ける。

Minimize/Maximize cross(Ce1, Ce2) + cross(Ce2, Ce3) + cross(Ce3, Ce1)
Subject to
  B: 3x3 signed orthogonal matrix
  C = [1 0 0; 0 1 0] * B
  cross(Ce1, Ce2) >= 0
  cross(Ce2, Ce3) >= 0
  cross(Ce3, Ce1) >= 0

ここで行列Bを要素表示して [b11 b12 b13; b21 b22 b23; b31 b32 b33] と表すと、符号つき直交行列の性質から cross(Ce1, Ce2) = cross([b11; b21], [b12; b22]) = b33 ... がわかる。これにより以下のような書き換えができる。

Minimize/Maximize b31 + b32 + b33
Subject to
  [b11 b12 b13; b21 b22 b23; b31 b32 b33]: 3x3 signed orthogonal matrix
  b31 >= 0
  b32 >= 0
  b33 >= 0

この問題は [b31 b32 b33] にしか依存していない形になった。Gram-Schmidtの直交化により、 [b31 b32 b33] が単位長でさえあれば対応する B が存在するので、以下のような書き換えができる。

Minimize/Maximize b31 + b32 + b33
Subject to
  [b31 b32 b33]: nonnegative vector with unit length

これにより単純な幾何的な最適化になった。これを解くと

最小値: [b31 b32 b33] = [0 0 1] のとき、 1
最大値: [b31 b32 b33] = [sqrt(1/3) sqrt(1/3) sqrt(1/3)] のとき、 sqrt(3)

となる。

実際に復元するにあたっては s = b31 = b32 <= b33 = t として解くと

2s + t = A
2s^2 + t^2 = 1

を解いて

s = (2A - sqrt(6 - 2A^2))/6
t = (A + sqrt(6 - 2A^2))/3

となる。

これをもとに直交化すれば B が復元できるが、これは対称性をうまく利用すると

[(t+1)/2 (t-1)/2 -s;
 (t-1)/2 (t+1)/2 -s;
       s       s  t]

という比較的単純な式で与えることができる。

qnighy/gcj2018-qual-d.md

GCJ2018 Qual D 考察