TopCoder SRM 478 (Div 1) - simezi

予感の通りrngセット。相変わらず問題むずすぎるお。
そしてsky先生と同室。赤おめでとうございます。

189.69 / Opened / Unopened
0チャレンジ

183位
1841->1868

何でこれでレート上がるのー……

数直線上にいるウサギが、初期位置initからジャンプを繰り返してゴールまで行く。
このとき必要なジャンプの最小回数を求めよ。
100000回以下のジャンプでゴールへ到達するのが不可能な場合-1を返せ。

ただし、

えーなにこれ……250の難易度じゃねえ……
まず全探索の解法は明らかに間に合わなさそう。

という訳で上手い解法を探す。けれど思い浮かばない。

と言うかとっかかりすら見つからず、どんどん時間が過ぎる。
rng回はいつもこうだ……

全探索でも書いたら何か規則性見えたりするのか？
サンプル見てもそんなことはなさそうなんだけど……

書いた。やっぱ最後のサンプルが手許で3秒くらいかかるなー。
一応サーバ上でもテストしてみるか。
ん！？0.3秒で終わる？
もしかして全探索で間に合うのかこれ。

適当に数入れてみるが全部最悪0.3秒くらいで終わる。なんで？？？
とりあえず送信。

容量Cのボトルに、それぞれbottle[i]のジュースが入っている。
以下の操作を0回以上任意に行い、ジュースを売るときの、最大の利益を求めよ。
ただし、xリットルのジュースの入ったボトルはprice[x]で売れる。

操作:
好きな2本の相違なるボトルA,Bを選び、Aが満タンかBが空になるまでBのジュースをAに注ぐ。

C≦50,
ボトルの本数≦15を満たす。

うーまた方針の立たない問題。
DP？フロー？
なんか個数からしてビットDPっぽい感じはするんだけど……
でも容量Cが小さいってのは何故なんだぜ。

とりあえず、操作を繰り返す度に満タンまたは空のボトルの本数は増えていく。
そして、全てのボトルの容量はCで等しいから、A,Bのどちらかが満タンor空になるようなボトルの選び方は意味がない。

んでんで……どうすればいいの……

わかんない。メモ化して全探索のプログラムを書いてみる。
最大っぽいサンプルでTLEする。ていうかサンプル親切すぎだろー。
これまともにchallengeできるのかなあ。

全く方針の糸口が見えずに終了。

なんか速攻で一人青い人の250が落とされた。
色々見てみる。落とせそうなのがない。部屋にも後は動きがない。
みんなの250は2の累乗使ったり3で割ったりしてる謎いコードすぎて正しいのかわからない……

終了。

通った。というか部屋のテストは全部通ってる。