2014-02-09
■ ARC & JOI本選(競技のみ)
ARC
C:
半分全列挙。O(2^(N/2) log 2^(N/2))くらい?
B:
dp[i]=i番目の要素を最後にもつLISの長さ としてO(N)
A:
さすがに... O(sqrt(N))
D:
segment treeに差分のGCDをもたせて、求めた差分のGCDと数列のある値とのGCDを求めればよく、
数列のある値を求める時はBITをつかう。O(N log N)で解ける。
JOI本選:
1:
やるだけ。面倒
2:
上限を20000にするだけ
3:
にぶたんの中でにぶたんをするだけ。yokozuna曰くO(N)で出来るらしくやばい
4:
移動距離=m下った距離=dとすると登った距離はHn-X+(m+d)なので
総計はHn-X+2*(m+d)。Hn-Xは定数なのでm+dを最小化すれば良く、これもyokozuna曰くエッジのコストをちょっと
いじるだけで良いらしい。こわい。
5:
なにかやばいもの。年々5の難易度おかしくなってきてるしそのうちNP-Hardが出そう
