今回で最後のPSet。 問題はこちら 意訳が間違っていたらご指摘ください。 7-1 DPを実装する問題。漸化式が与えられているので境界条件に注意してコードする。 また、遷移した親のアドレスも保持する必要がある。 7-2 会社の株価の過去データが与えられている…

問題はこちら 意訳が間違っていたらご指摘ください。 6-1 Renbookという架空の(Facebookのパクリ)webサイトの友達ランク計算の話。 ]はuがvに興味を持った度合いを表す。 ユーザ同士の関係は有向グラフによって表される。友達同士はエッジで結ばれている。 …

CS6.006で習ったことだし、DPに強くなりたい。 問題は以下。 atcoder.jp 状態遷移図を書く。 遷移図 一つのノードから分岐する全てのノードを網羅できるようなサブ問題を考える。 ここでは、根ノードとそこからわかれる二つのノードを網羅する例を考えている…

わかったこと 文字列系のDPでよく使われるsub-problem prefix suffix substring 当然といわれれば当然。prefixとsuffixをどちらも使いそうな時はつまりsubstringである。 pseudo polynomial ナップザック問題： ナップザックに、重さ、価値の品物を入れるか…

ふと、まとまった時間でアルゴリズムを学び直したいと思った。 いつ転職しても(させられても)いいように。 MITのCS 6.006という講座がある。2011年の秋学期にMITで行われたアルゴリズムの授業であり、ほぼ全てのリソースが無料で公開されている。 G社に内定…

問題はこちら 意訳が間違っていたらご指摘ください。 フォーマットの説明 問題文 思考方法→答え の順で書いています。 Problem 5-1 base = 256、つまり256進数で表された整数の計算をするプログラムについて。 base = 256なので、我々が普段使う10種類の0-9…

問題はこちら 意訳が間違っていたらご指摘ください。 大問1 (a) 文字列の文字コードの和(のmod)をハッシュ値として使った場合、を達成できるか？ 1. Yes, 文字列の長さに基づいて均等にハッシュ値がばらける 2. Yes, 文字列中の文字に基づいて均等にハッシュ…

わかったこと Multiplicationの時間計算量 桁どうしの掛け算を行うときの時間計算量は、 で与えられる。 naiveなアルゴリズム: Karatsuba: DivisionはNewton Method + Multiplicationによって行われる を求めたいとき、と考え、 を先に求める。 を求めたいと…

表記: n: テーブルに入っている要素のサイズ m: テーブルのサイズ とする。 わかったこと Table Shrinkingでは、縮めるタイミングとサイズの係数をずらすのが良い テーブルの要素の追加・削除を繰り返し、n = m/2となったタイミングでテーブルを縮めるとする…

わかったこと ディクショナリはハッシュ表、Binary Search Treeの上位概念 Pythonでお馴染みのディクショナリ。 ディクショナリは insert delete search を行うもので、具体的な実装方法としてハッシュ表、Binary Search Treeがある。 ディクショナリとハッ…

トピック Insertion Sort Merge Sort Heap Sort Counting Sort Radix Sort わかったこと Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でもの計算量がかかる。 理由 最低かかる計算量は、決定木…

問題はこちら 今回は大問2のコーディングの部分のみ。 時間あったら大問1のrecursion treeの話も追記します。 Pythonプロファイラを使ってボトルネックを特定する問題。プロファイラを使う点で実用的。 プライオリティキューが実装されていて、最小値をとっ…

ISUCON8のPythonプログラムで、 db.autocommit(false)なる行が何をしているのか調べる。 コミット？トランザクション？よくわからない言葉がでてくる。 トランザクションについてはzd6ir7さんのQiita記事がわかりやすかった。 トランザクション 「複数の処理…