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 & …

Fractional Cascading について

日本語で書かれた記事が見つからなかったのでざっくり書く 問題 vを二次元配列として、ソート済みの各配列v[i]に対してlower_boundを求めるクエリを処理する。 アルゴリズム 愚直に二分探索したら配列数をkとしてO(klog(n))となる。Fractional Cascading を…

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と比較するとわかる…

AOJ 1604 デッドロック検出

問題 Deadlock Detection | Aizu Online Judge 解法 dp[今、各スレッドでロックしている資源をあわせたものの集合] = (次にどれかのスレッドが確保する可能性のある資源の集合の集合) みたいにする。 そして最終的に $ \exists S, \exists e \in dp[S], e \s…

ICPC 2017 国内予選 参加記

チームnasubidenamidaでふるやん(@furuya1223)さんといないち(@37dbye)さんと出た。10位を取れた。 ふるやんさんの参加記はこちら。 www.creativ.xyz コンテスト前 ゼミを早退してコンテスト会場に来て準備をする。模擬予選から特になにもしておらずほげ。 …

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倍近く遅くなってい…

AOJ 2170 Marked Ancestor

問題 Marked Ancestor | Aizu Online Judge 木に対してノードをマークするというクエリと、あるノードに対してマークされた最も近い祖先を答えるというクエリに答えよ。 解法 ノードをマークするというクエリは子全体に対するmax更新クエリとみなせ、最も近…

SRM610 Div2 Hard MiningGoldEasy

問題 TopCoder Statistics - Problem Statement 解法 xとyを独立に考える。 任意の動き方に対してx,yのそれぞれに対して座標の変化が起こらないような区間を考える。 すると関数 は のうちのどれかを最小値としてとるような凸関数であるので、 event_i、even…

Codeforces Round 381 Div2 D Alyona and a tree

ダブリングでそれぞれの頂点がどこまで支配されるのかを求めた後、各頂点に+1, -1を記録し木上でimos法みたいなことをします。 O(Nlog(n)) gist2622f3016f0d316048b64712fa3894dc 500msくらいかかっていて結構遅い

はじめに

プログラミングとかについて書くかもしれません