Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年05月12日10時02分から.
[summary]

Assignment

250-600-1000の変則セット.
怖い配点だなぁ….

EASY

N個 (50以下) の街があって,それぞれの人口が与えられている.
それぞれの街の名前は0からN-1と付けられているとする.
街が1つになるまで,2つの街を選んで合併するという操作を行う.
合併後の人口は,2つの街の人口の和で,新しい街の名前は2つの街のうち人口が多かった方を採用する.
(人口が同じだったらどっちを採用しても良い)
最終的に残る街の名前として考えうるのは何通りあるかを求める問題.

やるだけっぽい.
ある街の名前にできるかを全部判定.
それは,適当に吸収できる部分から吸収していって,全部吸収できたら終わり.
書く.
合わない.
吸収できたから,まだ吸収を続行してねフラグを立てるの忘れてた.
修正.合った.サブミット.
(しかし,なぜ,ソートしなかった…)

MEDIUM

ノード数N (50以下) で連結なグラフが与えられる.枝には距離が定義されている.
最初,ノード0にいて,順番に訪れたいノードが50個以下与えられる.
最初,車が50個以下あって,車の置いてあるノードが与えられる.
車に乗ると,どこまででも乗れるが,一度降りるとその車は消滅する.(訪れたいノードに訪れるときは降りなければ訪れたとみなされない)
歩行スピードと車スピードが与えられる.
目的地を順番に行くのにかかる最小時間を求める問題.
(距離や時間の計算は,オーバーフローの心配のないぐらいの整数演算で完結できる程度の範囲)

えっと,問題文長いな,ややこしそうだな.
読む.ふむふむ.
どうするのかわからない.車が少ないなければビットDPというか,ノードを拡大してダイクストラでいいんだろうけど.
….
各移動の際に,車を使うことでショートカットできる時間を求めておいて,それを最大化するDPなんじゃないか?
….
DPできないじゃん…,結局2^50だよ….
….
!?
最小費用流!
MEDIUMからこれがでるのか??
まぁ,良さそうだ,書いてみる.
サンプル通る.
サブミット.

HARD

スライム育成ゲームを考える.
スライムは3匹いて,それぞれの初期ステータスが与えられる.ステータスの数はN個 (150以下).
コスト1で,誰かのどれかのステータスを1だけ上昇させることができる.
ステータスの名前を1~Nまで付け替えたときに,
 全てのスライムに対して, ステータスkの値 <= ステータスk+1の値 (k = 1, 2, ..., N-1)
という条件を満たす付け替え方を存在するようにしたい.
最小コストを求める問題.
初期ステータスは各1以上10^9以下.

問題の意味が理解出来ない.
….
サンプル見てなんとなく理解.
さて,何も思いつかないが….
単に,和の小さい順から並び替えるとか,そんなんじゃダメだよなぁ….
一応書いてみる.
サンプル全部通りやがる.
適当に,作ったケースを全探索と比較する.
全然ダメでしたー.
greedyに入れ替える操作を実装する.
まだまだ全然ダメですー.
greedy系列はあんまりうまくいかない問題っぽいなぁ.
お手上げ.
なんか部屋で1人提出してる人がいるから,ランダム最大ケースでも作っておこう.
これは,ブラインド爆撃してもいいレベルだよね?

Challenge

HARDブラインド爆撃で1成功.
後は何もせず.

System tests

EASY, MEDIUM通る.
HARDは皆落ちそうだなとか思ってたけど,本当に全滅してた.おかげで良い順位.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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