読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #367 (Div. 2)

Codeforces Trie

最後の問題が解けなかったのは残念。

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) で張り替えられる。

原理は簡単だが実装がやや面倒。

最近ジャッジが重すぎる気がする。