All about 三角化

いま二次元配列x[i][j]が任意のi, jについてx[i][j] = x[j][i]を満たすとする*1
ﾌﾂｰに作ると(iの上限+1)×(jの上限+1)語ぐらいの記憶域が要るが、常に
　高次側のindex ＜ 低次側のindex
とする約束とせば、
　k = S(i, j) = (i * (i - 1)) / 2 + j
というindex kを設けることで、記憶域を1語も無駄にせずに約半分のサイズに1次元化できる

■ 1語も無駄にならないことの証明
S(i, j) := (i * (i - 1)) / 2 + jとおくと、j = S(i, j) - (i * (i - 1)) / 2。
一方、仮定より0 ≦ j ＜ i。よって、
0 ≦ S(i, j) - (i * (i - 1)) / 2 ＜ i
∴(i * (i - 1)) / 2 ≦ S(i, j) ＜ i + (i * (i - 1)) / 2
∴S(i, 0) ≦ S(i, j) ＜ S(i+1, 0)

もし
　高次側のindex ≦ 低次側のindex
とする約束（＝が有り得る）ならば、
　k = S(i, j) = (i * (i + 1)) / 2 + j
でおk

証明は上と同様、

*1:Indexは0始まりの整数とする