同じ席に座れる関係を無向グラフ$G$で表すことにすると、可能な席数を求める問題は$G$をいくつかのクリークに分割する問題と解釈できる。したがって、この問題は最小クリーク被覆問題そのものなので、補グラフの彩色数を求めればよい。
彩色数を求める$O(2^nn)$アルゴリズム:
https://ei1333.github.io/luzhiled/snippets/graph/chromatic-number.html
https://codeforces.com/blog/entry/57496
https://www.slideshare.net/wata_orz/ss-12131479
前の整数を取ったら、次の整数は取れないし、前の整数を取らなかったらだいたい次の整数を取る必要があることに注目してDPする。
後者の場合は必ずしも取らないといけないわけではなく、何回かはパスする必要がある。$N$が偶数の場合はちょうど1回パスするべきで、$N$が奇数の場合はちょうど2回パスするべきである。したがって
$\operatorname{dp}[x][y][z] :=$ $a_1, ..., a_x$まで見て、整数$a_x$を取り$(y=1)$/取らず$(y=0)$、今までにパスした回数が$z$である場合の最大値
としてDPすればよい。ただし例外として、最後の整数$a_N$を取らなかった場合はパスしたとみなす必要がある。
GCJ Round 1Aに出てメモリエラー（？）にハマってしまったのでメモ。
Square Danceのhiddenを落としてしまったのだが、ローカルでいろいろ調べても落ちるケースが見つからない。テストサブミットでしつこく調べていると、どうも入力が大きい時に無条件で落ちているようだった。まさかと思って、dynamic-space-sizeを増やしたSBCLを別に起動して投げてみたら通った。ヘッダを以下のようにする:
(unless (member :child-sbcl *features*)
(quit
:recklessly-p t
:unix-status
(process-exit-code
(run-program *runtime-pathname*
`("--control-stack-size" "128MB"
"--dynamic-space-size" "8GB"
"--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
"--eval" "(push :child-sbcl *features*)"
"--script" ,(namestring *load-pathname*))
:output t :error t :input t))))
必要なサイズを調べてみると
gcすれば通るgcすれば通るgcしなくても通るという感じだった。
しかし、メモリ制約が1GBなのに8GBが必要なのは不可解ではある。たまに起こる現象として、使用量500MBあたりで新たにメモリを確保しようとするときに、1GB以上確保しようとしてheap exhaustedになるというのがあるが、それは2GBや4GBに設定してもだめな理由を説明していない。そもそも、roomとかで調べてもそんなにたくさんメモリを使っているようには見えないし…… ローカルでroswellのsbcl-bin/1.3.14を使っても起きない問題なので、調べるのが難しい。
次のroundの方針は迷うけれど、
dynamice-space-sizeを大きめに設定する。（とりあえず16GB？）(gc :full t)する。（コンパイルでけっこうメモリを使うので）gcする。でいくことにする。
GCJ 2020のSBCLの詳細は以下の通り:
--scriptで実行される）事前コンパイルはないが、今年も長めのTLでまとめてテストするスタイルなので、コンパイル時間のぶんのロスは気にしなくてよさそう。
上の問題は不運ではあったけれど、そもそもPascal Walkをバグらせてしまったのが悪いとも言える。チャンスはまだあるので、早めに気づけてよかった。
区間$[l,r)$に関する掛け算$a_l a_{l+1} ... a_{r-1}$が何回足されるかを数えればよい。区間の右端を揃えて数えると下の表のようになる:
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| $a_1 \cdot 2^3$ | $a_1a_2 \cdot 2^2$ | $a_1a_2a_3 \cdot 2$ | $a_1a_2a_3a_4 \cdot 1$ | $a_1a_2a_3a_4a_5 \cdot 1$ |
| $a_2 \cdot 2^2$ | $a_2a_3 \cdot 2$ | $a_2a_3a_4 \cdot 1$ | $a_2a_3a_4a_5 \cdot 1$ | |
| $a_3 \cdot 2^2$ | $a_3a_4 \cdot 2$ | $a_3a_4a_5 \cdot 2$ | ||
| $a_4 \cdot 2^2$ | $a_4a_5 \cdot 2^2$ | |||
| $a_5 \cdot 2^3$ |
（幅の関係で$N=5$でやったけど、$N=6$くらいのほうがわかりやすいかも）
上の表から、$a_x$を右端とする掛け算の総和から$a_{x+1}$を右端とする掛け算の総和を得るには、だいたい$a_{x+1} / 2$を掛ければよいということがわかる。この係数で帳尻を合わせるために少し改変すると、次のようになる:
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $2^4$ | $a_1 \cdot 2^3$ | $a_1a_2 \cdot 2^2$ | $a_1a_2a_3 \cdot 2$ | $a_1a_2a_3a_4 \cdot 1$ | $a_1a_2a_3a_4a_5 \cdot 1$ |
| $2^3$ | $a_2 \cdot 2^2$ | $a_2a_3 \cdot 2$ | $a_2a_3a_4 \cdot 1$ | $a_2a_3a_4a_5 \cdot 1$ | |
| $2^3$ | $a_3 \cdot 2^2$ | $a_3a_4 \cdot 2$ | $a_3a_4a_5 \cdot 2$ | ||
| $2^3$ | $a_4 \cdot 2^2$ | $a_4a_5 \cdot 2^2$ | |||
| $2^3$ | $a_5 \cdot 2^3$ | ||||
| $2^3$ |
したがって$\operatorname{dp}[0] := 2^{N-1}$で初期化したあと、$\operatorname{dp}[x] := \operatorname{dp}[x-1]\cdot a_{x}/2 + 2^{N-2}$と更新していけばよさそう。ただし、最後だけは$1/2$を掛けずに$\operatorname{dp}[N] := a_{N}\operatorname{dp}[N-1] + 2^{N-2}$とする。
$\operatorname{dp}[1]$から$\operatorname{dp}[N]$までを、不要な$2^{N-2}$を引きながら足していけば、答えが得られる。
端が含まれると足される回数が変わるということを整理するのに時間がかかった。