Hatena::Grouptopcoder

Hiro180の日記

 | 

2014-02-09

ARC & JOI本選(競技のみ) 22:48

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が出そう

 |