2019年3月30日土曜日

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

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

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

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

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

  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

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

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

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

2019年3月26日火曜日

ABC 008 C - コイン

ABC 008 C - コイン

任意のコインkkについて確率変数XkX_kXk()=1X_k(表) = 1Xk()=0X_k(裏) = 0と定める。また、コインkkの約数が書かれている(kk自身を除く)コインの数をdkd_kとする。dk=0d_k=0ならE[Xk]=P[Xk=1]=1E[X_k]=P[X_k = 1] = 1である。また、dk>1d_k > 1dkd_kが偶数なら
E[Xk]=(N1dk)!dk!N!p=1N(p10)(Npdk)+(p12)(Npdk2)+...+(p1dk)(Np0) \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}
であり、dkd_kが奇数なら
E[Xk]=(N1dk)!dk!N!p=1N(p10)(Npdk)+(p12)(Npdk2)+...+(p1dk1)(Np1) \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}
である。ただし、nmn \le mのとき(nm)=0\binom{n}{m}=0とする。求める期待値はE[Xk]=E[Xk]E[\sum X_k] = \sum E[X_k]なので、そのまま計算できる。64ビット整数に収まらないのでdouble floatを使った。計算量はdouble floatに収まる範囲ではO(N2){\mathcal O}(N^2)

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

ABC 122 D - We Like AGC

ABC 122 D - We Like AGC

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

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

2019年3月25日月曜日

WUPC 2012 E - 会場への道

WUPC 2012 E - 会場への道

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

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


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

2019年3月24日日曜日

AGC 032 A - Limited Insertion

AGC 032 A - Limited Insertion

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

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

2019年3月21日木曜日

CS Academy FIICode 2019 Round #3 - Array Macao

CS Academy FIICode 2019 Round #3 - Array Macao

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

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

とすると、答えは
max(maxd[10]maxi[n1]fA(i,d),maxd[10]maxi[n1]fB(i,d))\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))
であり、漸化式は次のように書ける。

fA(i,d)={1+maxlD(ai)maxk[i1]fB(k,l)(i1dD(ai))1(i=0dD(a0))0(dD(ai)) f_A(i, d) = \begin{cases} 1+ \max_{l \in D(a_i)} \max_{k \in [i-1]} f_B(k, l) & (i \ge 1 かつ d \in D(a_i)) \\ 1 & (i = 0 かつ d \in D(a_0)) \\ 0 & (d \notin D(a_i)) \end{cases} \\
fB(i,d)={1+maxlD(bi)maxk[i1]fA(k,l)(dD(bi)21)0() f_B(i, d) = \begin{cases} 1+ \max_{l \in D(b_i)} \max_{k \in [i-1]} f_A(k, l) & (d \in D(b_i) かつ第2項\ge 1)\\ 0 & (それ以外)\\ \end{cases}

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

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

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

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