Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年04月16日10時から.

Assignment

なんか普通の部屋.感想が出てこない.

EASY

生徒は最初は時刻0に部屋に行って,以下の行動を繰り返す.
 WaitTimeだけ部屋にいる.区間の両端の時間は部屋にいる.
 その後,WalkTimeだけ部屋に居ない.
教授は時間bestTimeからworstTimeまでの中で一様分布にしたがって部屋に到着する.
教授が部屋に到着した瞬間から,そのlateTime未満後までの間に生徒がいればOK.
OKじゃない確率を求める問題.

問題文読みにくいー.
まぁ,こういう意味だよね….
制限小さいので愚直に全部回せば良いでしょ!
書いてみる.サンプル.合わない.
サンプルを手計算….あれ,答え違うぞ.
OKの確率を求めてたよ.駄目な確率を求める問題だった.
それでも合わない….
何を勘違いしたのか,出歩るき始めてから,lateTime未満に教授が到着したらOKにしてた.
違うじゃん,逆じゃん.
直す.サンプル通った.
境界だけテストする.大丈夫っぽい.サブミット.160点とか.時間かけすぎorz

MEDIUM

 S(0,n) = n
 S(k,n) = S(k-1,1) + S(k-1,2) + … S(k-1,N)
なので,S(k,n) mod 1000000007を求める問題.kは50以下,nは10^9以下.

問題文単純だ,嬉しい.
DPできんし,行列冪乗か?
小さい部分を紙に書いてみる.
S(k,n) = S(k-1,n) + S(k,n-1)だなぁ.
でも,DPは無理.行列冪乗っぽくもない.
てか,これって,S(k,n)ってkを固定した時って,nについてのk+1次の多項式とかそんなんだよね? ∑i^kはk+1次式なんだから.
小さいところだけDPして,多項式の係数を連立一次方程式で求めてやればいいのでは?
書いてみる.
書いた.サンプルは合う.
ライブラリをintからlong longに書き直したので,見直しする.
大丈夫そう.サブミット.

HARD

連続するN文字中,違い種類の文字はD種類までしか含まれてはいけない.
そんな文字列の中で,seedと同じ長さで,seedより辞書順でkだけ遅い文字列を求めよ.
seedは50文字以下,使える文字の種類はアルファベット小文字26種類のみ,kは10^18以下.

もう残り30分ぐらいしか無い.
これは…,すごい面倒なDPなんじゃないの…?
今見てる,連続するN文字が,どことどこが同じ文字か,最初の文字は何文字目かを状態としてDP.
ちょっと手抜きして実装.
残り5分.
実行してみる.Abort.
残り2分.
実行してみる.答え合わない.制限時間に間に合ってない気がする.
諦めた.

Challenge

250は境界条件で落ちる人いるはず.
特に,自分が歩き始めると同時に先生が到着するとOKにしなければいけないところ! (後で気づいたけどこれサンプルにあったのね)
探す!
500が2つ落ちた.え?そっち??
500を見てみる.nが10^9なのにDPしてる人がいる.おいおい.
他の人を見る.500は単純に2項係数である.
k=0とかk=-1とか足して,首を45度傾けると二項係数に見えた.死にたい.
250に戻る.
これは…間違ってるんじゃないかな?…と思ってたら他の人に落とされた.
次,これも間違ってるよね!
テストケース入力中に他の人に落とされたorz
これは…間違ってるんじゃないかな?
落ちなかったorz
-25点.

System tests

チャレンジ失敗が大きく響いてる….
と思ったら自分の250落ちた.うわー,変数1つ書き間違えてる.ていうか,アドホックに修正したとき直し忘れたな.
やっぱりこういうアドホックな修正は良くない.
問題文ちゃんと読んで,頭の中整理して,一発で書きたい…,なかなか難しいけど.
チャレンジ失敗はどうでも良くなった.
まぁ,朝方のSRMなので,調子悪くて当然ですね…orz

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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