Entries

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

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

SRM508 DIV1 HARD - BarbarianInvasion2 (この記事を編集する[管理者用])

Source

TopCoder SRM508 DIV1 HARD (1000pt)
Problem Statement
SRM508 DIV1 自分の参加記録

問題概要

厳密に凸なN角形 (50以下) と,その厳密に内部の点M個 (5以下) が与えられる.
N角形の周上に,等間隔に1000000!人 (凄い沢山) の人が並んでいる.
それらの人が,内部のM箇所の点に,1000000! / M人ずつ移動する.
各人の移動スピードは1.
必要時間の最小値を求める問題.

解法

答えに対して2分探索する.
M個の点を中心とする円と,N角形の各辺との交点で分割して,それぞれの線分がどの点に移動可能かを求める.
後は,最大流を流してやり,全て対応関係が取れるかどうかを調べる.
分割された線分の数は,最大で,N*(2M+1)ぐらいになるが,どの点に移動可能かで分別したら2^Mで抑えることができる.(が,やらなくても十分大丈夫)

C++によるスパゲッティなソースコード

続きを読む

SRM508 DIV1 MEDIUM - YetAnotherORProblem / DIV2 HARD - YetAnotherORProblem2 (この記事を編集する[管理者用])

Source

TopCoder SRM508 DIV1 MEDIUM (500pt)
TopCoder SRM508 DIV2 HARD (1000pt)
Problem Statement (DIV1)
Problem Statement (DIV2)
SRM508 DIV1 自分の参加記録

問題概要

要素数Nの整数列Aが与えられる.(DIV1では,A[i]は1以上10^18以下.DIV2ではA[i]は1以上15000以下ですべての要素が同じ値)
以下の条件を満たす要素数Nの整数列Rは何通り存在するか,mod 1000000009で求める問題.
 条件1: R[i]は0以上A[i]以下
 条件2: R[0] | R[1] | … | R[N-1] = R[0] + R[1] + … + R[N-1]
(2項演算子|はビット演算のORを表す)
Nは10以下.

解法

要するに,条件2というのは,同じビットは高々1個までしか使えないだけ.
上の桁から,どの数字にビットを立てるか (それとも立てないか) で分岐していく.
後は,各要素の使える最大値は,i桁目を立てれるもので,立てなかったら2^i-1以下 (全てのビットが使用可能) になるし,
そうでなければ,元々の数字の下i-1桁,のどちらかになる.
ということで,状態数は 桁数*2^N 程度になり,DPできる.
以下は,超手抜きで,引数でそのままメモしてるが,なんとか通る.
DIV2では,上限が小さいので,今まで使ったビットでメモすることも可能.

C++によるスパゲッティなソースコード (DIV1用)

続きを読む

SRM508 DIV1 EASY/DIV2 MEDIUM - DivideAndShift (この記事を編集する[管理者用])

Source

TopCoder SRM508 DIV1 EASY (250pt)
TopCoder SRM508 DIV2 MEDIUM (500pt)
Problem Statement
SRM508 DIV1 自分の参加記録

問題概要

N個 (1000000以下) の箱が一列に並んでいる.
M番目 (N以下) の箱だけに中身が入っている.
先頭の箱のみ,(時間0で)中身を取り出すことができる.
中身を取り出すまでの最小時間を求める問題.
できる操作は以下の3種類.両方とも時間1消費する.
 操作1: 先頭の箱を最後の箱の後ろに置く
 操作2: 最後の箱を先頭の箱の前に置く
 操作3: 素数pで,現在の箱の総数(n)を割り切れるものを1つ選ぶ.箱を先頭からn/p個ずつ,p個のグループに分けて,中身が入ってる箱のグループのみ残して,他の箱を破棄する

解法

Shift操作 (操作1と操作2) と,Divide操作 (操作3) は可換.更に,Divide操作同士も可換.(全ての操作は可換)
Shift操作のみの場合の答えは,最初から数えるか最後から数えて小さいほうなので,すぐわかる.
最後にShift操作をするとして,考えうるDivide操作を全部試す.

C++によるスパゲッティなソースコード

続きを読む

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

2011年06月03日00時02分から.
[TopCoder summary]

気分転換にHARDから逆順にやってみた.
が,全部提出はできてしまうセットだったのであんまり意味なかった.

・HARD (解いた)
doubleの最大流を持ってないのは痛い.ってかこれで用意できたので良かったと思うべきか.
結構すんなりサンプル通って,そのままシステムも通ったのは良かった.時間はかかってるけど….
・MEDIUM (Failed System Test / TLE)
状態数をもうちょっとちゃんと見積もるべき.
 これって,大して状態数ないよね → map使ってvectorでそのままメモ化すれば良いや
って短絡的思考.
当然sortして状態数を減らすべきだと思ってたのに,忘れてた.sortしてたら通ってる.
提出後にsort忘れているのは気づいたが,適当に最大っぽいケースを入れて間に合うからいいや,ってなった.
最悪では間に合っていなかった.
sortして,計算量を減らさなくても,結構現実的な計算量なので,ちゃんと見積もっても厳しかったかもしれない.
・EASY (解いた)
シフトは最後にするだけでいいよな? → うん良さそう.
じゃ,割っていくのを全部試すだけだ.
と,結構すんなりと思いついたつもりで,思いつくまでに時間が結構かかってる模様.
・Challenge
EASYでsqrt(N)までしか割るのを試してない人がいたので落とす.

Appendix

Recent Articles

ブログ内検索

Ads


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