TopCoder SRM 543 Div1

Result

189.20 / Failed / Opened
0チャレンジ


312位 1701 -> 1724

Easy EllysXors

問題

L以上R以下の数の全てのxorを求めよ。

制約条件

L, R≦4 * 10^9

試行錯誤

この間のaizu練習会の問題に似てる。
っていうかまんま部分問題。


あの時は、数字を1桁ずつ見てくDPぽくやったんだっけ。
えーDiv1 Easyからそんなことやらなくちゃいけないんだろうか。


書きかき。
めんどい。書きながらsummary見てると、みんなガンガン提出してる。おかしい。
そこで気づく、確か4で割った余りで規則的になってたはず。


4で割った余りでやって終了。
最初に変な方針でやろうとしたせいでかなり時間浪費した。

Medium EllysRivers

問題

xy平面上に、n本の川とn+1個の陸地がある。
i番目の川の幅はwidth[i]で、n番目の陸地とn+1番目の陸地の間を流れている。
その川を渡るときのスピードは、speed[i](方向によらず一定)である。


陸地は細長く、y軸に平行な線分とみなすものとする。
線分の下側の端点のy座標は0, 上側の端点のy座標はlengthである。
陸地の、座標が整数の点には船着場がある。


(0, 0)を出発して、陸地を歩くか、船を使い、n+1番目の陸地のy座標lengthの点へ移動したい。
陸地を歩くスピードはwalkである。船の出発点と到着点は船着場である必要がある。
移動にかかる最短時間を求めよ。

制約条件

n≦50
length≦100000
speed[i]≦100000
width[i]≦100000

試行錯誤

最短路問題。
Dijkstraとか使うとEがでかいので明らかにTLE...
なんか問題の構造を上手く使えという話。


光の屈折っぽい感じなんだけど、船着場の間しか川を渡れないから、
どうみてもDP.
計算量を落とすにはどうしたら。


しばらく考える。
3分探索したらいけるんじゃ。
下に凸になるはずだし、いけそう。


書いた。
サンプル合った。
計算時間大丈夫か確認。サンプル4が0.4秒くらい。
サンプル適当に大きくする。1秒くらいか。大丈夫っぽい。


送信。

Hard

あけただけ

Challenge

部屋のほかの500を見てみる。
三分探索じゃなくて二分探索してる人がいる。
落とされてる。


あれ、てか自分の500も落とされた。一体何故。

System Test

250は通った。