Codeforces Round #367 (Div. 2)
最後の問題が解けなかったのは残念。
A. Beru-taxi
http://codeforces.com/problemset/problem/706/A
hypot(x[i]-a, y[i]-b)/v[i] の最小値を求めればいい。出力桁数や min の初期値ミスに注意。
B. Interesting drink
http://codeforces.com/problemset/problem/706/B
m[i] 以下の要素の個数が求めたい。これは累積和や二分探索(upper_bound)が使える。
累積和を使う場合は m[i] が 109 なので配列外参照に注意。
C. Hard problem
http://codeforces.com/problemset/problem/706/C
- dp[ i 番目までソート済み ][ i 番目が反転してるか ] := この状態に至る最小のコスト
ありうるミスとしては次のようなものだろうか。
- 遷移時の大小判定に等号を含めない
- INF が小さい
c[i]≦109 なので 109*105 より大きい値を INF を設定しておくとよい。
D. Vasily's Multiset
http://codeforces.com/problemset/problem/706/D
上位ビットになるべく 1 が立つようにすれば、それが最大値になる。たとえば x=10010 だったら、y=1**** よりは y=0**** と xor を取った方が大きくなる。
上から順にビットを決めていこうとすると、接頭辞が P であるようなものの存在を判定したくなる。これは trie を使って O(Q log x) でできる。
E. Working routine
http://codeforces.com/problemset/problem/706/E
連結リストを使って行列を管理すると O((n+m)q) で解ける。連結リストに左・右・下のリンクを持たせればいい。
(a,b),(a,b+w),(c,d),(c,d+w) のノードを一回求めれば、その下のノードは下へのリンクを辿って取得できるため O(h+w) で横方向のリンクは張り替えられる。
横方向だけでなく縦方向のリンクも張り替える必要がある。a-1,c-1,a+H-1,b+H-1 行目以外のリンクは変化しないので O(w) で張り替えられる。
原理は簡単だが実装がやや面倒。