2020年5月11日月曜日
CodeChef May Challenge 2020 - Not a Real World Problem
部分点について。$N \le 15$なら全探索でよい。$H = 2$なら縦2マスの符号の状態（4通り）を持ちながら左から右にDPすればよさそう。
一般の場合について。燃やす埋めるでできたら話が早いと思ってyosupoさんの記事を眺めると、できそうだ。異なる色に塗ると罰金がかかるタイプの問題であることがポイントか。
以下、yosupoさんのフレームワークに従って考える。粒子$i$を正に塗る、負に塗るという言い方を使う。また、粒子$i$の載っているマスに書かれている数を$h_i$とする。
- $h_i \ge 0$の場合: $i$を正に塗ると$p_ih_i$円得られる。負に塗ると$p_ih_i$円失う。→ 最初から$p_ih_i$円持っているとする。$i$を負に塗ると$2p_ih_i$円失う。
- $h_i < 0$の場合: $i$を正に塗ると$p_ih_i$円失う。負に塗ると$p_ih_i$円得られる。→ 最初から$p_ih_i$円持っているとする。$i$を正に塗ると$2p_ih_i$円失う。
- 粒子$i, j$が隣り合っているとき、$i$を正（負）に、$j$を正（負）に塗ると$p_ip_j$円得られる。$i$を正（負）に、$j$を負（正）に塗ると$p_ip_j$円失う。→ 最初から$p_ip_j$円持っているとする。$i$を正（負）に、$j$を負（正）に塗ると$2p_ip_j$円失う。
これをそのままグラフにして、最大フローを流せばよい。
ほとんどの$h_{y, x}$に意味がないのはなんだったんだろう…… 誤読を疑って何度も確認してしまった。
CodeChef May Challenge 2020 - Triple Sort
3つの数のシフト操作は2つの互換でできていて、つまり偶置換なので、与えられた置換が奇置換だとどうやっても$1, 2, ..., N$に戻すことはできない。
偶置換の場合について具体的な手順を与えるために、与えられた置換を巡回置換に分解して考える。長さ$k(\ge 3)$の巡回置換$(p_1 p_2 ... p_k)$があるとき、$p_1, p_2, p_3$に操作を適用すると先頭の2つが正しい場所に収まって長さ$k-2$の巡回置換$(p_3 ... p_k)$が残る。$k=3$の場合はこの操作ですべての数が正しい場所に戻るので、結局$k$が奇数ならこの操作を最後まで繰り返せることになる。いっぽう$k$が偶数の場合は、長さ$2$の巡回置換、つまり互換が残るので、これらの処理を考える。2組の互換$(p_1 p_2), (p_3 p_4)$がある時、操作$p_1, p_2, p_3$と$p_2, p_3, p_4$を順に適用することで、4つの数がすべて正しい位置に戻る。こうして2組ずつ処理していったとき、偶置換であれば最後に端（=1つの互換）が残ることもないので、けっきょく常に$1, 2, ..., N$に戻せることになる。また、操作1回につき2つの数を正しい位置に戻せるので、操作回数の上限も満たせることがわかる。
CodeChef May Challenge 2020 - Sorting Vases
$M=0$なら巡回置換に分解して数える典型問題。また、$N=5$程度なら各順列を頂点として0-1BFSで探索すればよい。
満点について。まず、2つのロボットが与えられたときに、「少なくともいっぽうのインデックスが等しい」という関係が同値関係になっていることに注目する。このため、$N$個のインデックスはノーコストで自由に行き来できるまとまりに分割できる。
具体例を挙げて考える:
1
9 5
5 8 2 4 6 7 9 3 1
2 5
5 6
3 4
7 8
8 9
この入力をグラフで図示すると次のような感じになる:
各頂点は、コスト0で相互に行き来できるインデックスを1つにまとめたものである。また、辺$A \rightarrow B$は$A$に含まれる場所から$B$に含まれる場所にちょうど1つの数を移動させなければならないことを表す。たとえば$5$は最初インデックス$1$にあって、インデックス$5$に移動させたいので、頂点$1$から頂点$5(, 2, 6)$に辺を張っている。
こうしてグラフにしてみると、$M=0$の場合と考え方はあまり変わらないことに気づく。つまり、このグラフ上の長さ$k$の閉路は$k-1$回のスワップで解消できるので、グラフをいくつかの（辺素な）閉路に分割する問題であることがわかる。また、必要なスワップの回数は閉路の総数のみによって決まることも変わらない。
さて、閉路の総数だが、下のグラフのように分割方法によって異なる場合がある。
このグラフでは、長さ2の閉路を3つ選ぶことも長さ3の閉路を2つ選ぶこともできる。したがって、スワップの回数を減らすために、できるだけ多くの閉路に分割する方法を考えなければならない。ここまで考察を進めるとbitDPの形が見えた:
$\operatorname{dp}[S][x][y] :=$ 辺の集合$S$を使用済みで、いま作りかけている閉路（まだ閉じていない）の始点が$x$、終点が$y$である時の、今までに作った閉路の総数の最大値。
遷移が${O}(N)$なので計算量は${O}(N^32^N)$になる。オーダー的には微妙なところだが、大半の状態は無効だし、各$N$がすべて$18$ということもありえないので大丈夫だろう。割と余裕で通った。（計算量の評価がtightじゃないかも） 辺数が${O}(N)$だから隣接リストで持てば${O}(N^2 2^N)$だった。
CodeChef May Challenge 2020 - Chef and Rainbow Road
要約: $a_1, ..., a_N$から (1) 重複を許して選んで (2) どれも少なくとも1個以上選んで (3) 合わせて$N+K-1$個になるように選んで、積を取るとする。それらの総和を求めよ。
最低$1$個以上という条件を外して$K-1$個選ぶことにして、求まった値に$a_1...a_N$を掛ければよい。
多項式で考えるんだろうなという検討はつくが、ほとんど何も知らないのでmaspyさんの記事などを見て式を考える。とりあえず
$(1+a_1x+a_1^2x^2 + ...)(1+a_2x+a_2^2x^2 + ...) ... (1+a_Nx+a_N^2x^2 + ...)$
の第$K-1$項(0-based)を見ればよいことがわかる。この式は$((1-a_1x)(1-a_2x)...(1-a_Nx))^{-1}$と表せて、$(1-a_1x)(1-a_2x)...(1-a_Nx)$は分割統治してFFTすればよく、逆元もFFTで求まるらしいので、$K \le 10^5$の部分点1, 2はそれで取れる。
部分点3からはこの方針では無理そう。ところで、この間のlong challengeのまったく歯が立たなかった問題についてNyaanさんが記事を書いていたのを思い出して見に行ったら、部分分数分解というワードが出てきて使えそうと思う。
$$ \frac{1}{(1-a_1x)(1-a_2x)} = \frac{a_1}{(a_1-a_2)(1-a_1x)} + \frac{a_2}{(a_2-a_1)(1-a_2x)} $$と分解できるので、全部掛けると$1/(1-a_1 x)$の係数は$a_1^{N-1}/\prod_{j \neq 1} (a_1 - a_j)$になる。対称性により$1/(1-a_i x)$の係数は$a_i^{N-1}/\prod_{j \neq i} (a_i - a_j)$であり、これが$1+a_i x + a_i^2 x^2 + ...$に掛かっているので$x^{K-1}$の係数は$a_i^{K+N-2}/\prod_{j \neq i} (a_i - a_j)$とわかる。この値をすべての$i$について加算すれば答えが得られる。部分点3が取れた。
満点について。$a_i^{K+N-2}/\prod_{j \neq i} (a_i - a_j)$の分母の形を見るとヴァンデルモンド行列式やラグランジュ補間などが思い浮かぶので、ラグランジュ補間の解説を読んでいて$(x-a_1)...(x-a_N)$を微分したものに代入すればいいと気づく。多項式の値を$N$個の点について求める必要があるが、ググると${O}(N\log^2 N)$でできるらしい → 間に合った。
最終日に満点に気づいた。時間がなさすぎたのでbeetさんのライブラリを大急ぎで写経…… 長期コンテストでも終了直前に方針が立つと結局時間に追われることになるな。
CodeChef May Challenge 2020 - Binary Land
$1$が書いてあるマスから$1$が書いてあるマスへのパスの求め方だけ検討すればよい。
2地点間のパスの総数自体は単純なDPで求まる。DPの遷移は$N \times N$の行列で書けるので、行列積をセグメント木などに乗せれば${O}(N^3Q\log Q)$で解ける。また、クエリが単調なことを利用するとSWAGが使えて${O}(N^3Q)$になる。
満点を取るためにはもう少し頑張る必要がある。まず、遷移の行列が三重対角行列になっていることに注目すると、行列積は${O}(N^2)$になる。したがって、SWAGへのpushとpopはこの計算量でできる……が、三重対角行列同士の積が三重対角行列になるわけではないので、SWAGをfoldする時の掛け算はどうしても${O}(N^3)$になってしまう。しかし、pathクエリに対して必要なのは行列そのものではなく一点の値なので、そこだけ求めるのは${O}(N)$で可能だった。これで${O}(N^2Q)$になった。
これでもなかなかACできなかった。行列をなるべく陽に持たずに省略できる部分は省略して、定数倍高速化を徹底するとようやく通った。
CodeChef May Challenge 2020 - Buying a New String
たくさん解かれているのに部分点すらわからないので、書いたことのない文字列アルゴリズムだろうなと検討をつける。Aho-Corasickがいちばんそれっぽいので、貼るととりあえず部分点が取れた。
$|A||B|$個の文字列間で遷移の共通部分が多いことを利用できれば満点が取れそう。そして、そのためにはAho-Corasickをちゃんと理解する必要がありそう。しかし、ei1333さんのコードを見ていても理屈がよくわからないので、明らかな性質だけでなんとかすることにした:
- Aho-Corasickのマッチは部分文字列の一致をひとつずつカウントする。つまり、まとめてカウントしたりはできないので、素朴にやるとマッチする文字列の長さに対して${O}(N^2)$になる。とりあえず、トライ木を作ったらノード毎に重みの和をまとめておいたほうがよさそう。たぶんそれでオーダーも落ちる。
- Aho-Corasickの状態は今いるノードだけで決まる。つまり、ノードが同じで以降の文字列が同じならその後の遷移はすべて同じ。
以上に基づくと、次の配列を作っておけばよいはず:
$\operatorname{cumul}_A[i] := A$の区間$[0, i)$を走査した後のスコア
$\operatorname{node}_A[i] := A$の区間$[0, i)$を走査した後のノード
$\operatorname{cumul}_B[i] := B$の区間$[0, i)$を走査した後のスコアを$0$として、そこから最後まで走査して得られるスコア。
$\operatorname{node}_B[i] := B$の区間$[0, i)$を走査した後のノード
$A, B$をそれぞれ$[0, i_1,), [i_2, \operatorname{length}(B))$で切った時のスコアは$\operatorname{cumul}_A[i_1]$に$\operatorname{node}_A[i_1]$から$B[i2, \operatorname{length}(B))$を走査して得られるスコアを足したものになるが、この途中で、$B$の位置$i$を走査する際にノードが$\operatorname{node}_B[i]$と一致していることが確認できたら$\operatorname{cumul}_B[i]$を足して打ち切ってよい。単語の長さが高々26なので、$i_1$からそれだけ遷移すれば一致するはず。計算量はたぶんアルファベットの数を$\alpha$として${O}(\alpha|A||B| + \sum_i S_i)$。
そしてまだAho-Corasickを理解していない……