Hatena::Grouptopcoder

ir5は引退した

 | 

2010-08-14

SRM 479

02:20

ふつうの回.

DivLevelProblemNameStatus
1250TheCofeeTimeDivOnePassed System Test
1500TheAirTripDivOnePassed System Test
11000開けてないUnopened

250

  • 問題文長いし読むのが苦行.
    • サンプル先読みしたりしたけどよくわかんなかったので素直に前から読んだ
  • 飛行機のシートが1~Nまで並んでいて,スチュワーデスがそれぞれの客にteaかcoffeeのどちらかを与える.与えるのにそれぞれコストがあるので,そのコストを最小化せよ,というもの.
    • Nは5000万以下.おいおい,飛行機どんだけ長いんだよ.よく知らんけど戦艦大和みたいなもんなのかな.
  • ちょっと考える
    • 最小化といっても,順番は割と適当でいいのでは…? とりあえず前から試していく方針でやってみよう
  • 書く.
  • 実装が結構面倒くさい…
    • 本当にもうシミュレーションみたいな感じで実装した.O(N)だから微妙かもだけどまぁたぶん間に合うだろう….

  • サンプルが微妙に合わない.
  • 実際に図を書いてみる.おわ,これ後ろからじゃないとだめじゃん….
  • 書き直す.サンプル通る.
    • 適当に自分ででかいやつも作る.あっているのかは分からないが少なくとも普通に間に合う.

  • なんかサンプルが弱そうで怖い….コーナーケースは一通りありそうに見えなくもないけど.
  • でもテスト作って確かめるのも難しいので,あきらめて提出した.ここまで20分くらいだったろうか.

500

  • こっちも問題文長くてウボァー.
  • グラフらしい.ひょえー.飛行機の飛び方が結構複雑というかそのまんまやるとサイズでかすぎるので,何か工夫がいるのだろう.
  • どうやらsafetyなる値を最大化させたいらしい.
    • んー,2分探索+なんか とかでいいのでは.
    • なんかってなんだ.
    • DP? いや違う,状態数が多すぎる.
    • safetyを固定した場合,他の空港にはできるだけ早く着いたほうがよいはず.早めに着てしまっても待てば良いだけなわけだし.
    • ならダイクストラをしてやればよいか.
  • 基本方針はすぐに分かった.書く.

  • なんか全然合わない….
  • コードを上から見てやるが,どこがおかしいのかよく分からない.
  • 1つ目の簡単なやつですら通らないので,実際にサンプルを書き下してみる.
  • なんか +safety するところがまずいっぽい.
    • 次のノードが目的地でないなら+safetyした時間を次の状態にすればいいが,次のノードが目的地なら+safetyする必要はない.
  • 修正.ここでも結構手間取ってしまう.サンプル全部合った.
  • 大きいのはよく分からないし,本当に簡単なやつだけ試す.まぁいいんじゃないかな… 提出.ここまで65分くらい.

Intermission

  • テストのしにくい問題が多かったので特に何もしなかった.
  • でも何もしないのもよくないので500のテストをする.あれ… n=2のときの挙動がなんかまずい… 1->2の直行便があるときにsafetyがへんな値になる.これはまずい…
  • あれ,でも直行便があるときってsafetyが定義されないんでは? 問題文よく読む.直行便はないらしい.よかった安心.

Challenge Phase

  • 皆様思い思いの方法で実装してらっしゃる
  • よく分からんなーと思って眺めてたら終わった

結果

不安だったけど両方通った.やった.


o o x 407.92 53位/722

1889->2010


ついに2000台の世界に.ここから転落しないようにしたいけどやっぱ怖いなぁ….とりあえず毎回2問解けなくてもいいから正のスコアを取ることを目標にごにょごにょしたい.

 |