TopCoder SRM 667 Div2

結果

• 237.94点 (oxx Challange: 0)
• Rating: 1000 -> 1035
• 部屋6位 / 全体156位

Rating上がったひょーい！！

250点問題 - Point Distance

問題概要

二次元上に点A,Bがある(A != B)。以下の条件を満たすCを答えよ。

• CはAともBとも異なる
• C (x,y) とすると -100 <= x,y <= 100
• AC > AB

Cが複数ある場合はそのうちの1つを答えれば良い。 また、Cは必ず存在する

• -50 <= A,Bのx,y <= 50

解答

全探索し237.94点

500点問題

問題概要

mの長さの命令がn個与えられる

例:

100
111
001

0, 1, .., m-1 のアドレスが付いたメモリがある。

100 なら 0 番目のメモリを使用する命令である。 111 なら、0,1,2番目のメモリを使用する命令である。

命令でメモリを使用する場合、その命令で初めて利用するメモリの数をkとすると k² の時間がかかる。 例えば、100 111 001 の順番で命令を実行すると、

• 100 は、0番目のメモリを初めて使うので、実行時間は1
• 111 は、1番目と2番目のメモリを初めて使うので、実行時間は4
• 001 は、全てメモリが使用済みなので実行時間は0

となり実行時間は5となる。

一方で、100 001 111 と実行した場合は、実行時間が3となる。

与えられた命令を、最も実行時間が短くなるように最適な順番で実行した場合、その実行時間を答えよ

という問題のはず…

解法

各命令で、新しく使われるメモリの数を調べて、それが最も少ないものを実行していく… でできると思ったが System test で落ちた。 てか部屋の人全員落ちてた。 何か間違っていたのかしら？要復習。

1000点問題

問題概要

m階建てのビルがn個ある。 このビルに店を出したい。 店はm店舗まで出せる。ただし、同じビルの同じ階には同時に1店舗までしか出せない。

関数P(x,y)が与えられる。 ある店に対して、その店があるビルをxとし、 そのビル、または、そのビルに隣接するビルにある店舗の合計をyとすると、 店の価値はP(x,y)で与えられる。 このPは、yが増えると単調減少する関数である。 全ての店の価値の合計が収益となる。収益が最大になるように店を出した場合の、収益の値を求めよ。

解法

わからん。気になる。

反省

• 12時スタートだったので眠かった
• 眠すぎたので最後30分とChallange Phaseはなにもしてなかった