Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年01月23日02時02分から.

Assignment

250-500-1000の標準的なセットで,標準的な部屋.

EASY

50*50ピクセル以下の白黒画像が与えられる.
最初真っ白な画像で,好きな回数だけn*nの正方形領域を黒くできる.その時,黒い場所は黒いまま.
与えられた白黒画像を作れるような最大のnを求める問題.

実際に塗るだけ…ではなかろうか.
全ての,n*nが黒い場所を実際に塗ってみて,もともとの画像が復元出来てるかで,nで可能かどうかは判定できる.
後は全てのnについて判定すれば良い.
書こう.
…,あれ,計算量全然大したことないと思ってたけど,これって実はO(50^5)じゃないか?
いや,まぁいい,間に合うはず.
書いた.
一応最悪ケースを試す.100ms未満.余裕すぎる…,こんなに速いのか.
サブミット.

MEDIUM

n本 (50以下) の木の高さの分布が与えられる.
それぞれの分布はa[k]以上b[k]以下 (a[k], b[k]は100000以下) の整数を等確率に取るような分布.
木の高さが与えられたとき,以下でスコアを定める.そのスコアの期待値を求める問題.
 Alternatingとは,木の高さAが順番に大きくなって小さくなって (または,小さくなって大きくなって) となること,つまり
  A[0] > A[1] < A[2] > A[3] < … または A[0] < A[1] > A[2] < A[3] > …
 Alternatingな木の高さに関しては,スコアは隣合う木の高さの差の絶対値を足した物,つまり
  |A[0]-A[1]| + |A[1]-A[2]| + |A[2]-A[3]| + …
 Alternatingじゃない木の高さに関しては,好きな数だけ木を無視して,Alternatingな木の高さにしたときのスコアの最大値

えっと….DPっぽいが….
うん,木の高さの上限も100000だし,前の木の高さを覚えてDPすれば良さそう.
工夫せずにDPすると,1回の更新で100000^2掛かるけど,途中までの和を計算してうまく使えば100000になるはず.
で,Alternatingじゃないとダメだから….
 dp[今何本目][今増えてるか減ってるか][前の木の高さ]
とかでやればOK.
いや,期待値だから…,それぞれの状態を達成する組み合わせの数も覚えて正規化が必要….
いや,一様分布だからいらないか.
ちょっと書き始める.
…,ってか,凄いめんどいぞ?
うがーー,書き書き.
いや,まてよ,ちょっと手を止めて冷静になれ.
木を切るのって,絶対に極値の木を残せば良いんだよね?
もうちょっと言えば,別に木を切らなくても,隣り合う木の高さの絶対値の差を足していくだけだよね?
…,そうっぽい.いや,絶対そう.
この罠はなんだ…,今増えてるか減ってるかの状態要らない.少し楽になる!
….
ちょっとじゃなくて,もっともっと待て.
それだったら…,期待値だから….
隣り合う木の高さの差の期待値を別々に求めて足すだけ….
なんだそれはー!
一旦ソースコードを全消し.書きなおす.
でも,愚直にやると100000^2で死ぬ.
でも,どうとでもなるよね.
和の公式使えばいい…,が場合分けがちょっと面倒じゃない? もっといい方法ない?
うまい方法思いつかないが,差がkになるパターン数を数え上げてみよう.
おっと,これ,long longにしないとオーバーフローするな…,チャレンジケースに覚えておこう.
サンプルあった.提出!

HARD

N*M (150*150以下) のグリッドの各マスにスイッチがある.最初はスイッチは全部オフ.
あるマスを選んでスイッチを反転させると,同時に,そのマスからチェスのナイトで1回で移動できるマスのスイッチが全部反転する.
たかだか各マスを選ぶ回数は1回までという制約を課したとき,全てのスイッチをオンにする方法は何通りあるかをmod 123456789で求める問題.
スイッチを選ぶ順番だけ入れ替えたものは同じものとみなす.

うーん,全くわからない.

サンプル見ると実は答えは2の冪じゃないかと予想.
77502052ってのが2^x mod 123456789かどうか確かめてみる.
2の冪だ!
だから…?
なにか法則でもないかな….
小さいケースで総当たりしてみよう.
….
nを固定したとき,フラクタルっぽい構造が見え隠れするがよくわからない….
時間切れ.

Challenge

500のオーバーフローする + 中盤以降ランダム最大のテストケースを作って待機してた.
500のオーバーフロー狙いと行く.
いきなり,100000^2っぽいコードを見つけたので,まあ,これは落としておく.
案の定,オーバーフロー1人いたー,落とす!

System tests

250,500通る.
500が遅めだったけど,2チャレンジ成功のおかげで良い順位だった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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