エクサウィザーズ2019 C - Snuke the Wizard

• 問題
• AC

最初、位置ではなくゴーレムにアルファベットが振られている問題と読み間違えてしまい、すべて実装し終わってサンプルでテストするまで気づかなかった（30分ロス）。誤読することがあるのは仕方ないけれど、最初にサンプルをシミュレーションすれば気づけたはず。

考察は基本原則に従った: AとBを同時に処理しなければならない場合はまず、Aだけで良いとしたら？と考える。今回の場合、LとRが混在することで逆に問題が簡単になるというのは明らかにありえないので、まず片方だけの場合について解けなければどうしようもないと思える。

呪文がRしかない場合について、サンプルのAABCBDBAを例にとって考える。初期位置$i$のゴーレムが（右に）消滅するのはそれぞれ呪文の部分列に

1. A, A, B, C, B, D, B, A
2. A, B, C, B, D, B, A
3. B, C, B, D, B, A
4. C, B, D, B, A
5. B, D, B, A
6. D, B, A
7. B, A
8. A

が含まれている場合だが、これらを素朴に１つずつチェックしていくと${\mathcal O}(QN)$になってしまう。しかし、例えば呪文の部分列にB, D, B, Aが含まれれば当然D, B, Aも含まれるので二分探索して境界を探せば${\mathcal O}(Q \log N)$ですむ。

こうなると、呪文にLとRが混在する場合も二分探索でできるのでは？と考えたくなるが、できる。ゴーレムが他のゴーレムを追い越すことはないので、初期位置$i$のゴーレムが右に消えるなら初期位置$i+1$のゴーレムも消えるし、左に消えれば$i-1$のゴーレムも左に消える。したがって、$i \le p$なる$i$がすべて左に消滅するような最大の$p$と、$q \le i$なる$i$がすべて右に消滅するような最小の$q$を二分探索で求めると、答えは$\max (0, q - p - 1)$である。

いきなり太字の核心部分に気づけるほうが頭いい感じだけど、気づかなくても解けるようになったのは進歩だと思うことにする。

ABC 122 D - We Like AGC

• 問題
• AC

メモ化で書いていたら混乱したのでボトムアップのDPで書き直した。あとで解き直すかも。

昔の AtCoder (りんごさん体制になる前) だったら D で N <= 10^18 という問題が旧 ARC の後半で出せたと思いますが、今だったらそういう独自性のないテンプレ問題は AGC どころか ARC でも即 reject ですね…現状の AtCoder の問題点の一つはビギナーを卒業した人の「お勉強」に適さないことです。

— えびま (@evima0) 2019年3月24日

（高々）64次元空間の線型変換とみなせるのか。なるほどー…… 言われてみればとなるけど、これを${\mathcal O}(\log n)$で解けと言われたら今の自分には普通のDPすら見えなくなりそう。

ABC 008 C - コイン

• 問題
• AC

任意のコイン$k$について確率変数$X_k$を$X_k(表) = 1$、$X_k(裏) = 0$と定める。また、コイン$k$の約数が書かれている（$k自身$を除く）コインの数を$d_k$とする。$d_k=0$なら$E[X_k]=P[X_k = 1] = 1$である。また、$d_k > 1$で$d_k$が偶数なら
$\begin{aligned} E[X_k] = \frac{(N-1-d_k)!d_k!}{N!} \sum_{p=1}^N &\binom{p-1}{0}\binom{N-p}{d_k} + \binom{p-1}{2}\binom{N-p}{d_k-2} + \\ & ... + \binom{p-1}{d_k}\binom{N-p}{0} \end{aligned}$
であり、$d_k$が奇数なら
$\begin{aligned} E[X_k] = \frac{(N-1-d_k)!d_k!}{N!} \sum_{p=1}^N & \binom{p-1}{0}\binom{N-p}{d_k} + \binom{p-1}{2}\binom{N-p}{d_k-2} + \\ & ... + \binom{p-1}{d_k-1}\binom{N-p}{1} \end{aligned}$
である。ただし、$n \le m$のとき$\binom{n}{m}=0$とする。求める期待値は$E[\sum X_k] = \sum E[X_k]$なので、そのまま計算できる。64ビット整数に収まらないのでdouble floatを使った。計算量はdouble floatに収まる範囲では${\mathcal O}(N^2)$。

解説にははるかに筋の良い考え方が書いてあった。

WUPC 2012 E - 会場への道

• 問題
• AC

いったん会場に着いたら戻れないというルールを見落としてWAし続けた。コーナーケースで落ちてるっぽい時は、問題文を読みなおすべき。

あと、ダイクストラ法の空間計算量の見積もりをときどき間違えてしまう。ダイクストラ法では１つの辺につき高々１回しかenqueueされないので長さ$|E|$の優先度付きキューを用意すればよいのだが、今回は28倍に増えるので$28 \times |E|$……ではなく、逆辺もあるので$28 \times 2 \times |E|$だった。¹ （追記） 結局二分ヒープを可変長にしたらこの手の悩みがなくなった。もっと早くやればよかった……

---

1. 一般の無向グラフでダイクストラ法をする場合、データとしては$2|E|$個の有向辺を持つことになるが、アルゴリズム中では辺$v \rightarrow w$がキューに加わる時点で頂点$v$への最短距離が確定しているので$w \rightarrow v$がキューに加わることはない。したがって、キューのサイズは$|E|$で十分である。ただ、この問題では頂点に状態を持たせた時点で無向グラフではなくなっている。 ↩︎

AGC 032 A - Limited Insertion

• 問題
• AC

$b&#x27;_i = b_{i+1}-1$として0-basedで考える。$k\in \{0, 1, ..., N-1\}$が与えられたとせよ。$b&#x27;_k$より左にある数（$b&#x27;_0, ..., b&#x27;_{k-1}$）が$b&#x27;_k$個より多く挿入されると、もう$b&#x27;_k$は挿入できない。また、$b&#x27;_k$より左にある数を少なくとも$b&#x27;_k$個挿入ずみでないと、$b&#x27;_k$はまだ挿入できない。したがって、$B = \{b&#x27;_i | b&#x27;_iより左の数がちょうどb&#x27;_i個挿入ずみ\}$から１つ選んで挿入する操作を$N$回繰り返せればそれが答えになるし、できなければ不可能である。ここでもう少し考えると、常に$B$の中でいちばん右にある数だけ調べれば良いことに気づく。というのも、$b&#x27;_i$より右にある数が挿入ずみかどうかは$b&#x27;_i$が挿入できるかどうかに影響しないからである。計算量は${\mathcal O}(n^2)$。

操作を逆順に見るとよりシンプルになるらしい。それは最初に検討するべきだった。

CS AcademyのSBCLについて

• /box/Main.lispをコンパイルしてから/box/Main.faslを実行する。
• 実行時エラーが出てもWrong Answerになる。（たぶん--scriptで実行していない。）
• SBCLのバージョンは1.3.3。
• スタックサイズを増やす方法がAtCoderとは少し違うので以下にメモ。実行時エラーがWrong Answerに化ける仕様もこれで解決しているかもしれない。

#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "32MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))

CS Academy FIICode 2019 Round #3 - Array Macao

• 問題
• AC

しょうもないバグで間に合わなかったのだが、想定解より遅い方法を取ってしまったのでメモしておく。以下、すべて0-basedとし、整数$k$の10進表示に含まれる数字の集合を$D(k)$とする。

$f_A(i, d) = \begin{cases} a_i を末尾とする最長列の長さ &amp; (d \in D(a_i)) \\ 0 &amp; (d \notin D(a_i)) \end{cases} \\ f_B(i, d) = \begin{cases} b_i を末尾とする最長列の長さ &amp; (d \in D(b_i)) \\ 0 &amp; (d \notin D(b_i)) \end{cases}$

とすると、答えは
$\max (\max_{d \in [10]} \max_{i \in [n-1]} f_A(i, d), \max_{d \in [10]} \max_{i \in [n-1]} f_B(i, d))$
であり、漸化式は次のように書ける。

$f_A(i, d) = \begin{cases} 1+ \max_{l \in D(a_i)} \max_{k \in [i-1]} f_B(k, l) &amp; (i \ge 1 かつ d \in D(a_i)) \\ 1 &amp; (i = 0 かつ d \in D(a_0)) \\ 0 &amp; (d \notin D(a_i)) \end{cases} \\$
$f_B(i, d) = \begin{cases} 1+ \max_{l \in D(b_i)} \max_{k \in [i-1]} f_A(k, l) &amp; (d \in D(b_i) かつ第2項\ge 1)\\ 0 &amp; (それ以外)\\ \end{cases}$

$f_A$と$f_B$が微妙に異なるのは、$b_i$を先頭にした列が作れないからである。漸化式の$\max_{k \in [i-1]}f(k, l)$の部分は数字$l$に対応するBITがあれば${\mathcal O}(\log n)$で求まるので、計20本のBITを用意することで全体としては${\mathcal O}(n \log n)$になる。（350msくらいでAC。）

しかし、解説にある通り、以下の通りにDPすれば${\mathcal O}(n)$で求まるはず。

$f_A(k, d) =$ 問題を$\{0, ..., k\}$に制限したとき、末尾が$(a_i)_{i \in [k]}$から選ばれていてかつ数字$d$を含む数であるような最長列の長さ。

$f_B(k, d) =$ 問題を$\{0, ..., k\}$に制限したとき、末尾が$(b_i)_{i \in [k]}$から選ばれていてかつ数字$d$を含む数であるような最長列の長さ。