2021年10月9日土曜日
エクサウィザーズプログラミングコンテスト2021 (ABC 222) G - 222
与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatrix}, v= \begin{bmatrix} 0 \\ 1\end{bmatrix}$とするとき、$a_k$は$M^k v$の第一成分に等しい。従って、問題は$v = M^kv$であるような最小の正整数$k$を求めることと言い換えられる。
この問題はbaby-step giant-stepで解ける。$B= \lceil \sqrt K \rceil$とする。$a_0, a_1, a_2, ..., a_{B-1}$について$\mod K$での値をmapのキー、添字をmapの値として保持しておく。（キーが重複する場合、そこでサイクルに入るので、それまでに$0$が見つかっていなければ打ち切ってよい。） $k= iB-j$, $j \in \{0, 1, ..., B-1\}$とする時、$v = M^kv$が成り立つためには$M^j v = M^{iH}v$が成り立つ必要がある。したがって、$i=1, 2, ..., B$について$M^{iB}v$を計算して$a_{iB}$を求め。この値が先に作ったマップに入っていれば対応する添字$j$を取り出すと$k=iB-j$が答えの候補になる。ただし、$M$は正則とは限らないので、$M^j v = M^{iB}v$は必要条件でしかない。つまり、$a_{iB-j} \mod K$が必ず$0$になるわけではない。実際に$M^{iB-j}v$を計算して確認する必要がある。
ハッシュテーブルを使った場合の期待計算量は${O}(\sqrt K)$。
2021年10月3日日曜日
ABC 221 H - Count Multiset
分割数っぽい数え上げなので分割数っぽいDPを考える。
まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて得られ、分割の中に1を含むものは$n-1$の$k-1$分割に1を付加すれば得られるのだった。漸化式で表すと
$$ P(n, k) = P(n-k, k) + P(n-1, k-1) $$このDPを、同じ数を$M$個より多くは含まないという制約（以下、単に制約と呼ぶ）に合うように修正することを考える。制約付きの分割の総数を$P'(n, k)$とする。
上の遷移の一つ目の項、つまり分割の中に1を含まないものを$n-k$の$k$分割のすべての項を$1$増加させて得る場合については、制約はそのまま守られるのでこのままでよさそう。一方、二つ目の項、つまり、分割の中に1を含むものを数えたい場合、このままだと1を$M+1$個含むものも数えてしまうことになるので、これを除きたい。
$n$の$k$分割で$1$をちょうど$M+1$個含み、他は制約を満たしているようなものの総数 = $n-(M+1)$の$k-(M+1)$分割で1を含まず、かつ制約を満たしているようなものの総数 = $n-(M+1)- (k-(M+1))$、つまり$n-k$の$k-(M+1)$分割で、制約を満たしているようなものの総数
と言い換えると、最後の量は$P'(n-k, k-(M+1))$に等しいので、漸化式は
$$ P'(n, k) = P'(n-k, k) + P'(n-1, k-1) - P'(n-k, k-(M+1)) $$となる。
スターリング数っぽい数え上げがスターリング数っぽいDPでできる、はけっこう見るけど、分割数っぽい数え上げではうまくいく問題を見た記憶がなくて、遷移を考え始めるまでに時間がかかった……が、例えばJOI 2009 予選 F - ビンゴ がそうだったのを思い出した。
2021年10月2日土曜日
第八回 アルゴリズム実技検定
満点だった。
L - K番目の絶対値
総和の絶対値が$D$以下であるような連続部分列を数える問題が解ければよさそう。累積和$S_i = A_1 + ... + A_i$上で言い換えると各$i$について$|S_i-S_j| \le D$であるような$j < i$を数えればよく、これは$S_0, S_1, ..., S_{i-1}$の中で$[S_i-D, S_i+D]$に含まれるようなものを数えることに等しい。数え上げを${O}(N \log N)$で解くと、全体で${O}(N \log N \log \sum_i |A_i|)$。
順序対を数えることにすれば尺取りでできる。確かに。
M - バランス
SoundHound Inc. Programming Contest 2018 Masters Tournament E - + Graph
O - 色分けトーナメント
- トーナメントは$2 \cdot 2^N-1$頂点の完全二分木とすると、制約$(W_i, L_i)$は$W_i$と$L_i$のLCAまで$W_i$と$L_i$が勝ち上がって$W_i$が勝つこととみなせる。
- ある選手を青に塗ると決めても赤に塗ると決めても有効な塗り方は同数ある。（どの有効な塗り方についても、すべての色を反転したものが有効な塗り方であるため。）
$\operatorname{dp}_v[x] =$頂点$v$を根とする部分木に属する左から$x$番目の選手の色を決め打った時に、部分木$v$に属する選手の塗り方で（部分木$v$に含まれる制約を満たし、かつ）$v$が勝ち上がるようなものの総数、とする。$\operatorname{dp}_v$は$v$の子を$c_1, c_2$として$\operatorname{dp}_{c_1}, \operatorname{dp}_{c_2}$から線形で作れるので、下から処理していけばよい。根に関する$\operatorname{dp}$の総和を2倍したものが答えになる。
各深さの$\operatorname{dp}$の長さの総和はちょうど$2^N$になるので、全体の計算量は${O}(N 2^N + M)$。
2021年9月12日日曜日
日本橋ハーフマラソン 2021 増刊号 A - 農場王X
評価関数を作ってビームサーチした。
前提
収穫機を買うのをどこでやめるか問題はしばらく考えずに、収穫機も資金に換算したスコアで物事を考えることにした。
評価関数
収穫機を設置/撤去する場所の持つべき望ましい性質を列挙して、それらの組み合わせで評価関数を作る。評価はマス毎に行い、価値の高いマスに収穫機を設置して価値の低いマスから収穫機を撤去する貪欲法を前提とする。また、理想的には、収穫機のあるマスの価値の総和を取ると盤面の価値になっていてほしい。
以下の評価関数に従って貪欲法をするとして、収穫機を買うのを止めるタイミングを全探索すると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
子供$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に関しても強双対性が成り立つので、上のILPの最大値は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の整数性について追記した。
2021年8月28日土曜日
日本橋ハーフマラソン 2021
A - 魔法使いXの戦い
308662点。1つのモンスターにつき、だいたい3回くらいパワーアップできる計算で、3回ならひとつずつ最適な組み合わせを貪欲に取っていけそう。素朴にやると${O}(N^4)$だが、最後は二分探索でよいので${O}(N^3 \log N)$。
まだ回数に余裕があるので、末尾に近いモンスターは4回パワーアップしたいが、これは素朴に探索すると間に合わない。$q$に選ぶモンスターから近い数値で固まっているものを省いたりして間に合う程度のノード数に減らした。
探索する順番を工夫すれば少し伸びるかもと思っていろいろ試したが伸びず。
B - マッサージチェア2021
210901点。一点のパワーを変更して干渉する点のパワーを減らすだけの山登りをした。すぐに収束してしまうが、簡単に書けそうな他の遷移もないので多点スタートなどで時間を使い切ることにした。一点のパワーを下がるほうに変更するような完全に無駄な遷移も入れてしまっているなど、いろいろ詰めが甘かった。
AtCoder Adのように、1つのノードを大きくして周りのノードを小さくする操作と、1つのノードを小さくして周りを大きくするような操作を組み合わせて再帰的に頑張るともう少しよくなるかもと思ったが、この時間では書ける気がしなかった。
マス$(i, j)$のパワーを表す変数を$p_{i,j}$とし、マス$(i, j)$に正のパワーを与えることをバイナリ変数$x_{i, j}$で表すと、素朴なMIP定式化は
maximize $E_{i, j}p_{i, j}$
subject to
- $0 \le p_{i, j} \le Nx_{i, j}$
- $p_{i_1, j_1}-N(1-x_{i_2, j_2})\le |i_1-i_2|+|j_1-j_2|-1$
という感じか。
解説を見ると全然問題の性質をとらえられていないなと思う。短時間コンテストは自明な方針を手早く実装したあと細部の詰めで同方針の人にちょっと勝つだけでそれなりの順位がとれてしまうことがありそう。