Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-01-21SRM459(DIV2)

SRM459 div2 第二問(500点)

| 15:32 | SRM459 div2 第二問(500点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM459 div2 第二問(500点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145

整数Xについての不等式が複数提示される。それらの条件を最も多く満たすXが存在するとき、

満たす条件の数を求める問題。

これは時間切れでした。他の人のソースコードを見ると、X を -0.5 ~ 1000.5 の範囲で動かして

同時に満たす条件の数を計算している人が多かったです。シンプルですがその発想はなかった。


僕は各条件について、取りうる X の値を限定していく手法で作ってみました。

例えば、 X >= 5 が与えられたら

X = 5 に合致条件数を 1 プラス。

X = 4 のデータが無かったら作成して合致条件数に 0 を代入。

X > 5 の範囲でデータを探し、見つかったら、合致条件数を 1 プラス。

すべての条件で処理が終わったら、持っているデータのうちで最も合致条件数が多いものを返す。

しかし、どこをどう間違えたのか特定のテストケースに合格せずに失敗しました。

これは後でやりなおします。