Yukicoder No.720 行列のできるフィボナッチ数列道場 (2)

問題

No.720 行列のできるフィボナッチ数列道場 (2) - yukicoder

アルゴリズム

$$ s[n] = \sum_{i = 0}^{n} {F[i*m]} $$

$$ B = {\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}}^m $$

$$ A = { \begin{bmatrix} 1 & 0 & 1 \\ 0 & B[0][0] & B[0][1] \\ 0 & B[1][0] & B[1][1] \end{bmatrix} } $$

とおいたとき

$$ \begin{bmatrix} s[n+1] \\ F[m(n+2)+1] \\ F[m(n+2)] \end{bmatrix} = A \begin{bmatrix} s[n] \\ F[m(n+1)+1] \\ F[m(n+1)] \end{bmatrix} $$

が成立してこれで行列累乗すればよい。 計算量は$O(\log{n}+\log{m})$

コード

Fractional Cascading について

日本語で書かれた記事が見つからなかったのでざっくり書く

問題

vを二次元配列として、ソート済みの各配列v[i]に対してlower_boundを求めるクエリを処理する。

アルゴリズム

愚直に二分探索したら配列数をkとしてO(klog(n))となる。Fractional Cascading を用いるとO(log(n)+k)となる。

前処理をして今の二分探索の結果から次の位置を推定できるようにしていく。末尾から今探索する配列と次に探索する配列を混ぜることによって今の探索の結果から次に調べる位置が推定できるようにしていく。次の配列の全要素と混ぜると計算量が爆発するのでふたつ飛ばしに1/2個をサンプリングして混ぜる。すると混ぜるたびに半分になっていくので動的配列のときとかと同じノリで計算量が線形になる。もちろん次の正確な位置はわからなくなるのでちょっと周辺をさがす必要が出てくる。英語版wkipediaに具体例がある。

実装

参考にしたサイト

Fractional cascading - Wikipedia

あとでもうちょっと詳しくするかも

Atcoder Regular Contest 079 E - Decrease (Judge ver.)

問題

arc079.contest.atcoder.jp

解法

二分探索をする。操作を全要素に+1、特定の要素に-(n+1)として見ると、k回の操作で全要素をn-1以下にできるかどうかはaの各要素の値xに関して$ \lceil \frac{x-(n-1-k)}{n+1} \rceil $の和をとってkと比較するとわかる。

普通に二分探索をしようとすると単調性が成り立つは微妙に嘘とわかるのでちょっと工夫をする。

check(x) := x回の操作で全要素がn以下になるか とする。

あるkに関してcheck(k)を仮定する。 !check(k+1)ならば最大の要素を減らなければどうしようもないので、最大のやつから選択し減らしていくと任意の要素の選択の仕方のうちで操作の回数が最小化される。

そして全要素に操作を適用すると(たぶん)k+n回の操作でもすべての要素をn-1以下にできる。よってあるl(0 < l <= n)に関して check(k) -> check(k+l) が成立する。

よって区間を2nの大きさの区間に分割して、分割後の2nの大きさの区間のなかで全要素をn-1以下にできるようなものがあればその区間はtrueといったように区間ごとに真偽を割り振る。上での考察よりこのような真偽の割り当てに対しては単調性が成り立つので、二分探索で初めてtrueとなるような区間を求める。そしてその区間内を線形探索する。

計算量はたぶん $ O(n^{2} log{\sum a[i]}) $

ソースコード

今回の想定解みたいな計算量の評価が難しい解法を思いつくのが難しい。

AOJ 1604 デッドロック検出

問題

Deadlock Detection | Aizu Online Judge

解法

dp[今、各スレッドでロックしている資源をあわせたものの集合] = (次にどれかのスレッドが確保する可能性のある資源の集合の集合) みたいにする。

そして最終的に $ \exists S, \exists e \in dp[S], e \subset S $が成り立つとそこで行き止まりになるのでデッドロックとなる。

マージを高速に行いたいので集合を表すデータ構造としてはbitsetを使う。

計算量は $ 3^{10} \times 10 \times 2^{10}/64 + (2^{10})^{2} \times 10 $ くらい

コード

感想

最初紙に書かずに考察していたらひたすらごちゃごちゃしてごちゃごちゃしてごちゃごちゃした。

紙に書くの、大事

ICPC 2017 国内予選 参加記

チームnasubidenamidaでふるやん(@furuya1223)さんといないち(@37dbye)さんと出た。10位を取れた。

ふるやんさんの参加記はこちら。

www.creativ.xyz

コンテスト前

ゼミを早退してコンテスト会場に来て準備をする。模擬予選から特になにもしておらずほげ。

コンテスト中

模擬予選と同様にAを僕が担当する。まあやるだけ。

次にふるやんさんがCを書き始めDを考える。題意をつかむのに若干苦労したけど積制約でminに着目するのは典型なので割りとあっさり解ける。そしてE、Fを読み始めたあたりでCの実装が終わり、いないちさんがBを書き始める。ふるやんさんにDの解法をチェックしてもらい、よさそうとの意見をもらう。

次にEとFにふるやんさんととりかかる。とりあえずFはアドホックな考察ゲーっぽかったのでふるやんさんに投げ、僕はEを考える。最初はどこから手を付けていいかわけわからんとか思っていたけど16文字以下の制約を見て全探索を考え始める。計算量としてもA(N) = A(N-1)+2A(N-3)みたいな漸化式になって間に合いそうみたいな気分になる。実装が大変そうだったので実装方針を詰める。横でふるやんさんがめっちゃ紙にゴリゴリ考察してて強そう。

いないちさんのBがバグったとのことでとりあえずソースを印刷して僕がDの実装に取り掛かり始める。その最中でいないちさんがバグを取れたらしく、いないちさんにバトンタッチ。サンプルが通ったらしくsubmitしACを取る。その後Dの実装に戻り若干バグらせるもAC。この時点で29位。2チーム通過を狙うならもう一問解きたい。

Fはまだ考察中らしくPCがあいていたのでEの実装にとりかかる。バグらせる気しかしなかったのでかなり集中してとりかかる。かなり大変そうとか思っていたけど取り掛かってみると意外とそこまででもなくてなんとかAC。この時点で11位になって完全にゲームクリアみたいな気分になる。するとふるやんさんがFを解けた(!)と主張し実装を始める。Gを適当に考察して適当なことを言っているうちにふるやんさんがFの実装を終え提出。ACをとり9位(!)になる。ふるやんパワーすごい。

そしてふるやんさんがGに関して右手法っぽくやればいけそうと主張し間に合わないと思いつつ実装を開始。 終了5分前になって先輩チームがざわつき始め順位表を見てみると一気に2完(!)しておりびっくりする。そしてGの実装は当然間に合わずコンテスト終了。

最終順位は10位でギリギリ一桁を逃す。

コンテスト終了後

先輩チームにハイタッチをねだりに行く。

阪大からはおそらく全チームつくば進出でめでたい。

そしてふるやんさんにFの解法を尋ねたりする。よくわからなかった。IQを感じた。

感想

今回脳をまったくつかってないのでつくばまでにはちゃんと脳を使えるようになるたいと感じた。アドホックな考察力ってどうやったらつくんですかね。

RustでUnion-Find実装してみた

atc001.contest.atcoder.jp

をRustで解いた。

コード

速度

Rustでの実装(Submission #1334290 - AtCoder Typical Contest 001 | AtCoder)とC++での実装(http://atc001.contest.atcoder.jp/submissions/1334930)を比較するとRustのほうが10倍近く遅くなっているけど書き方が悪いのかな?

どうしたら速くなるんだろう。

追記

標準入出力を速くしたらC++並みの速度になりました

Submission #2016889 - AtCoder Typical Contest 001

AOJ 2170 Marked Ancestor

問題

Marked Ancestor | Aizu Online Judge

木に対してノードをマークするというクエリと、あるノードに対してマークされた最も近い祖先を答えるというクエリに答えよ。

解法

ノードをマークするというクエリは子全体に対するmax更新クエリとみなせ、最も近い祖先を答えるクエリは子に記録されたmaxを答えるクエリとみなせる。

よってEuler Tour Technique + 遅延評価セグメント木 で殴る👊👊👊

$ O(n log{n}) $

コード