Codeforces Round #367 (div. 2)
Codeforces Round #367 (div. 2)に参加した。
officialだと230位くらいでレートが下がりそうな順位だった。
A. Beru-taxi
- 問題
タクシーiが(x_i, y_i)にいて、速度v_i(1 <= i <= N)で走ることができる。(a, b)に向かってまっすぐ走ったとき、(a, b)に最も速く着くタクシーの着く時間を求めよ。
- 解法
距離/速度を計算するだけ
- 計算量
O(N)
- コード
B. Interesting drink
- 問題
N個の商品が与えられ、その値段がx_1, x_2, ..., x_Nであるとする。これに対して、Q個の金額m_1, ..., m_Qが与えられるので、各m_iで買える商品の種類数を答えよ。
- 解法
数列をソートすると、m_i で upper bound を取ったときのインデックスが答えとなる。
- 計算量
O((N+Q)logN)
- コード
C. Hard problem
- 問題
N個の文字列が与えられ、各文字列を逆順にするためのコストc_iが与えられる。幾つかの文字列を逆順にして、文字列を先頭から辞書順になるようにするとき、逆順にするコストの合計を最小化せよ。どのように逆順にしても辞書順にならない場合は-1を出力せよ。
- 制約
2 <= N <= 10^5
0 <= c_i <= 10^9
文字列の長さの合計 <= 10^5
- 解法
DP。dp[i][j] := (i-1番目までを辞書順にして、i番目が(j=0→逆順にしない/j=1→逆順にする)場合の最小のコスト)とおくと、
dp[i+1][0] = min(dp[i][0], dp[i][1]) (if (i番目の文字列) < (i+1の文字列) かつ (i番目の逆順の文字列) < (i+1番目の文字列))
dp[i+1][1] = min(dp[i][0], dp[i][1]) + 逆順にするコスト (if (i番目の文字列) < (i+1の逆順の文字列) かつ (i番目の逆順の文字列) < (i+1番目の逆順の文字列))
とする(片方しか逆順になっていない場合はそちらだけで更新する。詳しくはコードを参照)
- 計算量
O(N+sum(文字列の長さ))
- コード
D. Vasiliy's Multiset
- 問題
初め、multisetには0が1つ入っている。これに対して、1. xをmultisetに追加する、2. xをmultisetから削除する、3. xとmultisetの要素yの中で、x^yが最大になるものを出力する、という3種類のクエリがQ個与えられるので処理せよ。
- 解法
xとXORを取ったときに、上位bitを立てるようなものがmultisetに入っている場合は、下位ビットがどうなろうとそれを取った方がいいということが分かる。
よって、上位からビットを立てるか決めていく二分探索を行う。
0. left = 0, right = INFとする
1. for i in 30 to 0 do
1.1 multisetに対して、mid=left + 2^iのlower boundを求める
1.2 xのiビットが0の場合、mid以上の値がmultisetにある場合は、iビット目を立てることができるので、left = midとする。もしない場合は、right = midとする。
1.3 xのiビットが1の場合、midより小さくなる値がmultisetにある場合は、iビット目を立てることができるので、right = midとする。もしない場合はleft = midとする。
2 答えをx xor leftとする
- 制約
1 <= Q <= 2×10^5
1 <= x <= 10^9
- 計算量
O(QlogQlogx)
- コード
感想
Dはもっと複雑なことをしないといけないと思って詰まっていたのがダメだった。
想定解はTrieを使うらしい。