Code Formula 2014 予選A C - 決勝進出者

• 問題
• AC

すべて0-basedで考える。$i$回目の予選で$x$位になった人を$Nx + i$位とみなすと、順位を重複なしで比較できる。$Nx+i$位になった人より上位になれる可能性がある人の総数は、$i$回目の予選までにそれ以上の順位を取った人$+(n-i-1)\times x$に等しいから、この数が$k$より小さければ本選進出が決定する。これをもとにシミュレーションすればよい。

具体的には、現時点の最高順位をBITや平衡二分木などに記録して、$i$回目の予選までにある順位より上の順位を取った人の人数を取得できるようにしておけばよい。各予選について$a_{i, 0}, a_{i, 1}, ..., a_{i, K-1}$を順に見ていって、それぞれ$\log(NK)$で本選進出を判定できる。

問題は、$i$回目の予選で$K$位以内に入ってない人も本選進出が決まる可能性があることで、これを素朴に調べるとすべての予選について${O}(NK)$回の走査をすることになる。しかし、一回の予選内で$x$位の人と$y$位の人がいて$x < y$であるとき、$y$位がその順位によって進出決定する$\Rightarrow x$位がその順位によって進出決定する、が成り立つことを利用すると、全部調べなくてもよい。つまり、各予選について本選進出が決定している人/していない人の境界だけ持っておいて、毎回そこから調べればよいことになる。これで全体の計算量が${O}(NK \log(NK))$になる。

---

よく考えると、各予選について毎回${O}(NK)$の走査をしても余裕で間に合う制約だった。

CodeChef UWCOI 2020 - Blocks

• 問題
• AC

整数$x$を質問して答え$N-x$が帰ってくること（つまり、末尾まで一致していること）と、問題の列が長さ$x$のprefixの繰り返しになっていることは同値である。質問する$x$は$N$の約数だけでよくて、 $10^6$以下の自然数の約数の数は高々$240$個なので、すべて調べれば部分点が取れる。

$N$を素因数分解して$N = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$とする。$N/p_i^{e_i}$を質問して末尾まで一致している$\Leftrightarrow$素因数$p_i$は必要ない、が成り立つので、これで必要な素因数を割り出したあと、それぞれの指数に関して二分探索すればよい。高々9回で可能というのは全列挙で示すしかなさそう？

KUPC 2012 F - Acceleration of Network

• 問題
• AC

一日毎に復旧度をシミュレーションすればよさそう。タイプ$0, 1, 2$のサービスについて優先度付きキュー$Q_0, Q_1, Q_2$を用意しておいて、復旧したサービスは追加して、期限切れになったサービスは削除すればよい。全体の流れとしては

1. 今日の復旧度を記録する
2. $Q_0, Q_1, Q_2$から期限切れになったサービスを削除する
3. 今日復旧したサービスを加える
4. 復旧度を更新する

を繰り返すことになるが、4の更新の仕方が問題になる。タイプ毎にわけて考える:

タイプ$0$のサービス: 復旧度の増分は$Q_0$の長さに等しい。
タイプ$1$のサービス: 復旧度の増分が一日毎に$Q_1$の長さだけ増える。
タイプ$2$のサービス: 復旧度の増分の増分が一日毎に$Q_2$の長さ$\times 2$だけ増える。^[1]

これらをそのままシミュレーションすればよい。

---

解説を読んだ。$(今日の日付-復旧した日付)^2$の式を$(t-s_i)^2 = t^2 -2s_it +s_i^2$みたいに展開してしまえば、二次関数の係数の増減だけでシミュレーションできるらしい。ぜんぜん持ってない考え方だった。

---

1. $x^2 - (x-1)^2 = 2x-1$だから、1つのサービス毎に、復旧度の増分の増分が2ずつ増えていく。 ↩︎

KUPC 2012 G - 村

• 問題
• AC

とりあえずrange tree + fractional cascadingを貼ったらMLEした。

2点の表札が同じであるとき、またその時に限り、それぞれの点$(x,y)$から見てもう一つの点は正方形$[x-2R, x+2R] \times [y-2R, y+2R]$に入っていることに注目して平面走査する^[1]。

各点$(x, y)$についてクエリ$(x, y, \text{"add"}), (x + 2R, y, \text{"delete"})$を用意しておいて、$2N$個のクエリを$x$に関してソートする。あとはクエリの先頭から順に平衡二分木に$y$座標を追加/削除していく。$y$を追加する際に$[y-2R, y+2R]$にすでに点がなければ、新しい表札が必要ということになる。

---

座標の重複があるのでmultisetにあたるものが必要だと思うけど、とりあえず普通のtreapを投げたら通ってしまった。（キーが全部衝突すると深さが${O}(N)$になるのでハック可能なはず。）

---

1. 全部$\pm 2R$でやったが、もちろん$\pm R$でもよい。 ↩︎

CodeChef Februrary Challenge - No Change Required

• 問題
• AC

整除性に関する列$D_1|D_2|...|D_N|P$が作れるとき、$P$を超えるコインを持っていれば必ずちょうど$P$が払える。

上の条件を満たさない場合の反例の作り方について。$P$を割り切らない$D_i$がある場合は自明な例が作れる。すべての$D_i$が$P$の約数である場合、$D_{i-1} \nmid D_i$となっている部分を見つける。このとき、$xD_i = P$を満たす$x$と$yD_{i-1} > D_i$を満たす最小の$y$について、コイン$i-1$を$y$枚、コイン$i$を$x-1$枚持てば、どのコインを減らしても$P$未満になる。

---

最初、すべてが$P$の約数ならNOと決めつけていて、$P=12$で4セント2枚と6セント1枚みたいな例に気づくのに長時間かかってしまった。

remove-duplicatesの計算量

SBCLのremove-duplicatesについて。

remove-duplicatesは常に${O}(N^2)$と思っていたのだけど、${O}(N)$の場合もあることを知った。^[1] 具体的には、

1. 入力がリストで
2. keyとtest-notが与えられていなくて
3. testがeq・eql・equal・equalpのどれか

である場合にハッシュテーブルが使われて${O}(N)$になる。

自分が必ず${O}(N^2)$になると思いこんでいたのはCLHSの次の記述

The elements of sequence are compared pairwise, and if any two match, then the one occurring earlier in sequence is discarded, unless from-end is true, in which case the one later in sequence is discarded. (http://clhs.lisp.se/Body/f_rm_dup.htm)

が理由で、pairwiseに比較すると決まっていればそれを利用した副作用をtest関数に含めてもよいことになるので、比較自体をやめてしまうのは標準に反するように見えたからだった。

でも、よく考えてみるとtestがeqlの場合は副作用がないので、pairwiseの比較をさぼっても挙動を区別できない。^[2] keyがある場合にハッシュテーブルを使わないのは、keyが副作用を持つケースがあるからだろう。しかし、入力がリストの場合に限定している理由はわからない。

delete-duplicatesにはこの最適化がなぜかない（のでこちらのほうが遅くなったりする）のだが、in-place性を重視する意図があるかもしれない。

この実装になったのはわりとずっと昔のことらしい。

---

redditも参照。副作用云々は別に関係ない気がしてきた。

---

1. AtCoderで ar44denchiさんの提出を見て気づいた。 ↩︎

2. ユーザー定義のテスト関数でも、sb-impl::*user-hash-table-tests*に登録済みでsb-c::flushableとかの宣言があれば最適化してもよいことになる？ ↩︎

JOI2007 春合宿 - circuit

• 問題
• AC

置換の累乗根を考える問題。ひとまず置換を巡回置換に分解すると、巡回置換の長さと個数だけに意味があることがわかる。与えられた置換が長さ$l$の巡回置換$C(l)$個から構成されるとして、累乗根を探す。

一般に長さ$L$の巡回置換を$k$乗すると長さ$L/\gcd(L, k)$の巡回置換$\gcd(L, k)$個に分解される。逆に長さ$l$の巡回置換がいくつかある時、$L = \gcd(L, k)l$を満たすような$L$があれば、長さ$l$の巡回置換を$\gcd(L, k)$個合わせた置換の$k$乗根として長さ$L$の巡回置換を構成できる。

そこで、長さ$l$の巡回置換に対して可能な長さ$L$の集合を$S(l, k)$とする:

$$ S(l, k) = \{L : L = l\gcd(L, k), \: L \le f(l)l\} $$

長さ$L \in S(l, k)$を採用するとき、長さ$l$の巡回置換を$\gcd(L, k)$個消費して（$k$乗根となる長さ$L$の）巡回置換が作れることになる。したがって、この問題は$S(l, k)$内の長さを重複を許して自由に使って$C(l)$個をちょうど消費する問題になる。（重複あり部分和問題） この問題をすべての$l$について解けばよい。解けない$l$があれば解なしとなる。

計算量について。$S(l, k)$を求めるのは$1, 2, ...f(l)l$をすべて試せばよくて、$f(l)l$の総和はちょうど$N$に等しいのでこの部分は${O}(N)$である。$L$は$k$の約数に$l$を掛けたものだから、$S(l, k)$のサイズは$k$の約数の総数$d(k)$を超えない。したがって、各部分和問題のサイズは$C(l)d(k)$で総和は$Nd(k)$。全体の計算量も${O}(Nd(k))$になる。