inohilog

/var/log/inohiro

日記

  • ほとんど何もできなかった
    • 当初からそのつもりだったので仕方ない
* A
人ごとに和の比較

* B
線対称
定義2について考える

* C
線対称な部分列をつくり、一番長い物
すべての部分列(2^12)
Longest Common Subsequence の真似
テーブルを作る

* D
BFS, DFS
通過点のチェック

* E
Bi の小さいものから順に特と仮定して良い
Bi < Bj な問題、i,j について、iよりjを先に溶いても両方のファーストアクセプタンスが獲得できるなら、iから溶いて良い

DP

* H
最小費用流

k個の頂点を用意
コストcの区間a,bに対応して、頂点aから頂点bへの容量t, コストcのへんを貼る
頂点akら頂点a+1に容量無限, コストoのへんを貼る

* I
-, &, ^ を使って20人文の計算
出力のkビット目は、入力のkビット目にしか依らない
- 各演算子はビットごとに独立, 合成しても同じ
XiとXj の kビット目が~ 

((x%1)|(


* G
N本の棒から6本選んで、2つの三角形を作る
週の長さを最大にしたい

a < b + c で三角形が作れる
1つ作る場合: 長い順にソート, 連続している3つを考える
2つ作る場合: 長い順にソート, 2箇所選ぶ | 2つの三角形に分ける

大きい方からABCを決める、Cより小さいものから3つ取る

* J
乱択を用いた平衡二分探索木
Treap 平衡二分探索木
優先度を挿入時にランダムで決める
- キーだけを見ると二分探索木
- 優先度を見ると二分ヒープ
-- 親よりも小さくなっている

O(N^3) 時間のDP
N^2 logN

畳込み -> FFTで計算

* K
巡回セールスマン問題
最短経路N個を求めればいい

頂点1からすべての頂点に到達できる
頂点1を根とするツリーに、500本くらい木を加えたものである

全点対最短路

* L
L番目の数字(k番目の数字)
ツリーが与えられる。各ノードに数字が決まっている
ある頂点vからwへの経路上の数字で、L番目のものを求めよ
根つきの木を作って、「頂点vより上でx以下が何個あるか」
普通のB木は毎回内容を書き換えるが、親ノードの木を部分的に再利用した木を作れば、領域O(log n)で新しく木を作れる

Purely Functional Data Structure 永続データ構造
領域 O(n log n)
時間 

Wavelet Tree 
オイラーツリーテクニック(?
Oiler Tree Technique