Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

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

Assignment

サマータイムが終わって午前2時開始.
250-550-950の変則セット.

EASY

50個以下の正整数列と1以上50以下の整数kが与えられる.
2つ以上同じ要素を選べず,a番目とa+k+1番目を選ぶという処理を繰り返す
選んだ数字の総和の最大値を求める問題.

うさぎセット!
うーん,思いつかない.
ある区間まで決めつけてDP?
一番左を選ばないなら1個先,選ぶなら,k個だけ全探索して,使った一番最後より後の区間を求めればよい.
….
あれ,kの上限は?
50.
どうやっても2^25通りぐらいは探索しないとダメになっちゃう…,これは無理.
うーん.
あれ,これってk個飛ばしで見てやると,独立したk+1個の問題に分割できるのでは.
分割した問題は….
要素が偶数なら全部選ぶ,奇数なら1個選べないが,両端のどちらかが選べない.
提出.
あれ,そんなこともないな….
奇数番目のどれかを使わないのであれば大丈夫なのか.
奇数番目の最小値を全部の和から引く.
再提出.

MEDIUM

k択問題がm問出題される.
連続する2問は答えの番号は等しくない.
また,10個以下の数字のペア(a,b)が与えられa問目とb問目は答えの番号が等しい.
(与えられる数字はすべて異なる)
答えはそれを満たすような数列から1つランダムに選び,自分の解答もそのような数列から1つランダムに選ぶ.
正解数の期待値を求める問題.
そのような出題パターンが存在しないなら-1を返す.

えーっと.
全問正解する確率なんて,パターンを数え上げて,その逆数なんじゃ.
てか,それって10^-9をすぐ下回って誤差誤差で通るのでは….
あれ,サンプル見ると答えが1を超えてる.
あ,正解数の期待値を求めるのか.
え,それって,どう考えてもm/kでいいんじゃないの.いいよね.
-1かどうかのみを判定する問題か.
いや,確かにこれがめんどいような気がする.
(a,b)のペアでaとbの差が1なら不可能.
そもそもk=1でmが2以上なら不可能.
k=2なら交互に配置するしかないから,(a,b)の差が奇数なら不可能.
….
取り敢えず,例外っぽい処理は書いたが,後は…?
kが3以上なら普通に配置できる気がするなぁ.
多分,できるでしょ.
ていしゅ…つの前にちょっと待てよ.
(a,c)と(a,c+1)があったら不可能じゃないか? (実際にはそう言うのはない,あれはもっと怪しいケースがいくらでも作れる)
えーっと…,適当に解決して,提出.

HARD

 F(x) = x/m (xがmの倍数)
 F(x) = x+1 (xがmの倍数でない)
でF(x)を定める.
nが与えられたとき,
 F^k(x) != 1 (k=0,1,2,...,n-1)
 F^n(x) = 1
となるようなxの数をmod 1000000009で求める問題.
nとmは10^6以下.

あれ,解けそうな気がする.DPっぽい.
取り敢えず,m進数で考えた方がわかりやすいよね.
うーん.
100000なら0が続いてる数だけ1になるまでかかる.
120221なら(m-1)+(m-2)+(m-0)+(m-2)+(m-2)+(m-1)+1だけかかる…っぽい.
120221000なら上のに+3だけかかる.
じゃあ,大体のところは,(m-各桁)の総和がn-1-kになるものに最後にk個だけ0を付ければ良い.
DPで,(m-各桁)の総和が1~n-1になる数字の種類を求めて大体それが答え.
途中までのsumも計算しておけばO(n)で計算出来る.
書く.
あれー,最後のケースだけ合わない….
うーん,うーん,とか言ってて時間切れ.

Challenge

Intermission中.
落とすのは,250で端しか考えてない人.
550で(a,c), (a,c+1)のケース.
950は…無理だろう.
550のチャレンジケース(1,5), (1,6)を作る.
入力がinvalidとか言われた.
え,それだと550点の理由は…?
k=3で反例があるんだ,きっと….
インターミッション残り3分,必死で探す.
あった….
Challenge開始.
300点以上で提出してる550をブラインド撃墜.落ちる落ちる…w
200点台のも見て,怪しそうなのを取り敢えず落とす.
250問題を眺める.
全探索っぽいのを見つけた.でかいケースを入れる.TLE.落とせた.
端しか考えてない人いた.落とす.
8成功1失敗で+375点.
ほくほく.
自分の名前が落ちてきた.550が落とされたっぽい.
と思ったら,250も550も落とされてる.なんですとーーー.
あ,i+=2と書くべきをi++と書いてる….こういうケアレスミスはいい加減無くさないと….

System tests

システムテストにかけられる価値がなかった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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