Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年11月19日11時02分から.

Assignment

日本人(結構上位)の多い部屋.珍しい.

EASY

n人の暇人とm人の暇じゃない人がいる.(nとmはそれぞれ47以下)
毎ターンn+m人の中から異なる2人を選んで,暇にさせる.
全員が暇になるまでのターン数の期待値を求める問題.

ループのあるDPだなぁ….
250にしては重い気が.
うーん,いや,そんな事しなくても,簡単に求まるんじゃないの?
1人しか暇にさせない場合は,簡単そうで,2人でもそれの拡張ですぐ求まるような気も….
いや,やっぱりよくわからん気がする.DPしたほうが早いだろう.
書く.
答えが合わない.
なんでマイナスとか100万ぐらいとか変な数字が出てくるの….
ケアレスミス修正したらサンプル通った.
サブミット.
見直す.
あれ,この2項係数の配列,配列外にアクセスしてないか….
まぁ,サンプル通るし大丈夫だろう.

MEDIUM

文字列AとBが与えられるので,
 Aからオーバラップせずにそれぞれ空でない部分文字列A1,A2を切り出し
 Bからオーバラップせずにそれぞれ空でない部分文字列B1,B2を切り出し
A1+B1 = A2+B2になるようにしたい.
このときの,A1+B1の最長の文字列のうち,辞書順で最小のものを求める問題.
AとBの文字列の長さは47以下.

文字列の長さが短いし普通にやっても大丈夫そうだし,簡単そう.
サンプルの意味が理解出来ない.
なるほど,理解.
47までなのでO(n^5)なら大丈夫.
取り敢えず,A1とB1の切り出し方を全探索して,A2とB2をgreedyに切りだして可能かどうか判定してみる.
A1とB1を切り出すのみのプログラムで実行時間を測る.
800ms!
遅っ.
string使ってるせいだろうなぁ…,まぁ,でも,残り1200msで書けないならどっちみち無理だし気にしないことにしよう.
あれ,O(n^5)でどうやって書くんだ…?
いや,これ間に合わないんでは….
普通に取り敢えずO(n^6)で書く.
まぁ,TLEだわな….
うーん,rolling hash使えばO(n^5 log n)にはなるだろうけど….
ちょっと方針が間違ってないか?
A1とA2の最初の位置のB1とB2の最後の位置を全探索してやって,文字が一致してる限りgreedyに伸ばしていけば良いのでは.
うーん,いや,実装面倒だし….
rolling hashで取り敢えず書く.
TLE.
てか,そもそも答えが全然違う.
あー,ケアレスミスしてる.修正.
サンプル0だけ答え合わない.なんでだ.
何かがおかしい.
取り敢えず,普通に枝刈りしてみる.
全部同じ文字*2の最悪ケースは間に合うようになる.同然だけど.
あー,時間ない.
サンプル0通ってないけど,提出して誰かに50点をあげよう.
(Intermission中にバグ見つけて直したけど,結局TLEでした)

HARD

読んでない.

Challenge

適当に眺める.
EASYでmemo[50][50]とか見かけたので即座に反応して落とす.
MEDUIMはチャレンジされた.お見事.
後は落とせそうなのが見当たらなくなった時点で離脱.

System tests

EASYは通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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