Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1756-c6b036c5
この記事にトラックバックする(FC2ブログユーザー)

SRM492 DIV1 参加記録 (この記事を編集する[管理者用])

2010年12月29日11時02分から.

Assignment

250-550-1000の微変則セット.

EASY

一直線上の地面にN本 (50以下) の木が立っている.木の場所と高さが与えられる.
いくつかの木を切って (高さ0にすることも可能) 木の最も高い点が全部同一直線上にあるようにしたい.
切らなければいけない最小の木の数を求める問題.

サンプル見てだいたい問題理解してから,問題を読む.
ふむふむ,思ったとおり.
で….
2本選んで,その頂点を通る線上になるようにすればいい気がする.
えー…,整数だけで計算可能だが面倒.
doubleでも多分大丈夫なはず,このぐらいなら…,きっといける!
doubleで行く.
サンプルが全然合わない.
あ,xとy逆だった.
1個合わない.
なるほど,1個だけ切らなくていい場合があるのか.
高さはマイナスにできないのでそういうこともあるのか….
1個だけ切らない場合は常に可能なのでそうする.
これでサンプル全部通るがなんか怪しいなぁ.
もっと,ちゃんとロジカルに考えてみろ!
1個だけ切らない場合は常に可能.
2個以上切らないなら,それで直線は一意に定まる.
だからこれで良い!
ってことで,良さそうだった.提出.

MEDIUM

ノード数N (50以下) の無向グラフが与えられる.枝にはコストがつけられている.
ノード番号が順番にM個 (50以下) 与えられて,その順番に訪れたい.
ただ,ブラウザの戻るボタンのように,前いたノードに戻るのは無コストで移動可能.(一度戻ると,先に進むには普通にコストが必要)
最小コストを求める問題.

うーん?
DP…だよなぁ.
多分,与えられたノード番号のある区間を部分問題として,状態数O(m^2).
で,最後に最初のノードに戻ってくる場所で場合分けして行く.
で,範囲を2つに分けて部分問題に帰着,後ろの問題は,今の場所から次の場所に移動しなきゃいけないからそのコストを足すだけ(*).
えーと,愚直に書くとO(m^3)でいける.
最初,(*)を思いつかなくて今いる場所を覚えておかないといけないかと思ったけど,O(n m^3)だと実は間に合わないとか言う罠がありそうなのでO(m^3)で書く! 550ptだし.
最後のサンプルが合わない.
サンプル見ずに理由を考える.
…,途中で寄り道してもいいよね….
どうしよう….
うーん.
やっぱり今いる場所を覚えておけばいいのでは?
O(n m^3)でいけ…ない.
どこに寄り道するかも調べないといけないから愚直に書くとO(n^2 m^3)になる….
どうやってオーダー1つ落とすのか….
わからない.
とりあえず,浮気してHARDを開くだけ開く.
問題文長かったので読まずに帰ってきてしまった.
うーん.
とりあえず,O(n^2 m^3)でいいから書いてみよう.
お,サンプルは通った.
とりあえず,ランダム最大でも作って実行時間調べてみましょう.
1.4秒…,え,間に合うの?
たしかに定数部分は小さい気がするが….
サブミット.

HARD

読んでない.

Challenge

250はdoubleでEPS使ってない人が落ちそうだったが,どうやって落とせばいいのかわからず.
550がランダム最大ケースを入れられたらしく落とされた.WAらしい.

System tests

250はdoubleだったけど通った.よかった.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1756-c6b036c5
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。