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は通った。