competitive: 9月 2021

2021年9月12日日曜日

前提

収穫機を買うのをどこでやめるか問題はしばらく考えずに、収穫機も資金に換算したスコアで物事を考えることにした。

評価関数

収穫機を設置/撤去する場所の持つべき望ましい性質を列挙して、それらの組み合わせで評価関数を作る。評価はマス毎に行い、価値の高いマスに収穫機を設置して価値の低いマスから収穫機を撤去する貪欲法を前提とする。また、理想的には、収穫機のあるマスの価値の総和を取ると盤面の価値になっていてほしい。

以下の評価関数に従って貪欲法をするとして、収穫機を買うのを止めるタイミングを全探索すると2.6億程度のスコアになった。

マスの価値

基本的には設定の通り、マスを覆う連結成分のサイズ×野菜の価値がそのマスの価値と考えるとよさそう。まだ出現していない野菜については時刻が離れると価値が指数的に下がるとして調整した。時刻の値は野菜の出現日と消失日の2種類があるが、消失日に従って下がるとしたほうがよかった。

また、既に出現している野菜についても、やはり消失日が遠いと価値が指数的に下がるとしたほうがスコアがよいようだった。

マスの価値の伝搬

現在か近い未来に価値の高い野菜が生えるマスの周辺は価値が高いと考えられる。ただ、具体的に価値をどう伝搬するかが問題だった。周辺にどれだけ野菜が多かろうと1ターンで覆えるマスは1つだけなので、野菜が多いエリアを過大評価しないようにする必要がある。

いろいろ試した結果、最大連結成分からの最短経路DAGを作って、その逆順に各頂点 $v$ に $\max_{pはvの親頂点}(pの価値)$ に減衰率を掛けたものを加算していくことにした。

これだと距離について指数的に価値が減っていくことになるけれど、価値が3倍なら3ターン掛けてでもいくべき、と考えると反比例で減っていくほうが自然に思える。ただ、こちらは高速な表現ができなかった。
最大連結成分から到達する前に消失してしまう野菜の価値は伝搬しないようにする。

連結していることの価値

収穫機の連結性は維持したい。これを収穫機のないマスについて言い換えると、連結成分の隣は価値が大きい。収穫機のあるマスについて言い換えると、連結成分の関節点は非関節点より価値が大きい。

収穫機が数個のうちはいくつかの連結成分に分離して遠くの野菜を取りに行く可能性も考慮するつもりだったが、試してみるとそれで得られる利益がほぼないことがわかったので、最終的にはひとつの連結成分を伸縮することを前提とした方針に変えた。つまり、評価関数に含めるのではなく、収穫機を撤去するマスは非関節点で、収穫機を置くマスは連結成分の隣とした。

また、下記のビームサーチをする際には収穫機のあるマスの価値の総和を盤面の価値としたが、この時は非関節点が多い配置のほうが（次の撤去候補が多いぶん）やや良いという考えに基づいて、非関節点の評価値に1より少し大きい定数を掛けた。

ビームサーチ

上の評価関数を調整すると、局所的には明らかな問題が見つからなくなった。大きな改善があるとしたら「この日は上のほうに収穫機が集まっているけれど、長期的には実は下に集まったほうが得だった」のような状況をできるだけ減らすくらいで、これは適切に状態をまとめてビームサーチすることで実現できそうと思った。

ビームサーチの前提として似た盤面をまとめるために、全体を8×8の4個の領域に区切って、各領域に収穫機が何個あるかで盤面を同一視することにした。ただ、序盤についてはこの同一視はやりすぎで、区切る領域を少し増やしたほうが良いようだった。最終的には時間経過で16個→5個→4個と分割数を減らすように調整した。

終盤のほうが重要なのでビーム幅は終盤に大きいほうがよく、幅30から幅150まで増えていくようにした。

まだ収穫機を買うのをいつ止めるかという問題が残っている。今度は収穫機の調達数で全探索するわけにもいかないので、830日目以降は買わないという単純な仕組みにした。ここは時間があればもう少し詰めたかった。

2021年9月2日木曜日

ARC 126 E - Snack

問題
AC

子供 $i$ が種類 $j$ の菓子を $x_{i, j}$ 個もらうとすると、与えられた問題は以下の条件で $\sum x_{i, j}$ を最大化する問題と考えられる:

$\sum_{j=1}^Nx_{i,j} \le C_i \qquad\forall i \in [M]$
$\sum_{i=1}^Mx_{i, j} \le A_j \qquad \forall j \in [N]$
$0 \le x_{i, j} \le B_i \qquad \forall i \in [M], \forall j \in [N]$
$x_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$

ただし、 $[M] = \{1, 2, ..., M\}, [N] = \{1, 2, ..., N\}$ 。実は4の整数制約は外してもよい。つまり、このILPの最適解はLP緩和の最適解にもなっている。以下はConfortiのInteger Programmingのp. 133を基にした説明。

定義: $m \times n$ 行列 $A$ の行を2つの集合 $S$ と $R$ に分割する: $S \dot{\cup} R = [m]$ 。 $S$ の行ベクトルの総和 - $R$ の行ベクトルの総和が $0, \pm 1$ のみからなるベクトルであるとき、 $S, R$ を $A$ の公平な行二彩色 (equitable row-bicoloring) と呼ぶ。

定理: 行列 $A$ が $0, \pm 1$ のみからなり、各列の非ゼロ成分は高々2個であるとする。 $A$ が公平な行二彩色可能であれば、全ユニモジュラである。

上の制約の1, 2の係数行列について考えると、1の行と2の行に分割すれば公平になっている定理の条件を満たし、全ユニモジュラである。

定理: $A$ を $m \times n$ 整数行列とする。 $A$ が全ユニモジュラならば、任意の $l, u \in \mathbb Z^n, d \in \mathbb Z^m$ について凸多面体 $Q := \{x: Ax \le d, l \le x \le u\}$ は整数多面体である、

この定理より上の制約1～3によって与えられる凸多面体は整数多面体なので、任意の目的関数について（有界なら）最適解の少なくとも一つは整数解である。

従って、ILPに関する双対、つまり元の問題のLP緩和のLP双対に整数制約を課したものを考えると、これについても強双対性が成り立つ。双対問題は以下の条件で $\sum_{i=1}^MC_ip_i + \sum_{j=1}^NA_jq_j+\sum_{i=1}^MB_i\sum_{j=1}^Nr_{i, j}$ を最小化する問題である:

$p_i + q_j + r_{i, j} \ge 1 \qquad \forall i \in [M], \forall j \in [N]$
$p_i \ge 0, q_j \ge 0, r_{i, j} \ge 0 \qquad \forall i \in [M], \forall j \in [N]$
$p_i, q_j, r_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$

双対問題を、 $M \times N$ のグリッドのいくつかの行と列を選択して覆うようなイメージで解釈した:

行と列の集合 $S \subseteq [M], T \subseteq [N]$ を任意に選ぶ。言い換えると、 $p_i=1$ とする $i$ 、 $q_j=1$ とする $j$ を選ぶ。
$i \in S$ についてコスト $C_i$ を払う。
$j \in T$ についてコスト $A_j$ を払う。
$S$ に含まれる行と $T$ に含まれる列に覆われないすべてのマス $(i, j)$ についてコスト $B_i$ を払う。

最後の「覆われない」の部分の扱いが面倒に見えるので、さらに言い換える:

最初にコスト $N\sum_{i=1}^MB_i$ を払っておく。
$S \subseteq [M], T \subseteq [N]$ を任意に選ぶ。 $k=|T|$ とする。
$i \in S$ についてコスト $C_i-(N-k)B_i$ を払う。
$j \in T$ についてコスト $A_j-\sum_{i=1}^M B_i$ を払う。

さて、 $[N]$ から $k$ 点選ぶと決めたときの最小コストについて考える。 $S \in [M], T \in [N]$ について $(N-k)\sum_{i=1}^MB_i + \sum_{i \in S}(C_i-(N-k)B_i)+\sum_{j \in T}A_j$ が総コストである。 $T$ は $A_j$ の小さいほうから $k$ 個取ればよく、 $S$ のほうは $C_i-(N-k)B_i < 0$ であるものだけ取ればよい。 $C_i-(N-k)B_i$ は $k$ が減少すると一点で正から負に切り替わる。具体的には $k \le \lfloor (NB_i-C_i)/B_i \rfloor$ で0以下になる。したがって、この閾値を超えた $i$ について $C_i$ と $B_i$ の総和を保持することにすれば $k$ ごとに ${O}(1)$ で計算できる。 $(A_i)$ のソートが必要だから全体の計算量は ${O}(N \log N + M)$ 。

LPの整数性について追記した。