Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年07月06日20時02分から.

Assignment

topcoder.comに繋がらないせいで,なかなかアリーナに入れない.
10分以上遅れたら参加しない,と思ってずっとアタックしてたら,5分遅れぐらいで入れた.
なので,参加.
300-600-900の変則セット.

EASY

最初,17マス以下のセルが直線上にある.
ランダムにウサギが,r匹いる.
端のウサギは真ん中よりに,W色のセルにいるウサギは右へ,B色のセルにいるウサギは左へ,R色のセルにいるウサギは前いたセルに戻る(最初だったら左へ行く).
同じマスに2匹の兎が集まると居なくなる.
毎ターン,右端のマス目が消える.
残り2マスになったとき,うさぎの残りの数の期待値を求める問題.
細かい条件は問題文参照.

うさぎだ,hosさんっぽい….
17ってことは,300点だし,簡単めなビットDPなのかな?
問題読む.
全初期パターンを列挙して,シミュレーションじゃない?
やるだけだ…,めんどうだから300点か.
書く.
書いた.
サンプル通った.
サイズ17でも,時間は間に合う,問題なさそう.
サブミット.

MEDIUM

ウサギのカップルは,生まれて2年目から,1つのカップルを生成し続ける.
k (kは10000000以下) 年目のうさぎのカップルの数を mod 1000000009 で求める問題.
ただし,50個以下の年が与えられて,その時に,カップルの数を半分どこかに移動させて居なくなる.
半分というのは,古いウサギから優先的に選ばれて,奇数なら,切り上げで移動させるカップルの方が多い.

kは大きいから,フィボナッチ数で,行列べき乗.
を,50個ぐらいの区間に分割して,逐次やって,半分減らせば良い.
かきかき.
あれ,半分減らすのは…?
若いウサギが減らされることはあるのか?
ない,常に年寄りのウサギの方が数が多い.
嘘だ!1年目だけ違う.これはコーナーケース….
いや,それより問題なのは,奇数かどうかで,1足して2で割るか,そのまま2で割るか変わること.
mod 1000000009で計算してたら,わからないじゃないか….
どうするんだ?
mod 2も一緒に計算しておく.
mod 2000000018で計算すればいいか….
いや,2回目以降困る.
mod 2で計算してた方が,移動させるカップル数を引いた後,奇数か偶数かわからなくなる.
むむむ….
mod 2^50を計算しておけばいいのか?
いや,それって,行列で計算するとき,掛け算が計算できない,long longでもオーバーフローするじゃないか….
えええ?
どうするんだ….
64bit * 64bit mod 64bitのライブラリをコピペして,無理やりやる.
書いた.サンプル通った.
サブミット.

HARD

コンテストの問題の配点と,各問題がシステムテストが終わったかどうかの情報が与えられる.
 システムテストが終わった問題に関しては,正解者のリスト,
 システムテストが終わってない問題に関しては,提出者のリスト(正解かどうか不明)
が与えられる.
参加者中,上位n人の中から,m人選んでチームをつくる場合,作れる可能性のあるチームの数をmod いくらかで求める問題.
問題数は50以下,参加者数は50以下,各問題の点数は100000以下.
同点の場合は,番号の若い参加者の方が順位が高いとみなす.

残り10分しかないので,解けないだろうけど問題だけ読む.
うーん,よく分からないけど,組み合わせの数を絡めたDPなのかなぁ?

Challenge

600で1年目に減らすコーナーケースを…叩くつもりで…,部屋で提出してるのが自分だけ.
900も提出してるの1人だけ….
300は落ちないだろう….
ってことで,見てるだけ.
やたらと,自分の600がチャレンジされる,なんでだ?
他の部屋の人の600の解答を見に行く.
kだけループ回してる,それTLEだろ…,でもなんでチャレンジされてないの?
kの上限小さい!間に合うのか!
あれ…,それだと,600点問題ってもっと簡単じゃないの…?orz
てか,そもそも,mod 2^50とかって頑張らなくてもオーバーフローに任せておけば計算できたんじゃ….
色々泣きたい.

System tests

EASYとMEDIUM通る.
Rateは相変わらず自己ベストに漸近中.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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