* A
人ごとに和の比較
* B
線対称
定義２について考える
* 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のへんを貼る
頂点aｋら頂点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個を求めればいい
頂点１からすべての頂点に到達できる
頂点１を根とするツリーに、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
