第五回 アルゴリズム実技検定

• アーカイブ
• 提出

リアルタイム受験した。4時間15分で全完。

J - 長い長い文字列

各操作で文字列の長さがどうなるかは先頭からシミュレーションすればわかるので、事前に求めておく。（大きな数になりえるので、適当に上限を決めて$\min$を取る。）

$i$番目の操作で長さが$L_i$になるとする。列$(L_i)$で$X$以上である最小の位置$i$を求めて、その位置にアルファベットがあればそれが答えである。数字の場合は、この操作を行う前の長さを$l$とするとき、$X$文字目は$(X-1) \% l$文字目と一致しているはずである。したがって、$X := (X-1) \% l$として同じことを繰り返せばよい。ただし、$0$文字目は$l$文字目と考える。

L - T消し

TDPCのiwiを思い出して見に行ったらそのものだった。

M - 棒の出荷

最小値を決め打って判定問題を解く。$\operatorname{dp}[x] :=$位置$x$で区切れるならtrue、不可能ならfalseというDPを考えると、適当な区間$[l(x), r(x))$について$\operatorname{dp}[x] = \operatorname{dp}[l(x)] \lor \operatorname{dp}[l(x)+1] \lor ... \lor \operatorname{dp}[r(x)-1]$という遷移になる。コンテスト中はすぐにセグ木を貼ったが、累積和上でDPするとか、（$[l[x], r[x])$は$x$について単調なので）スライドさせながらDPするとか、なんでもできそう。

O - 通知

愚直に処理すると、次数の大きい頂点が何回も更新されるときに困るが、次数の大きい頂点はそんなに多くなりえないことに注目する。閾値$D$を決めてそれより次数の大きい頂点とそうでない頂点をわけて処理してみる。以下、次数が$D$より大きい頂点をlarge node、小さい頂点をsmall nodeと呼ぶことにする。

通知クエリを処理するとき、small nodeからは周囲に愚直に通知を送り（small nodeなので送るべき頂点は多くない）、large nodeからは送らずに自身にためておいて、消化クエリが来た時に受け取る側から読みに行きたい（large nodeは多くないので毎回全部調べてもよい）。そこで、3つの配列を管理する:

• $\operatorname{unread}[x] :=$ small nodeから$x$に送られた通知で未読のものの総数
• $\operatorname{send}[x] :=$ large nodeである$x$が周囲に送った通知の総数
• $\operatorname{read}[x][y] :=$ 頂点$x$ がlarge node $y$から受け取った通知で既読のものの総数。

具体的な処理は次のようになる:

• $x$に対する通知クエリ
  • $x$がsmall nodeなら、$x$に接続しているすべての頂点$y$について、$\operatorname{unread}[y] \mathrm{+}{=} 1$する。
  • $x$がlarge nodeなら、$\operatorname{send}[x] \mathrm{+}{=} 1$する。
• $x$に対する消化クエリ
  • small nodeからの通知の総数を得る: $\operatorname{unread}[x]$を読んだあと、$0$にリセットする
  • large nodeからの通知の総数を得る: $x$に接続しているすべてのlarge node $y$について、$\operatorname{send}[y]$から既読の通知の総数$\operatorname{read}[x][y]$を引いたものの総和を取る。$\operatorname{read}[x][y] := \operatorname{send}[y]$として、既読を更新しておくこと。

計算量について考える。辺が1つ増えると全体の次数が2増えるので、次数の総和は$2M$である。したがって、次数$B$以上の頂点、つまりlarge nodeは、高々$2M/B$個しかない。クエリあたりの計算量は以下のように評価できる:

• $v$に対する通知クエリ
  • $v$がsmall nodeなら$O(D)$
  • $v$がlarge nodeなら$O(1)$
• $v$に対する消化クエリ
  • small nodeからの通知の合計を得るのは${O}(1)$
  • large nodeからの通知の合計を得るのは${O}(M/D)$

結局、全体の計算量は${O}(N+M+Q(D+M/D))$と書けて、$D= \sqrt M$なら${O}(N+M+Q\sqrt M$)。

解説の実装は$\operatorname{read}[x][y]$を頂点$x$がlarge nodeから今までに受け取った通知の数の合計として一次元配列にまとめていた。確かにそれでよかった。

CodeChef - Counting Strings

• 問題
• FFT
• 累積和

問題: 与えられた文字列$s$について、左から比較しても右から比較しても辞書順で大きい文字列$t$を数える。

$t$の構成を考えると、2つの位置$i, j (i \le j)$を境界にして、以下のように左から順に5つの部分に分解できる。（2番目と4番目は1文字）

• $s$と完全一致
• $s[i] < t[i]$
• 文字自由
• $s[j] < t[j]$
• $s$と完全一致

$N := |s|$とし、0-basedで考える。$f(i) :=$ 文字$s[i]$より大きい文字の数（$s[i] = \operatorname{a}$なら$f(i)=25$）とすると、$i, j$が異なる場合の数え上げは$\sum_{i < j} f(i)f(j)26^{j-i-1}$である。あとは$i, j$が一致する場合、つまり$s$と$t$がちょうど1字異なる場合を別に数えて$f(0)+...+f(N-1)$を足す。

上の式を見ると、畳み込める形になっている。$g(x) = f(N-x-1)$として一方の添え字を逆順にすると、$26^{N-2}\sum_{i+j \le N-2} f(i)g(j) (1/26)^{i+j}$と変形できて、$f$と$g$をFFTで畳み込んだ後で$1/26$を掛けながら加算すればよい。$\bmod$は$10^9+7$だが、登場する数が十分に小さい（高々$25^2 \cdot 10^5$）ので$998244353$でやっても問題ない。

---

よく見ると、変形して累積和を取るだけだった。

$$\sum_{i < j} f(i)f(j)26^{j-i-1} = \frac{1}{26}\sum_{i=0}^{N-1} \biggl( \frac {f(i)}{26^i} \sum_{j = i+1}^{N-1}{f(j)}26^j \biggr )$$

形を見て畳み込みできそうと思えるのは悪くないとしても、変数を分離できないかまず考えるほうがさすがによい気がする。

CodeChef - Two Closest

• 問題
• AC

問題: 無向グラフ$G=(V, E)$と$V$の部分集合$S$ (special node)が与えられる。$S$上の任意の2点間の距離で最短のものを求めよ。

方針: すべてのspecial nodeから各点への最短距離を調べるために$K$回ダイクストラする。この際、距離のテーブルは毎回使いまわしてよくて、枝刈りができる。また、special nodeを調べる順番をシャッフルすれば期待計算量が保証できる。

正当性について。今、special node $A_1, ..., A_{i-1}$について二頂点間の最短距離の最小値が求まっているとし、距離のテーブル$d$が$d[v] := v$と$A_1, ..., A_{i-1}$との最短距離の最小値、という状態になっているとする。ここからさらにspecial node $A_i$を始点にダイクストラするとする。この際、頂点$u$から$v$を更新しようとした時に$d[u] + w(u, v) \ge d[v]$であれば、$v$は無視してよい。なぜなら$A_i$から任意の頂点$x$に到達する際の最短経路が$v$を通るとしても、それ以下の距離で$A_1, ..., A_{i-1}$のいずれかから$x$に到達できることになるからだ。

計算量について。$K$回ダイクストラをしている間に頂点$v$がキューからポップされる回数の期待値を考える。$v$がキューからポップされるのは、今調べているspecial nodeと$v$の最短距離が以前調べたすべてのspecial nodeと$v$の最短距離より小さい場合である。したがって、この期待値は$K$個のspecial nodeと$v$との最短距離を$d_1, ..., d_K$とした時、$(d_i)$をシャッフルした列のLDSの長さの期待値に等しく、${O}(\sqrt K)$らしい^[1]。したがって、ポップに関する期待計算量は${O}(\sqrt KN \log N)$となる。また、ポップした頂点の隣接頂点を調べてdecrease keyする操作の期待計算量は、二分ヒープなら${O}(\sqrt KM \log N)$となる。 したがって、全体の期待計算量は${O}(\sqrt K (M+N)\log N)$ということになる。

waterfallsさんの別の乱択の方針も面白かった。special nodeをランダムに2分割して、一方を始点としたダイクストラをすると、最短距離を与える二頂点が異なるグループに属している時に正しい答えが出る。そうなる確率は1/2なので、何回もやって最小値を取ればよい。このテクニックは無向グラフの最短閉路アルゴリズムで見たことがある: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf

---

1. この評価については https://www.math.ucdavis.edu/~romik/book/ のp.9に簡潔な証明が載っている。ランダム順列のLISの長さの期待値に関する研究はJ. M. Hammersley, A few seedlings of researchが初出らしい。（後者は読んでいない） ↩︎

JOI2019 本選 C - たのしいたのしいたのしい家庭菜園

• 問題
• AC

左から列を作っていくとして、次にR, G, Yを隣に置くためにはまだ使っていないものの中で一番近いものを持ってくればよい。今までにR, G, Yをそれぞれ何個使ったか保持していれば一番近いR, G, Yがどこにあるかは決まるので、$\operatorname{dp}[x][y][z][c] :=$Rを$x$個、Gを$y$個、Yを$z$個使っていて直前に置いた色が$c$である場合の最小コスト、というDPが${O}(N^3)$でできるはず……だが、それ以降のほうが難しかった。

例えば$\operatorname{dp}[x][y][z][c]$から次にGを隣に持ってきて$\operatorname{dp}[x][y+1][z][G]$に遷移するとき、何回スワップが必要か数える必要があるのだが、どうやって数えるかでしばらく悩んでいた。結論から言えば

1. $\max(0, 次のGの位置以前にあるRの総数 - x)$
2. $\max(0, 次のGの位置以前にあるYの総数-z)$

の和が間にあるG, Yの総数に等しく、これが必要なスワップの総数に等しい。

HTTF2021 決勝 - マイニング

• 問題
• 提出

入力の作り方を見る限り、鉱脈はある程度まとまっているので、鉱脈を連結成分として表現して、連結成分とその間のパスを効率よく取っていくとよさそう……だが言うは易しという感じの方針なので具体的にどう実装するかで悩み続けた。

• 鉱脈を構成する点を判別していくつかの連結成分にわける
  • 定数$\alpha$を決めて、$p_{ij}-C/\alpha \ge 0$である点$(i, j)$を鉱脈を構成する点と考える。鉱脈を構成する二点で隣接しているものをUnionFindでつなぐ。コスト$C/2$で取れる点がある程度あることを考慮に入れようとして$\alpha = 1.5$くらいで始めたが、最終的には$1.05$になった。後から考えると、これは$1$で問題なかったと思う。
  • 連結成分はだいたい100個前後になる。
• 2つの連結成分間の距離を求めておく
  • ある連結成分を始点とした場合の、グリッド上の各点への最短距離はダイクストラで求まるので、全連結成分間の距離をあらかじめ求めておく。連結成分は100個程度なので、100回程度ダイクストラすればよい。
  • 「グリッドの外周」もひとつの連結成分とみなして最短距離を求めておく。
  • ダイクストラをする際、鉱脈を構成する点は通れないことにしておく。こうしないと鉱脈を突っ切って別に鉱脈に行ったほうが得という場合にコストの推定を間違えてしまうし、そもそも負辺を含んでいることになるのでダイクストラできない。通れないことにしたせいで連結成分$A$から$C$への移動が連結成分$B$に阻まれても別に問題ない。（次のパートで、必要なら$A$から$B$、$B$から$C$みたいな経路ができるはずなので。）
• MST+ 焼きなまし
  • 使う連結成分が決まっているとき、推定スコアは、連結成分中の$p_{ij} - C/\alpha$の総和から連結成分を頂点とする無向グラフ上のMSTの総コストを引いたものと考えられる。
  • 連結成分を使う/使わないで焼きなます。毎回クラスカルした。最初は単純に山登りしたが、焼きなましで多少スコアが上がった。
• 基本の採掘経路を求める
  • 使う連結成分が決まったので、「グリッドの外周」を表す連結成分を根としてMST上をDFSしながら採掘していく。隣接する連結成分へ移動するための具体的な経路は、上と同じようにダイクストラして復元すれば得られる。
    • 頂点を取る順番もスコアに関係しそうだと思ったけれど、つめられず。
• 貪欲で仕上げ
  • 既に採掘した点の隣接点でスコアが上がるものがあれば取る。
  • 既に採掘した点の隣接点とさらにその隣接点の2点を取ってスコアが上がるなら取る。
  • 以下、同様の貪欲を深さ4までやる。

267万点だった。

---

太字の部分に気づいて方針が決まるのに4時間、最初の提出までに6時間半かけてしまった。2～4時間のコンテストだと何もできずに終わってそう。

CS Academy Round #66 - Flipping Matrix

• 問題
• AC

操作を逆順に見る。単位行列の行や列を入れ換えていくと、次のことがわかる:

• 行と列の間に$1$による一対一対応があるという性質は交換で保たれる。（→ 置換行列）
• 任意の二行の交換はある二列の交換と同一操作であり、任意の二列の交換はある二行の交換と同一操作である。

逆に、初期配置から$1$を共通に含む行と列を1対1に対応させることができれば、この対応を1つの置換と考えることができ、互換を繰り返すことによって単位置換（＝単位行列）に戻せる。また、あらゆる置換は高々$N-1$個の互換の積で表せるので、$N$回以下という制限は問題にならない。結局、やることは次のようにまとまる:

1. $N \times N$の二部グラフ$G$をつくり、$A_{ij}=1$なら行に対応する頂点$i$から列に対応する頂点$j$に辺を張る。
2. $G$の最大二部マッチング$M$を求める。$M$が完全マッチングでなければ実行不能である。
3. $M$を一つの置換とみなして巡回置換に分解し、さらに互換に分解する。互換に従って行の交換を行う。

JOI2009 春合宿 - stamps

• 問題
• AC

とりあえず最短作業時間は単純なDPで求まりそう。$\operatorname{dp}[x][y] := S$を左から$x$文字作り済みで、次に使える文字がOである（$y=0$）あるいはIである（$y=1$）場合の最小操作数、として$\operatorname{dp}[N][0]$が求める値である。使える文字と次に作りたい文字が一致していればコスト0で次に遷移できるし、一致していなければ文字を変更または挿入してコスト1で遷移できる。

また、元のIOI文字列をできるだけ短くするためには挿入の回数を最大化すればよくて、これも同様のDPができるが、最短作業時間のほうが優先なので上のDPと同時にやる必要がある。

形式的には、1つのDPと捉えて、DP配列に入っている値を$(最短作業時間, 挿入回数)$として辞書式の大小関係を与えると考えると、わかりやすいかもしれない。

CS Academy Round #76 - Pyramids

• 問題
• AC

ある種の区分線形関数に囲まれた領域の格子点を数える問題。区分線形関数を構成する線分の総数が${\mathcal O}(N)$なので、全部列挙して線分毎に下にある格子点を数えればよさそう。

まずは、与えられた点で折れ線を構成するものだけを左から列挙したい。点を$c$の昇順でソートしてスタックを持ちながら走査する。ある点$(r, c)$による山を処理するとき、スタックの先頭に入っている点（=ひとつ前の山の頂上）による山との関係には次の3通りがある:

1. 前の山に完全に含まれる
2. 前の山を完全に含む
3. 前の山と一部重なるか、遠く離れていて重ならない

今見ている点を$(r, c)$、スタックの先頭に入っている点を$(r', c')$として、

• $c+r \le c' + r'$なら1、つまり前の山に含まれるので無視
• $c-r \le c'-r'$なら2、つまり前の山を含むのでスタックをポップしてさらに前の点を見る
• それ以外は3なので新しい点をスタックにプッシュする

こうするとスタック（の反転）には山の頂点として有効な点だけが左から並ぶので、その間にできる谷に関する格子点をそれぞれ数えればよい。

数え上げパートについて。山の頂点が左から$(r_1, c_1), ..., (r_k, c_k)$と並んでいるとする。頂点$(r_i, c_i)$と$(r_{i+1}, c_{i+1})$の間にできる谷は直線$y=-(x-c_i)+r_i$と直線$y=x-c_{i+1}+r_{i+1}$の交点であり、その$y$座標は$(r_i+r_{i+1}+c_i-c_{i+1})/2$と表せる。そこで、$H= \max(0, \lceil (r_i+r_{i+1}+c_i-c_{i+1})/2 \rceil)$としてまずは下部の長方形の格子点を$H(c_{i+1}-c_i+1)$と数え、さらに上部の三角形の格子点を$(r_i-H)^2 + (r_{i+1}-H)^2$と数える。また、左端の頂点$(r_1, c_1)$の山の左側半分にある格子点$r_1^2$個と右端の頂点$(r_k, c_k)$の山の右側半分にある格子点$r_k^2$個は別に加算する。このとき、各頂点の下にある格子点をちょうど2回ずつ数えているので、$\sum_i r_i$を引けば正しい数になる。

CS Academy Round #79 - Groups

• 問題

計算量の説明がどこにも書かれていなくて困った。以下は自分の理解。

$i$番目のクエリで与えられる$P_i$人の人間について、代表者の人数を$x_i$、代表者以外の人数を$y_i$とする。$x_i$個のグループそれぞれについて、走査して離脱しないメンバーが見つかったら打ち切るのが想定解らしい。$D=10^5$として1つのクエリで調べるノード数は最大で$\min(x_iy_i, D)$なので、計算量は$\sum_{i=1}^Q \min(x_iy_i, D)$と書ける。これを評価したい。

まず、$\sum_{i=1}^Q P_i = \sum_{i=1}^Q (x_i + y_i) \le D$という制約がある。$x_i + y_i$が一定のとき$x_iy_i$は$x_i = y_i$で最大値を取るので、$\sum_{i=1}^Q x_i \le D/2$という条件下で$\sum_{i=1}^Q \min(x_i^2, D)$を評価する問題ということにいなる。面倒なので、代わりに$\sum_{i=1}^Q x_i \le D$としておく。

$x_i + x_j$が一定のとき、$x_i^2 + x_j^2$は$x_j=0$で最大になる^[1]ので、$\sum_{i=1}^Q x_i^2$を大きくするには値をできるだけ偏らせるのが最善である。ただし、1つの変数を$\sqrt D$より大きくしても意味がないので、最大値を取る配分の一つは$(x_1, x_2, ..., x_Q) = (\sqrt D, ..., \sqrt D, 0, ..., 0)$という形になる。$\sum_{i=1}^Q x_i \le D$より、最大で$\sqrt D$個程度の$x_i$を$\sqrt D$にできるから、このとき$\sum_{i=1}^Q \min(x_i^2, D) = D\sqrt D$と見積もれる。

---

1. 平面上で、原点を中心とするマンハッタン距離に関する円と、ユークリッド距離に関する円を思い浮かべればよい。 ↩︎

ARC 108 F - Paint Tree

• 問題

主張: 与えられた木$T$の直径を$D$とし、長さ$D$のあるパスの端点$V_b, V_w$が黒、白に塗られているとする。また、黒に塗られた頂点同士の最大距離を$X$とし、距離$X$の黒に塗られた2頂点$A, B$が与えられているとする。このとき、パス$V_b - A$または$V_b-B$の少なくとも一方は長さ$X$である。

証明: パス$V_b - A, V_b-B$の両方の長さが$X$未満と仮定する。3頂点$V_b, A, B$の間にできる3つのパスに共通して含まれるただ1つの頂点を$c$とすると^[1]、$d(c, A) + d(c, B) = X$だから、$d(c, A), d(c, B)$の少なくともいっぽうは$X/2$以上である。$d(c, A) \ge X/2$としてよい。また、パス$V_b - A$が長さ$X$未満という仮定より

$$d(V_b, c) + d(c, A) < X$$

が成り立つから、$d(V_b, c) < X/2$が導ける。整理すると

$$\begin{aligned} D & \le d(V_w, c) + d(V_b, c) \\ & < d(V_w, c) + \frac{X}{2} \\ & \le d(V_w, c) + d(c, A) \\ & = d(V_w, A) \end{aligned}$$

$d(V_w, A) > D$が導かれたので、直径より長いパスが見つかったことになり、矛盾する。$\square$

---

1. https://en.wikipedia.org/wiki/Tree_(graph_theory)#Properties より、For any three vertices in a tree, the three paths between them have exactly one vertex in common (this vertex is called the median of these three vertices). というやつ。 ↩︎

CODE FESTIVAL 2014 - 宝探し 2

• 問題
• AC

変更なしかつ一次元で考えると種類数の有名問題になるが、お宝が高々100種類しかないので累積和の列を100個用意するだけでよい。また、隣接要素を入れ替える操作が累積和上でどうなっているか考えると、右から左に移動するお宝に関する累積和列の1個所が+1され、左から右に移動するお宝に関する累積和列の同じ個所が-1されるだけなので、特別なデータ構造なしで処理できる。

二次元の場合も、二次元累積和を取って同じことをやればよい。上下の入れ替えでは、下から上に移動するお宝に関する累積和配列の1個所からその行の右方にある数がすべて+1され、上から下に移動するお宝に関する累積和列の同じ個所からその行の右方にある数がすべて-1される。左右の入れ替えも同様に処理できる。計算量は${O}(nmk + q\max(n, m))$。

CS Academy Round #83 - Firestarter

• 問題
• AC

着火クエリ$(T_i, A_i, B_i, X_i)$に対して新しい頂点$V_i$を導入し、辺$\{A_i, B_i\}$を分割して長さ$X_i$の辺$\{A_i, V_i\}$と長さ$L-X_i$の辺$\{V_i, B_i\}$を張る。ひとつの辺上に複数の着火が起こる場合には、3つ以上に分割する。こうしてできたグラフ上で、各頂点に初めて火が到達する時間を求める。具体的には、$V_i$の距離を$d[V_i] := T_i$とセットして多点スタートのダイクストラをする。（形式的には、大頂点$S$を導入して各$V_i$と$S$の間に長さ$T_i$の辺があると考えるのがよさそう。）

こうすると、頂点$v$に初めて火が到達する時間が$d[v]$に入ることになる。ただ、欲しいのはすべての辺が燃えきる時間なので、$\max d[v]$は答えにならない。長さ$l$の辺$\{u, v\}$が燃えきる時刻を$t$とすると$(t-d[u])+(t-d[v]) = l$なので、$t = (l + d[u]+d[v])/2$と求まる。この最大値を答えとすればよい。

---

時刻を決め打って二分探索をやってしまって、さすがにTLEだった。

第四回 アルゴリズム実技検定

• 問題
• 提出

リアルタイム受験した。3時間55分で全完。

L - マンションの改築

差分$d_i := a_i - a_{i+1}$に注目すると、$d_i = 0$になる$i$を数えればよいことがわかる。クエリによる$(d_i)$の変動は以下のようになる:

• タイプ1のクエリ: 奇数の$i$について$d_i \mathrel{{+}{=}} v$、偶数の$i$について$d_i \mathrel{{-}{=}} v$。
• タイプ2のクエリ: 奇数の$i$について$d_i \mathrel{{-}{=}} v$、偶数の$i$について$d_i \mathrel{{+}{=}} v$。
• タイプ3のクエリ: $d_{u-1} \mathrel{{-}{=}}v$、$d_{u} \mathrel{{+}{=}} v$。

$d_i = 0$になる$i$を数えたいので、さらに$\operatorname{table}[x] := d_i=x$である$i$の総数、という情報をハッシュテーブルなどで保持しておくとよさそうだ。しかし、$(d_i)$や$\operatorname{table}$をクエリ毎に愚直に操作すると、タイプ1と2については間に合わない。

偶奇にわければタイプ1, 2はまとめて処理できそうなので、$\operatorname{offset}_奇, \operatorname{offset}_偶$という量を保持することにする:

• タイプ1のクエリ: $\operatorname{offset}_奇 \mathrel{{+}{=}} v$、$\operatorname{offset}_偶 \mathrel{{-}{=}} v$。
• タイプ2のクエリ: $\operatorname{offset}_奇 \mathrel{{-}{=}} v$、$\operatorname{offset}_偶 \mathrel{{+}{=}} v$。

$d_i$の真の値は、これらのオフセットを足したものということになる。さらに、$\operatorname{table}_奇[x] := d_i=x$であるような奇数$i$の総数とし、$\operatorname{table}_偶$も同様に定義して、タイプ3のクエリでこれらを更新する:

• タイプ3のクエリ: $d_{u-1} \mathrel{{-}{=}}v$、$d_{u} \mathrel{{+}{=}} v$。さらに$d_{u-1}$と$d_u$の変更に応じて、$\operatorname{table}_奇, \operatorname{table}_偶$を適切に更新する。

こうすると、各クエリを処理したあとの答えは$\operatorname{table}_偶[- \operatorname{offset}_偶] + \operatorname{table}_奇[- \operatorname{offset}_奇]$で求まることになる。

M - 筆塗り

与えられたグラフ$T$を根付き木とみなす。$i$回目でパス$u-v$を塗るとしたとき、$u$から塗りながら木を上昇していって$\operatorname{LCA}(u, v)$の深さ以下になったらそこで塗りは無効になると考えることができて、$v$についても同様である。そこで、事前処理で$\operatorname{q}[v] :=$一方の端が$v$であるすべてのクエリ番号（のリストや可変長配列）、という情報を用意しておくことにする。

そして、$T$を葉からボトムアップに処理する。頂点$v$を処理する際に「子から$v$に上ってきた時点でまだ有効かもしれないクエリ番号」を番号の降順で優先度付きキューに保持する。具体的に手順を書くと、

1. $v$の子$c_1, c_2, ..., c_k$の保持する優先度付きキュー$Q_{c_1}, ..., Q_{c_k}$と$\operatorname{q}[v]$をすべてマージしたキュー$Q_v$を作る。
2. $Q_v$からクエリ番号$i$を取り出し、$i$に対応する$\operatorname{LCA}(u_i, v_i)$の深さを調べ、$v$の深さがそれ以下であれば$i$を捨てることを繰り返す。$v$のほうが深ければストップし、$v$とその親をつなぐ辺がクエリ$i$で塗られていることを確定する。（$Q_v$が空になるまで見つからなければこの辺は一度も塗られていないことになる）

ダブリングでLCAを求めてマージ可能なヒープを使った場合、計算量は${O}((N+Q) (\log N + \log Q))$となる。コンテスト中にはpairing heapを使ったが、二分ヒープでもマージテクをすれば$\log Q$が掛かるだけなので十分間に合う。

操作を逆から見ると簡単になるのは確かに……

O - 宝箱

一読して、セグメント木上でin-placeにDPする方法がありそうに見えたので、うまい更新方法を探した。

以下、0-basedで考えて、鍵屋$i$に対応する区間を半開区間$[l_i, r_i)$で持つことにする。とりあえず愚直なDPを考えると、$\operatorname{dp}[x] :=$ 右端（つまり$r_i$）が$x$以下の鍵屋のみを使って得られる最大利益、とするのがよさそう。右端が$x$と一致する鍵屋$i$がただひとつ存在するケースを例にとると、遷移は

$$\begin{aligned} \operatorname{dp}[x] \leftarrow \max( & \operatorname{dp}[x-1], \\ & \operatorname{dp}[l_i] + a_{l_i} + a_{l_i + 1} + ... + a_{r_i -1}, \\ & \operatorname{dp}[l_i+1] + a_{l_i+1} + ... + a_{r_i -1}, \\ & ... \\ & \operatorname{dp}[r_i - 1] + a_{r_i - 1}) \\ \end{aligned}$$

となる。遷移を見ると、$a_i$を加算している部分が前もって$\operatorname{dp}$に足されていれば、区間$\max$でまとめて処理できそうだ。実際、$\operatorname{dp}[x]$を処理したあとの遷移の式には、$\operatorname{dp}[0], \operatorname{dp}[1], ..., \operatorname{dp}[x]$は常に$a_x$が加算された形しか出てこないので、$\operatorname{dp}$を遅延セグメント木などで持っておいて、必要なタイミングで区間加算すればよい。疑似コードで書くと以下のようになる:

res = 0
for r from 1 to N:
  dp[r] = max(dp[r], dp[r-1])
  dp[0], ..., dp[r-1] += a[r-1] # 区間加算
  for l, c in 右端がrの鍵屋:
    dp[r] = max(dp[r], max(dp[l], ..., dp[r-1]) - c)
  res = max(res, dp[r])

上の$\operatorname{dp}$の定義は$\operatorname{dp}[x]$を処理した瞬間にしか成り立っていないことに注意。

dwangoプログラミングコンテスト D - タクシー

• 問題
• AC

最小費用流なので、とりあえずグラフを二周くらいしながら需要と供給を解消していって、循環流になおす。あとは負閉路を解消すれば最適になるが、このグラフ上の負閉路は環状線を一周するものしかありえないので、ここにできるだけ流せばよい。具体的には、残余グラフ上の負辺を集めて$(上限流量、辺の重み)$を上限流量の昇順でソートして、先頭から順に（一周のコストが負である限り）上限流量いっぱいに流すことを繰り返した。

ARC 093 E - Bichrome Spanning Tree

• 問題
• AC

$X$がMSTの重みの総和より小さい場合は実現不可能である。

$X$がMSTの重みの総和に等しい場合、MSTを作れるような塗り方を数えればよい……が、そもそも、だいたいの塗り方においてMSTが作れるように見える。というのも、MSTに使える辺が全部白または全部黒になっているような塗り方を除けばMSTができるからだ。つまり、MSTに使われうる辺が$K$本あるとき、$K$本全部を一色で塗る$2\cdot 2^{M-K}$通りの塗り方以外はMSTを作れる。あとは$K$が求まればよい。これは最小全域木$T$を作った後、$M$本の辺$e = (u, v)$について最適性条件を満たせるか判定すれば数えられる。具体的には、$e$の重みが（$T$上の）パス$u - v$上の重みの$\max$以下であれば$e$はMSTに使える^[1]。変更がないので、$\max$クエリはダブリング等で処理できる。（制約を$N=10^5$と勘違いしていた。愚直でよい。）

$X$がMSTの重みの総和より大きい場合、MSTに使われうる辺は全部白または全部黒に塗られていなければならないので、とりあえず白に塗られているとする。この時、黒に塗られていてMSTに使えない辺が全域木に少なくとも1本含まれていなければならないが、その1本以外は白い辺も自由に選べる。したがって、MSTに対して辺を挿入してそれによってできたサイクルから別の最大辺を削除して全域木を作った時に、重みの総和が$X$になるものを考えればよい。これにはやはり木上の$\max$クエリで答えられる。「MSTの辺と交換した時の重みの総和」が$X$になる辺を$p$本、$X$より大きくなる辺を$q$本としたとき、$p$本から少なくとも一つを黒い辺にする必要があって、$q$本は好きにぬってよいので、塗り方は$(2^p-1)2^q$通り。白の分と黒の分を足すと$2\cdot(2^p-1)2^q$通りとなる。${O}((M+N)\log N)$。

---

厳密な証明がよくわからなかった。

---

1. path optimality condition ↩︎

ABC 180 F - Unbranched

• 問題
• AC

「最大サイズがちょうど$L$」の代わりに、$f(n, m, l) :=$連結成分のサイズが$l$を超えない$n$頂点$m$辺のグラフの数、を数えることにして、$f(N, M, L)-f(N, M, L-1)$を答えとすればよい。

次数2以下の連結成分はパスかサイクルしかないので、この2つを作りながら数えていくDPができそうだが、頂点の順番をどうするかが問題になる。順番を固定した上で最後に定数を掛けるのはうまくいかなそうだし、固定せずに挿入していくDPもサイズの上限に関する制約を扱うのが困難に見える。

こういう時の典型テクニックの一つとして、「選ぶ頂点の一つは、残っているものの中でもっとも小さい番号とする」というルールを追加してグループ（この場合は連結成分）を作っていくというものがある。この場合はこれがうまくいきそうだ。

$\operatorname{dp}[x][y] :=$頂点を$x$個、辺を$y$個使ってできる（条件を満たす）グラフの総数

とする。残った$N-x$個の頂点からサイズ$s$のパスグラフを作る時、連結成分のうちの1つの頂点は残った頂点の中でもっとも番号の小さいものと決めているので、残りは$N-x-1$個から$s-1$個を選ぶことになる。ラベル付きパスグラフの総数は$s!/2$（ただし$s=1$の場合は例外）なので、

$$\operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{s!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y]$$

と遷移できる。サイクルを作る場合も同様で、ラベル付きサイクルグラフの総数は$(s-1)!/2$（ただし$s\le 2$の場合は例外）なので、

$$\operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{(s-1)!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y]$$

と遷移する。ただし、自己ループである$s=1$は許されないことに注意。

CodeChef October Challenge 2020 - Compress all Subsegments

• 問題
• AC

区間$I$に関する$f$の値は、$(A_i)_{i \in I}$中のhighest set bitの位置を$k$として、$k$が立っている数が$(A_i)_{i \in I}$に何個含まれるかでだいたい決まる:

1. $k$が立っている数が1個でそれ以外が0個の場合、その数自身になる
2. $k$が立っている数が奇数個の場合、上の場合を除いて$2^k$になる
3. $k$が立っている数が2個でそれ以外が0個の場合、不定
4. $k$が立っている数が2個でそれ以外が1個の場合、不定
5. $k$が立っている数が2個でそれ以外が2個以上の場合、0にできる
6. $k$が立っている数が4個でそれ以外が$0$個の場合、不定
7. $k$が立っている数が4個でそれ以外が$1$個以上の場合、0にできる
8. $k$が立っている数が6個以上の偶数の場合、それ以外が何個でも0にできる

まずは、$k$が立っている数が偶数個の時に常は$f$の値が0になり、$k$が立っている数が奇数個の時は常に$2^k$になるとして、偶奇のみに注目して計算する。そして、後から3, 4, 6のパターンを別に数えて補正する。

前半パートは、$i = 1, 2, ..., N$についてそれぞれ区間$[1, i], [2, i], ..., [i, i]$に関する結果の和を求めるとよい。この際、

• $\operatorname{odd}[x] :=$ highest set bitが$x$で、$x$が立っている数を奇数個含むような区間の数
• $\operatorname{even}[x] :=$ highest set bitが$x$で、$x$が立っている数を偶数個含むような区間の数

を保持しながら走査するとまとめて計算できる。${O}(N\log \max A_i)$。

CodeChef September Challenge 2020 - Chefina and Swap

• 問題
• AC

0-basedで考える。列$(S_i)$を$[0, m), [m, N)$に分けた時に、左右の和を等しくするようなスワップが何個あるか数える。まず、右の和のほうが大きいことが有効なスワップが存在する必要条件である。右の和が左の和より$D(m)$だけ大きいとする。このとき、$D(m)$が偶数なら左の区間の$S_i$と右の区間の$S_{i+D(m)/2}$を交換すると和が等しくなる。添え字$i$が有効である条件は$0\le i < m, m \le i+ D(m)/2 < N$で、これは$\max(0, m-D(m)/2) \le i < \min(m, N-D(m)/2)$とまとまる。この区間の長さが有効なスワップの数に等しいので、すべての$m$について足せばよい。ただし$D(m)=0$の場合は区間をまたいで数を移動する必要がないので特別扱いして、左の区間内と右の区間内のスワップの総数を数える。

さて、$0\le D(m) < 2N$が必要なことを考えると、有効な$m$は多くないはずだ。$m$が増加するとき、$D(m)$が正から負に変わる地点を考えると、この地点は全体の半分よりは右にあるはずだから、その付近では$m$が$1$動くごとにおおむね$2 \cdot N/2 = N$程度は$D(m)$が変化することになる。したがって、高々3つ程度の$m$について数えれば十分という見積もりができる。実装の際は$D(m) \ge 0$であるような最大の$m$を二分探索などで求めておいて、そこから下っていけばよい。

CodeChef September Challenge 2020 - Find XOR

• 問題
• AC

仮に$K=0$を尋ねることが可能だとすると、$K=0$による総和と$K=2^e$による総和の差は$(A_i)$の中で第$e$ビットが$1$であるものの総数-第$e$ビットが$0$であるものの総数に等しい。これを利用すると各桁の立っているビットの数がわかるので、偶数ならXORを0、奇数なら1とすればよい。

実際には$K\ge1$という制約があるが、代わりに全ビットを反転したもの（=$2^{20}-1$とXORを取ったもの）を$K$とすれば同じことができる。

また、素朴にやると$K=0, 2^0, 2^1, ..., 2^{19}$を全部尋ねる必要があってクエリの回数が21回になってしまう。$K=2^0, ..., 2^{18}$を調べて$K=0$の場合の生の総和と比較することで、$K=2^{19}$は省略できて20回になる。

---

$N \le 10^3 < 2^{10}$だから、11ビットくらいで区切れば2つの質問を1つのクエリでできそうと思ったが、分離がかなり複雑になりそうなので方針を変えた。

CodeChef September Challenge 2020 - Rotate the Polyline

• 問題
• AC

$v_i=P_iP_{i+1}$とした時、原点を通る直線$l$によってできた2つの（境界を含まない）半平面のそれぞれに連続した添え字のベクトルが並んでいれば、$l$に直交するベクトルが答えということになる。ただし、答えとなるベクトルは十分に原点に近い格子点を通る必要がある。

整数性の条件をいったん忘れると、直線$l$を表すベクトルの候補$u$は各$v_i$から偏角を左右に微小にずらした$2N$通りが考えられる。そこで偏角順の尺取り法をして、それぞれの$u$から偏角が$180 \degree$以内におさまるすべての$v_i$の添え字を保持することにする。添え字がすべて連続している瞬間があれば$u$を$90 \degree$回転したものを答えにすればよい。管理と判定はBITでできる。以下、実装のポイント:

• 尺取り法で区間を伸ばす場合の処理: ベクトルの候補$u$と$v_i$のクロス積がマイナスになるまで伸ばしていけばよい。^[1]
• 尺取り法で区間を縮める場合の処理: $u$と$v_i$のクロス積がプラスになるまで縮めればよい。
• $u$と同一か180度回転した偏角が$(v_i)$に含まれる場合、$u$（を$90\degree$回転したもの）は答えにできない。

さて、$2N$本の直線を用意する上で、整数性の条件を考慮しなくてはならない。単純化のために正数に限定して考える。ベクトル$(x, y)$から反時計回りに微小に偏角を進めたベクトルを得ることは、$y/x < 1$であればファレイ数列$F_{2\cdot 10^9}$において$y/x$の直後にある分数を得ることと同じである。$y/x \ge 1$の場合も、逆数を取って直前の分数を得ると考えればよい。やり方を知らないのでググったらstackexchangeの質問が見つかった。ファレイ数列の隣接項$p/q, c/d$は$cq-dp=1$を満たすので、$c, d$は互除法で求まるようだ。

---

1. クロス積がマイナスになるベクトルが存在しなかった場合はこれだとうまく処理できないように見える。こういうことが起こるのは、偏角ソートされた$(v_i)$の隣接項同士が$180\degree$より開いている場合だが、問題設定より全ベクトルを足すと$0$に戻るのでこの範囲に1つもベクトルがないということはありえない。 ↩︎

CodeChef September Challenge 2020 - Divide Candies

• 問題
• AC

べき乗和は$K$の値に関わらず奇数と偶数を交互に足すので、総和は奇、奇、偶、偶、奇、奇、……となる。総和が奇/偶の時の自明な下限がそれぞれ1/0なので、これを達成できれば最善となる。実験してみると、$N$が十分に大きければ常に下限が達成できるという予想が立つ。

$K=1$の場合、長さ4の区間は$0110$とわければよくて、$N$が$4$の倍数ならこれに従って等分できる。倍数でない場合もそれぞれ4つずつ等分した後、残りを適当にわければよい。

$K=2$について。また実験すると、長さ8の区間は$01101001$で等分できることがわかるので、$N$が小さい場合の構成を列挙した上で、以降は$8$個ずつ等分すればよい。

$K=3, 4$の場合も常に等分できるような長さの区間が見つかれば解決しそうだ。

$K=3$の場合は長さ16の区間は$0110100110010110$で等分できる。（ここでようやく、ひとつ小さい次数で得た列をflipしてくっつければよいことに気づく。）やはり$N$が小さい場合を列挙して、以降は$16$個ずつ等分すればよい。$K=4$も同様で、長さ32の区間を$01101001100101101001011001101001$で等分できる。

さて、$N$が小さい場合の解を用意する必要があるのだが、明らかにIPソルバで解けるのでOR-ToolsのCP-SATを使った。$K=3$までは愚直でいいとして、$K=4$はDPや半分全列挙でも簡単ではないように見える。（ちゃんと考えていない）

yukicoder No.1191 数え上げを愛したい（数列編）

• 問題
• AC

条件を満たす数列のすべての要素は互いに異なるので、昇順のものだけ数えて後で$N!$を掛ければよい。

$S_1$が与えられたとき、残りの項は

$f(k) :=$ $1$回の操作で$A$マス以上進むとして、$N-1$回操作してちょうど$k$マス進む場合の数

と考えると形としては$f(A)+f(A+1)+...+f(B)$通りのように求まる。（実際には$S_1+k \le M$であるような$f(k)$までしか足せない）したがって、$f$かあるいはその累積和$F(k) = \sum_{i=1}^kf(i)$が求めれば$S_1 = 1, 2, ..., N$について足せばよいことになる。形式的べき級数で考えると

$$\begin{aligned} f(k) & = [x^k](x^A+x^{A+1}...)^{N-1} \\ & =[x^k]\Bigl(\frac{x^A}{1-x}\Bigr)^{N-1} \\ & =[x^{k-A(N-1)}](1-x)^{-(N-1)} \\ & = [x^{k-A(N-1)}] \sum_{i=0}^\infty \binom{i+N-2}{N-2}x^i\\ & = \binom{k-A(N-1)+N-2}{N-2} \end{aligned}$$

$F(k)$を求めるなら、$(1-x)^{-1}$をもう一つ掛けることになるので$\binom{k-A(N-1)+N-1}{N-1}$となる。

CodeChef August Challenge 2020 - Smallest KMP

• 問題
• AC

最適な文字列がどういう形になっているか考えると、パターンの前後は$a...ab...b \ ...$と$... \ y...yz...z$のようになっているはずなので、$S$から$P$を除いた上でソートしたものを$S'$とし、$P$を$S'$のどこに挿入するのが最善か調べる。$P$を$S'$の$i$文字目に挿入したものと$S'$の$i+1$文字目に挿入したものを比較するとき、この比較は辞書順に関して下に凸になっているので、最小となる場所を二分探索で探せばよい。

CodeChef August Challenge 2020 - Insanely Hard School Exam

• 問題
• AC

1つの色についてだけ考える。平行な2直線がないとすると、直線が$x$本ある時のtruly-geometric triangle（以下TGT）の総数は$\binom{x}{3}$である。これを元に、$\operatorname{dp}[x][y] =$色$x$まで見て消しゴムの残量が$y$である場合のTGTの総数、として全体で${O}(NK)$のDPが可能なのでsubtask2, 3が解ける。

平行線がある場合について考える。平行関係は同値関係なので、異なる同値類の総数を$p$とし、$i$番目の同値類に属する直線が$L_i$個あるとする。$L_1 \ge L_2 \ge ... \ge L_p$と仮定してよい。これらの直線を消していくとき、同値類の総数をできるだけ減らすように消すのが最善なので、後ろから消していくのがよい。そこで$f(c, z) =$色$c$の直線が$z$本残っている場合のTGTの総数、として$f$を事前に求めておけば、上と同じDPで解ける。順序が固定されているので$f$自体もDPで求まる。

CodeChef August Challenge 2020 - Subsequence Frequency Counting

• 問題
• AC

数列$(A_i)$が整数$x$を$c_x$個含むとする。また、整数$x$が代表になるような部分列でちょうど$k$個の$x$を含むものの総数を$f(x, k)$とする。$f(x, k)$を二項係数で表すと、以下のようになる:

$$f(x, k) := \biggl( \sum_{i=0}^{k-1} \binom{c_1}{i}...\sum_{i=0}^{k-1}\binom{c_{x-1}}{i} \biggr) \binom{c_x}{k} \biggl(\sum_{i=0}^{k}\binom{c_{x+1}}{i} ... \sum_{i=0}^{k}\binom{c_N}{i} \biggr)$$

$f(x, k)$を$N$通りの引数について足せばよいが、毎回すべての二項係数を掛け算していては間に合わない。そこで、$\operatorname{dp}[x] := \sum_i \binom{c_x}{i}$という形の列をセグメント木で持っておくことを考える。$\operatorname{dp}$のそれぞれの値が適切な$k$に対応していれば、$f(x, k)$は$\operatorname{dp}[1...x-1]$の積と $\binom{c_x}{k}$と$\operatorname{dp}[x+1 ... N]$の積を掛けて求まることになる。$k=0$から$f$を求めていくとして、$\operatorname{dp}$の末尾から$k$が増えていくので、$k$の昇順、タイブレークは$x$の降順に$f(x, k)$を求めつつ$\operatorname{dp}$を更新していくと、一回の更新が${O}(\log N)$でできる。

CodeChef August Challenge 2020 - Chefina and Strange Tree

• 問題
• AC

与えられたグラフを根付き森とみなすと、ある頂点$v$を消す操作は、$v$のそれぞれの子の部分木と$v$の親側の木とをすべて切り離す操作と考えられる。オイラーツアー(pre-order)上で考えると、部分木は連続した区間に対応しているので、区間を切り貼りすることができればよい（下図）。そこでオイラーツアーを平衡二分木で保持することにする。

平衡二分木に$\min$を載せて、さらに遅延更新で加算ができるようにする。町$P_i$についての処理の流れは次のようになる:

1. $P_i$を含む木$T$（=1つの平衡二分木で表されたオイラーツアー）のすべての頂点の値から$A_{P_i}$を引く。
2. $T$の$\min$を求めて、$0$以下なら$T$上の二分探索で最小値を取る頂点$v$を探す。$v$が$i$日目に$0$になったと記録し、$v$の値を$+\infty$にセットする（再び$0$にならないようにするため。） $\min$が$0$より大きくなるまでこれを繰り返す。
3. 上図のように$P_i$の隣接頂点に関する部分木をすべて切り離す。

1を行う際に、$P_i$を含む平衡二分木を得る必要があるが、永続UnionFindを使った。事前に列$(P_i)$を逆順に走査しながら頂点をつないでおく。$P_i$を（正順に）処理する際には、その時点での$P_i$に対応する（UnionFind上の）根に平衡二分木を持たせるようにした。（でも、ちゃんと前処理すれば普通のUnionFindでできるか。）

計算量は全体で${O}(N\log N)$。

---

明らかに過剰なデータ構造をごちゃごちゃと貼ってしまった。physics0523さんの解説によると、操作の構造自体が木になっていることを利用できるらしい。なるほど……

AGC 037 B - First Second

• 問題
• AC

文字列を反転して条件を言い換えると、文字列$s, t, (|s| \le |t|)$に関する問題の条件は次のようになる。(添え字はPython風に表している)

1. $t$のprefixに$s$の最後の1文字を除いたもの$s[:-1]$が含まれ、
2. さらに$s$の最後の1文字$s[-1]$が$t$のそれ以降に存在する

1つ目の条件だけ考える場合、事前にTrieを作っておけば$s[:-1]$をprefixとして含むような文字列の総数は高速に数えられる。この時、$s[:-1]$をTrieで辿った際の終端ノードに2つ目の条件に関する情報があれば、うまく数えられそうに見える。具体的には、そのノードの部分木に含まれる文字列で$s[-1]$を含んでいるものの数が記録されていれば、2つ目の条件も満たすものが数えられる。

そこで、配列$\operatorname{dp_v}$を$\operatorname{dp_v}[c] :=v$の子に属する文字列で以降に文字$c$を含むものの総数、と定めて、Trieの各ノードに持たせればよい。

アルファベットのサイズを$\alpha$とするとき、この$\operatorname{dp}$配列は各ノードについてならし${O}(\alpha)$で作れるので、全体の計算量は${O}(\alpha\sum_i S_i)$。（一つの子ノードについて、親への遷移はちょうど1回で、遷移の計算量が${O}(\alpha)$。）

SBCLのハッシュテーブルに対するハック

SBCLのハッシュテーブルに対して、長さ$N$の列で${O}(N^2)$の時間がかかるようなものを作るメモ。

組み込みハッシュ関数の特性を生かしてキーを衝突させる

ハッシュテーブルの標準の4つのtestに対しては、それぞれハッシュ関数が用意されている:

CL-USER> (sb-impl::eq-hash 123456789)
123456789
NIL
CL-USER> (sb-impl::eql-hash 123456789)
123456789
NIL
CL-USER> (sb-impl::equal-hash 123456789)
1193941381175482768
NIL
CL-USER> (sb-impl::equalp-hash 123456789)
1193941381175482768
NIL

fixnumに対するeq、eqlのハッシュ関数はsb-kernel:pointer-hashそのものなので、（非負なら）整数がそのままハッシュ値になる。equal、equalpについてはsxhashが適用される。

どれも単純なハッシュ関数だが、これらがハッシュテーブルの中でそのまま使われるわけではなく、常にprefuzz-hashという変換を通る:

(defun prefuzz-hash (hash)
  ;; We're using power of two tables which obviously are very
  ;; sensitive to the exact values of the low bits in the hash
  ;; value. Do a little shuffling of the value to mix the high bits in
  ;; there too. On 32-bit machines, the result is is a positive fixnum,
  ;; but on 64-bit, we use 2 more bits though must avoid conflict with
  ;; the unique value that that denotes an address-based hash.
  (ldb (byte #-64-bit 29 #+64-bit 31 0)
       (+ (logxor #b11100101010001011010100111 hash)
          (ash hash -3)
          (ash hash -12)
          (ash hash -20))))

(defun mask-hash (hash mask)
  (truly-the index (logand mask hash)))

ハッシュ関数の返すハッシュ値はprefuzz-hashで31ビットのハッシュ値に変換される。さらに、このハッシュ値はmask-hashでマスクされ、ハッシュテーブルの内部に保持されている配列のサイズ$L$に応じて$L$未満のインデックスが対応する。（このサイズは常に2の累乗で、ハッシュ値の下位ビットを残すだけで求まる。）

まとめると、オブジェクトに対応するアドレスが計算されるまでの流れは

1. ハッシュ関数: オブジェクトに対するハッシュ値を決定する（ユーザー定義可能）
2. prefuzz-hash: ハッシュテーブル内部でハッシュ値を変換する
3. mask-hash: ハッシュ値から内部のインデックスを決定する

となる。さて、prefuzz-hashのコメントで書かれている通り、この実装全体の明らかな欠点として、上位ビットの変化に鋭敏でないというのがある:

CL-USER> (prefuzz-hash #b10101011101110111011101110111011101110111011101110111011101110)
691516418
CL-USER> (prefuzz-hash #b10111011101110111011101110111011101110111011101110111011101110)
691516418

prefuzz-hashでは$31$ビットでマスクする前に右シフトを複数入れて混ぜることでこの問題をある程度解消しているが、$-20$くらいだと上位11ビットの変化をまったく検知しないことになる。また、実際にはmask-hashでさらにビットが捨てられるので、検知できない範囲はもっと大きくなる。

これを利用して敵対的な入力を作ってみる:

(defun make-killer-sequence (length)
  (labels ((power-of-two-floor (x) ; x以下の最大の2の累乗を返す
             (ash 1 (- (integer-length x) 1))))
    (let* ((min (power-of-two-floor (floor #.(expt 2 62) length))))
      (loop for i from 1 to length
            collect (* min i)))))


(let ((list (make-killer-sequence 200000))
      (table (make-hash-table)))
  (time (dolist (x list)
          (setf (gethash x table) t)))
  table)
;; Evaluation took:
;;   42.093 seconds of real time
;;   42.031250 seconds of total run time (42.015625 user, 0.015625 system)
;;   99.85% CPU
;;   88,248,012,450 processor cycles
;;   22,735,232 bytes consed

(let ((list (loop repeat 200000
                  collect (random most-positive-fixnum)))
      (table (make-hash-table)))
  (time (dolist (x list)
          (setf (gethash x table) t)))
  table)
;; Evaluation took:
;;   0.031 seconds of real time
;;   0.031250 seconds of total run time (0.031250 user, 0.000000 system)
;;   100.00% CPU
;;   82,863,249 processor cycles
;;   22,741,968 bytes consed

ランダムな入力と比べて遅くなっていることがわかる。

乱択で衝突するキーを探す

ハッシュ関数の特性を考えなくても、SBCLの実装をそのまま再現して衝突するキーを探すことは当然できる。（ただし、探索時間はそれなりにかかる）

(defun make-killer-sequence2 (length)
  (declare (optimize (speed 3))
           ((integer 0 #.most-positive-fixnum) length))
  (assert (= 1 (logcount length))) ; 2の累乗
  (let* ((hash-fn (sb-impl::hash-table-hash-fun (make-hash-table :test #'eql)))
         (table (make-hash-table))
         (mask (- length 1)))
    (dotimes (i length)
      (loop
        (let* ((x (random most-positive-fixnum))
               (hash-value (prefuzz-hash (the (integer 0 #.most-positive-fixnum)
                                              (funcall hash-fn x))))
               (masked-value (logand mask hash-value)))
          (when (or (< (hash-table-count table) 2)
                    (gethash masked-value table))
            (push x (gethash masked-value table))
            (return)))))
    (loop for values being each hash-value of table
          append values)))

(let ((list (make-killer-sequence2 262144))
      (table (make-hash-table)))
  (time (dolist (x list)
          (setf (gethash x table) t)))
  table)
;; Evaluation took:
;;   32.281 seconds of real time
;;   32.281250 seconds of total run time (32.281250 user, 0.000000 system)
;;   100.00% CPU
;;   67,652,819,010 processor cycles
;;   32,850,480 bytes consed

(let ((list (loop repeat 262144
                  collect (random most-positive-fixnum)))
      (table (make-hash-table)))
  (time (dolist (x list)
          (setf (gethash x table) t)))
  table)
;; Evaluation took:
;;   0.100 seconds of real time
;;   0.109375 seconds of total run time (0.093750 user, 0.015625 system)
;;   [ Run times consist of 0.031 seconds GC time, and 0.079 seconds non-GC time. ]
;;   109.00% CPU
;;   202,079,224 processor cycles
;;   32,815,008 bytes consed

対応方法など

[少し追記]

1つ目のハックはこの実装特有の問題と言え、もう少しビットシフトを追加すれば難しくなりそうだが、2つ目は決定的ハッシュ全般の問題なので、決定的であることをやめる必要がある。たとえば、ハッシュを求める際にロード時（またはコンパイル時、実行時など）に生成した乱数を使うなどが考えられる。以下はロード時に決定する例^[1]:

(declaim ((mod #.most-positive-fixnum) *mask*))
(sb-ext:define-load-time-global *mask* (random most-positive-fixnum))

(defun my-hash (x)
  (declare (optimize (speed 3))
           ((integer 0 #.most-positive-fixnum) x))
  (let ((x (sxhash x)))
    (ldb (byte 62 0) (+ *mask* x (ash x -28) (ash x -36)))))

(make-hash-table :test #'eql :hash-function #'my-hash)

これも「自分には明らかなハックが思いつかない」程度のもので、fixnum以外に対するsxhashはたぶん安全ではないとか、そもそもビットシフトを適当に入れてXORを取るだけで十分なのかわからない、などいろいろ問題はありそう。ちゃんとしたやつについてはこの記事が参考になった。

---

1. ただし、起動時の*random-state*そのものが決定的なことに注意。時刻等から適当にシードを与えるか (sb-ext:seed-random-state t) を使う必要がある。 ↩︎

天下一プログラマーコンテスト2014 予選B D - 天下一芸術

• 問題
• AC

設計図上の番号$x$が与えられたとき、$x$を塗るための矩形としては、設計図上のすべての$x$を覆う最小の矩形以外は明らかに考慮する必要がない。また、この矩形に含まれる任意の番号$y (\neq x)$について、$y$は$x$の後に塗らなければならない。このようにして任意の2つの番号の前後関係を調べられるので、あとはそれらをすべて満たすような塗り方があるかどうか調べればよい。

部分点はペンキの順列を${O}(N!)$で全探索すれば取れる。また、違反している制約の数をスコアとして2点スワップの山登りをしたら満点が取れた。

---

落とせる入力があるかどうか考えてみたけれど思いつかなかった。

天下一プログラマーコンテスト2013 予選B E - 天下一最短路コンテスト

• 問題
• AC

一次元の問題として解ける。直線上に等間隔で$p_{100}, p_1, p_{98}, p_3, p_{96}, p_5, ..., p_4, p_{99}, p_2$と並べればよい。

---

思いつくのに二時間かかった。第一感でID順を工夫して頑張る問題と思ったのだけど、あまり筋がよくなかったかもしれない。

Introduction to Heuristics Contest

• 問題
• 提出

3問もあるのかと思って大急ぎで雑な焼きなましを書いたりしていた……

• とりあえず1点更新だけの単純な焼きなましを書いた。(81730043)
• 温度が適当すぎたので調整する。(99859730)
• 遷移時のスコア再計算を素朴にやっていたのを速くする。(102493050)
• 定数倍高速化する。 (104637270)
• 初期解を貪欲で作る。(112775607)
• 初期解を2日先読みの貪欲で作る。 (115690469)
• 初期解を3日先読みの貪欲で作る。(116929121)

単純な先読みは3日が限界なので、次はビームサーチをするべきだろうなと思った。この辺でコンテストが終わった。

• （焼きなましの）ほかの遷移を考える
• 遷移の平均計算量は双方向リストっぽい持ち方でもう少し頑張れそう？

---

Bがチュートリアルとわかった時点で完全に無視していたのだけど、あとでCを見たら、一点更新の焼きなまし自体があまりよくないと書いてあった。そう言われるととそうだなという気持ちにはなるけれど、コンテスト中に見ても手が止まってしまっただけな気がする。

Chokudai Contest 002 A - 約数をたくさんつくろう！

• 問題

バチャをした。

最初のほうに考えたこと:

• 小さい範囲での全探索の結果は、偶数しかない。
• 例えば40があったら20を入れるのは意味なさそうだし、逆に20を入れるなら40を入れるべきという話にはなる。
  • 整除関係において極大な数に絞る？
  • 整除関係において極大だからといって、素数を入れる意味はなさそう。
  • いちばん大きな数の半分以下の数を調べなくてよい。（2倍を入れて損はないので。） とすると、$(5\cdot10^8, 10^9]$を探す感じか。
  • $(5\cdot10^8, 10^9]$の中の偶数から探すとすると、$2.5 \times 10^8$個を調べることになる。この程度ならひとつひとつ調べるような方針はありそう。
• ある程度$d(n)$が大きい整数の集合から愚直焼きなまし、はありえる？

そもそも約数の総数はどのくらいが相場だったかか覚えていない。$10^9$から下って$998000000$あたりまで調べてmaxを探す:

1000000000 100個
999999990 192個
999999840 576個
999999000 1024個
998917920 1080個
...

だいたい相場がわかったので、とりあえず約数が600より多い整数を100個見つけて並べると36000。すでにけっこう高い。

約数の数が700以上、で同じことをやる。(37000)

新たに整数を追加した時のスコアの上昇を調べる:

999999000 1024
999989760 576
999959040 552
999949860 720
999936000 468
999915840 454
999853470 488
999835200 522
999814200 540
999782784 469
999760320 463
999758760 576
999734400 601
999702000 420
999697920 388
999694080 506
999657120 466
999638640 582
999621000 372
999567360 323
999566568 369
999532800 320
999511920 454
999507600 395
999500040 440
999488160 360
999447120 388
999398400 392
999383616 315
999375300 464
999371520 278
999350100 354
999311040 440
999306000 409
999295920 404
999278280 528
999266400 312
999223680 340
999217296 356
999187200 354
999180000 444
999167400 304
999159840 434
999129600 335
999114480 423
999076680 296
999028800 486
999016200 420
998917920 378
998899200 337
998891712 298
998875800 252
998857440 332
998856144 274
998844000 374
998820900 312
998811000 273
998808720 324
998786880 309
998776800 344
998749440 220
998712000 356
998692200 292
998688600 272
998686080 343
998634000 228
998612160 312
998609040 350
998600400 295
998585280 460
998565120 279
998557560 408
998549370 238
998529840 331
998524800 393
998497500 252
998490240 260
998457600 270
998418960 329
998382528 228
998373600 276
998361000 333
998300160 273
998298000 339
998289600 268
998265840 270
998243400 282
998197200 361
998150400 210
998147520 241
998086320 321
998071200 301
998038080 285
998000640 224
997978800 238
997956960 296
997949160 216
997920000 218
997908912 239
997883040 222

追加される約数の数がだんだん減っていく。このカーブを適切に決めて、閾値を超えるものだけ取ればよい？

二次回帰して回帰曲線を超えるものだけ取ろうとしたりする。1時間半ほど経過したところで、そんなことをする必要はないと気づく。できるだけスコアが上がるような貪欲を${O}(N^2)$でやればいいだけだった。

$10^9$から下って約数を400以上持つ整数を6000個列挙して、約数がもっとも増えるものを貪欲に取っていくと41200くらい。そこから山登りして41500くらい。

---

リアルタイムでchokudaiさんのヒントがあったらしい。でも、気づいていたら逆にこれに囚われてしまって苦戦しそう。

CodeChef June Challenge 2020 - The Delicious Cake

• 問題
• AC

与えられた点集合の凸包を考えるとき、凸包上の点をいくつか省いて内側の多角形に使うことは不可能に見える。そこで、凸包を何回も取ってネストされたレイヤー（凸多角形）を作り、クエリで与えられた頂点がどのレイヤーに含まれるか調べるというのを基本方針として思いつく。

ただ、与えられた点で1つのレイヤーの内部に含まれるものはそれ自身がいずれかのレイヤーに属さなければならないという条件がちょっと厄介に見える。縮退が起きている場合の扱いも書かれていなくてよくわからない。

しかし、とりあえず面倒なことは一切起こらないものとして、単純なコードを提出してみたら通ってしまった。（EPSすらちゃんと考慮していない）

CodeChef June Challenge 2020 - Convenient Airports

• 問題
• AC

辺をつなぎかえて2つの連結成分を1つの連結成分にするとき、サイクルをつぶしながらつなげばノーコストでつなげるので、連結成分ごとにサイクルの数のようなものを数えたい気持ちになる。何を数えるのか突き詰めると、結局「木と比べた時の余剰辺の数」を数えればいいことがわかる。

$K$個の連結成分のサイズを$n_1, ..., n_K$、辺数を$m_1, ..., m_K$とするとき、$m_1-n_1+1, ..., m_K-n_K+1$がそれぞれの余剰辺の数にあたる。連結成分が余剰辺の数に関して降順にならんでいるとする。これらを先頭から連結させていくとき、連結後の余剰辺は$\sum m_i - \sum n_i + 1$個であり、これが0になるまではノーコストで連結できる。余剰辺が0になるのは残っている連結成分がすべて木になる時で、以降は木同士をコスト2でつないでいく必要がある。

ただし、孤立点は（余剰辺のある連結成分に対してもノーコストでつなげないので）特別に扱う必要がある:

• 連結成分$C$に余剰辺が1つあると、2つの孤立点をコスト2で$C$につなぐことができる。
• 連結成分$C$に余剰辺がない、あるいは孤立点が1つしかない場合は、1つの孤立点をコスト2で$C$につなぐ必要がある。

さて、スコアを求めるだけではなく実際にシミュレーションしなくてはならない。最初にUnion-Findで辺を走査して、連結成分ごとに「ベースとなる木に含まれる辺」と「余剰辺」に分けた上で、余剰辺の数の降順でソートし、それらを（辺を組み替えながら）併合していった。孤立点は最初から分離しておいて、最後に併合した。

CodeChef June Challenge 2020 - Operations on a Tuple

• 問題
• AC

場合分けがかなりありそうだが、簡単なケースから考えていく。

• 0手で到達できるのは3対が最初から一致している場合
• 3手あればかならず到達できる
• 1手で到達できるのは次の5つの場合
  1. 2対が一致する
  2. 1対が一致して、残り2対の差が等しい
  3. 1対が一致して、残り2対の比が等しく、整数である
  4. 3対の差が等しい
  5. 3対の比が等しく、整数である

あとは2手と3手を区別する問題になるので、2手で到達できる $\Leftrightarrow$上の1-5のうちの少なくとも1つの状態に1手で到達できる、にしたがって考えればよい。とりあえず$p$に対する「意味のありそうな加算・乗算」を全部並べてみる:

• $p$に整数を足して$a$と等しくする ($a-p$を足す)
• $p$に整数を掛けて$a$と等しくする ($a/p$を掛ける)
• $p$に整数を足して、$a-p$と$b-q$を等しくする ($a+q-b-p$を足す)
• $p$に整数を掛けて、$a-p$と$b-q$を等しくする ($(a+q-b)/p$を掛ける)
• $p$に整数を足して、$a/p$と$b/q$を等しくする ($(aq-bp)/b$を足す)
• $p$に整数を掛けて、$a/p$と$b/q$を等しくする ($aq/bp$を掛ける)
• $p$と$q$に同じ整数を掛けて、$a-p$と$b-q$を等しくする　($(a-b)/(p-q)$を掛ける)
• $p$と$q$に同じ整数を足して、$a/p$と$b/q$を等しくする ($(bp - aq)/ (a - b)$を足す)

これらの8種類の加算・乗算を$p$には必ず適用するとして$q, r$に同じ操作を適用する/しないの4通りを調べ、それぞれの結果に対してあとで1手で到達できるかを上の基準で判定する。さらに、全体を$p, q, r$の順列6通りに対して調べる。

あとは、ゼロ除算が絡む場合の処理について検討する。「1手で到達できる場合」の3と5については場合分けするとして、後半の8種類の操作について考える。非ゼロ/0のように割り算が不能な場合については、その操作自体が不可能ということなので無視してよい。また、0/0が現れる場合は操作をせずとも目標とする状態が達成されているということなので、ほかの判定で拾われているはず……ということで、やはり無視してよい。

CodeChef June Challenge 2020 - Guessing Game

• 問題
• AC

嘘がない場合と同様に、二分探索で範囲を狭めていけそう。まず、上図の[A]のように全体の1/2の位置にある数を尋ねてGと返ってきた状況を考える。（赤線とその隣にあるアルファベットが、質問した位置と答えを表す。LIEは「真の数を含んでいるとすると答えが嘘である」区間を表す。）その次に全体の1/4の位置にある数を尋ねると、二回連続で嘘をつけないという条件により、3段目で×をつけた区間は除外できる。同様に、1回目でLが返ってきた場合は3/4の位置にある数を尋ねると同等の結果が得られる。2回の質問で可能な空間のサイズが3/4になっているので、これを繰り返せば部分点が取れる。

満点の条件では120回の質問で突き止める必要があるが、上の方針では最終的な候補数が$10^9 \times (3/4)^{60} \simeq 32$程度にしかならない。そこで、上図の[B]のようにG→Lという答えが返ってきた場合に、追加で3/4の位置にある数を尋ねるとサイズが1/2になることに注目する。この比率が毎回達成できれば間に合う計算だが、G→Gの場合にうまい追加質問がない。つまり、この区間割ではできればG→L, L→Gと答えてほしくてG→G、L→Lは望ましくないということになるが、それは割り方が最適でないということを意味する。

そこで、区間の割り方を調整して、G→LでもG→Gでも同じレートで空間が縮むようにしたい。2回目の質問で1/4の代わりに位置$x \in [0 ,1]$で区切るとする。このとき、G→Lでは3回の質問で空間が$x+1/4$倍になり、G→Gでは2回の質問で$1-x$倍になる。1回あたりの改善率が同じになる条件は$(x+1/4)^2 = (1-x)^3$なので、$x \simeq 0.31586$と求まる。計算してみると、120回の質問で足りることがわかる。

---

想定解の改善率は2回あたり33%だった。2回の質問を1セットとして、G→Lの場合には次のセットで前の結果を利用できるらしい。

BBC 004 E - simple finalization

• 問題

（引き分けを除いて）ちょうど$k$回戦後に$M$人が残る場合の数を考える。最後に残るプレイヤーの選び方が$\binom{N}{M}$通りで、残りの$N-M$人に$k$回のうちのどこで負けるかを割り振る必要がある。これは写像十二相の「ボールも箱も区別できる・各箱に少なくとも1つのボールが入る」場合にあたり、第二種スターリング数で書くなら$k! \cdot S(N-M, k)$。あとは$k$回の各じゃんけんで勝ちになった手がそれぞれ$3$通りありえるので、全体としては$\binom{N}{M}\cdot k! \cdot S(N-M, k) \cdot 3^k$通りと計算できる。これを$k=1, 2, ..., N-M$について足せばよい。

計算量はスターリング数の求め方次第で、Min_25さんの記事によると${O}(N\log N)$でできるらしい。

第三回 アルゴリズム実技検定

• 問題
• 提出

リアルタイム受験した。A～Nを解いて辛うじてエキスパートだった。（しかもNはオーダー的に間違っていると知りつつ枝刈りで通した……）

K

次の4つの配列を持ってシミュレーションする:

• $\operatorname{bottom}[x] :=$ 机$x$の一番下にあるコンテナ
• $\operatorname{top}[x] :=$ 机$x$の一番上にあるコンテナ
• $\operatorname{prev}[y] :=$ コンテナ$y$の下にあるコンテナ
• $\operatorname{next}[y] :=$ コンテナ$y$の上にあるコンテナ

もっと楽にできるらしい。

L

優先度付きキューを二つ用意して、一つは先頭の商品全部が入っている状態を保ち、もう一つは二番目までの商品全部が入っている状態を保つ。（どちらかのキューに既に買われた商品が残っている、は問題ない。買われたものを記録しておいて、既に買われたものを取り出した場合は飛ばせばよい）

N

$x$をスワップするクエリが来ると、区間$[x, x+1]$の順序が乱れる。順序が乱れたところを記録しておいて、ソートクエリが来たらそこだけソートすればよさそうだが、計算量的に「正しい」やりかたを書けなかった。例えば$[10, 30], [40, 50], [100, 120]$が乱れているとして、$[20, 110]$のソートクエリが来たら、$[20, 30], [40, 50], [100, 110]$だけソートすればよい……のだが、それによって正しい順序に戻るのは$[40, 50]$だけで、$[10, 30], [100, 200]$は全体としては乱れたままなのが困りごとだった。（つまり、素朴にやると中途半端な区間を何度もソートさせるような入力でオーダーが改善していない。）　この例でいうと、$[10, 30]$のうち$[20, 30]$がソートされたら、もう一度$[20, 30]$や$[21, 30]$のソートクエリが来ても何もする必要がないとか、列を平衡二分木などで保持しておいて、$[18, 30]$のソートクエリが来た時に、$a_{19}, a_{18}$だけ挿入しなおすような処理ができればならしで間に合っているとか、部分的なアイデアは思いつくものの全体としてうまく動くようにまとめきれなかった。（しかし、終了直前に不完全なまま出したら通ってしまった。）

「中途半端なソート」でも転倒ベースで見ればうまく扱える、確かに。しかし、それでも実装はまあまあ大変に見える。

JOI2009 春合宿 - Pyramid

• 問題
• AC

ピラミッドを高さの降順にソートしてBFSのイメージで埋めていく。具体的には$H=3000$から降りながら次を繰り返せばよい:

1. 頂上の高さが$H$のすべてのピラミッドについて$H$を答えに足し、その座標$(x, y)$を（スタックなりキューなりに）積んでおく。
2. 前のループで高さ$H+1$として積んでおいた頂点の八方を調べて、それぞれ訪問済みでなければ$H$を答えに足して座標を積んでおく。

メモリ制約が厳しいのでいろいろ使いまわす必要がある。

JOI2010 春合宿 - Sengoku

• 問題
• AC

$(i, j)$を通る傾き$1$の直線の切片は$j-i$で、傾き$-1$の直線の切片は$i+j$になる。

とりあえず重複のことは忘れて番兵毎に数えると、傾き$1$の直線の通るマスは$L - |i-j|$個あり、傾き$-1$の直線の通るマスは$i+j < L$のとき$i+j+1$個、$i+j \ge L$のとき$2L - (i+j+1)$個あることがわかるので、まずはこれらの総和が基本になる。

次に、重複を除くことを考える。まず、切片と傾きが同じ直線は完全に重なるので、登場した切片を記録しておいて、前に見たものは無視することで重複を避けられる。

最後に傾き$1$の直線と傾き$-1$の直線の交点の数を引く必要がある。まず、交点が格子点になるのは切片が偶数同士、奇数同士の場合なので、切片が偶数の直線についてのみ考えることにする。（奇数のものの交点も同様に数えられる。） 傾き$1$で切片が$C$の直線と傾き$-1$の直線が与えられた領域内で交わるのは、後者の切片が$[|C|, 2(L-1) - |C|$]に入っているとき、またその時に限るので、ソートしておいてそれぞれ二分探索で数えられる。