SRM479
密かにバースデーSRMだったので、妙な緊張感と戦う羽目に。
- -
250. TheCoffeeTimeDivOne
問題:乗客のお茶orコーヒーのオーダーを全て消化するための最短時間を求める。
- 貪欲に後ろから配れば良いんだろうなぁ…と思いつつ,貪欲でやる勇気が出ない。
- 貪欲に対するダメっぷりは今なお健在
- 他に思いつかないし、良さそうな気がしたので貪欲でやる事に。
- 客の数が最大44777777だったので、迷いつつO(n)で素直に実装してみた。
- 最大ケースでも大丈夫そうだったので提出した。
- さすがに通った。ちょっと安心。
500. TheAirTripDivOne
問題:飛行機を乗りついで空港1から空港nまで移動する。時間timeまでに到着するように経路を選ぶとき、乗り継ぎ時間の最小値が最大になるような経路は?
- 何故か最短経路の中で乗り継ぎ時間を最大化すると読み違える。
- え…普通に幅優先すれば良くね…?⇒当然だけど合わない
- そういえばtimeとかいう引数を使ってない…。
- あ、時間timeまでに目的地に着く経路を考えるのか。
- ※ここで今度は乗り継ぎ時間の和を最大化だと勘違い
- 乗り継ぎ時間の和の最大化ってどうするんだろう…。
- timeまでに目的地に着く経路とか無数にありそうだけど…。
- と、悩んでたら終わってしまいました。
- -
結果:AC / -- / -- ,199.52pt, 135位
レーティング:2076 -> 2099
得意分野のハズのグラフが解けなかったので不完全燃焼に終わりました。
意味を正しく取っていれば決して難しい問題では無かったようですが…。
あの場で、冷静にサンプルの内容でも見ておけば気付いたのだろうと思います。
この辺の慌てぶりの克服は、この一年も課題になりそうです。