2020年2月28日金曜日

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

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

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

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

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


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

2020年2月26日水曜日

CodeChef UWCOI 2020 - Blocks

CodeChef UWCOI 2020 - Blocks

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

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

2020年2月24日月曜日

KUPC 2012 G - 村

KUPC 2012 G - 村

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

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

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


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


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

KUPC 2012 F - Acceleration of Network

KUPC 2012 F - Acceleration of Network

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

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

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

タイプ00のサービス: 復旧度の増分はQ0Q_0の長さに等しい。
タイプ11のサービス: 復旧度の増分が一日毎にQ1Q_1の長さだけ増える。
タイプ22のサービス: 復旧度の増分の増分が一日毎にQ2Q_2の長さ×2\times 2だけ増える。1

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


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


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

2020年2月22日土曜日

強連結成分分解と2-SAT

強連結成分分解と2-SAT

http://www.prefield.com/algorithm/graph/strongly_connected_components.html
https://qnighy.hatenablog.com/entry/20100102/1262443288 (qnighyさんの解説)

強連結成分分解を1パスでやるアルゴリズムで、普通のKosaraju’s algorithmより定数倍がだいぶ速かった。初出がわからない。→たぶんTarjan’s algorithm

注意点として、DFSのpost orderで強連結成分を追加していくので、そのまま使うと強連結成分の番号がトポロジカル順序の逆順になる。(必要なら最後に番号を付け替えればよい。)


2-SATで勘違いしていたことがあった。論理式ABA \lor Bについては¬A\neg AからBBへの辺と¬B\neg BからAAへの辺を張って、論理式ABA \rightarrow Bに対してはAAからBBに辺を張るものだとなんとなく思っていたのだが、後者は間違っていて、¬AAB¬B\neg A \rightarrow A \rightarrow B \rightarrow \neg Bみたいな例で充足可能と判定されてしまう。論理式ABA \rightarrow Bに対しては辺ABA \rightarrow Bに加えて¬B¬A\neg B \rightarrow \neg Aを張る必要があった。

2020年2月17日月曜日

CodeChef Februrary Challenge - No Change Required

CodeChef Februrary Challenge - No Change Required

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

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


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

2020年2月9日日曜日

remove-duplicatesの計算量

remove-duplicatesの計算量

SBCLのremove-duplicatesについて。

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

  1. 入力がリストで
  2. keytest-notが与えられていなくて
  3. testeqeqlequalequalpのどれか

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

自分が必ずO(N2){\mathcal 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関数に含めてもよいことになるので、O(N2){\mathcal O}(N^2)で比較しないのは標準に反するように見えたからだった。

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

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

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


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


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

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

2020年2月3日月曜日

JOI2007 春合宿 - circuit

JOI2007 春合宿 - circuit

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

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

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

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

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

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