Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年05月18日00時02分から.
[summary]

Assignment

SRM504がサーバ不調でノーコンテストになったので,その補填コンテスト.
日本人2名ぐらいと同じ部屋.
250-550-900と不穏な点数の問題セット.

EASY

下1桁が4または7の正整数をラッキーな数字という.
N (1以上10^9以下) をラッキーな数字の和で書くとき,最小でいくつのラッキーな数字の和で書くことができるかを求める問題.

簡単そう.
10の倍数を加えることがいくらでもできるので,小さい範囲で求めれれば良さそう.
4と7しか使えないとして,1000までDPで求める.
後は,Nを10引きながら,DP[N],DP[N-10],DP[N-20],・・・の最小値が答えでいいよね.
しかし,もしかしたら間に合うかもしれないけど,10引いていくと1億回計算するので・・・.
Nが1000以上なら1000引いていって,残りから10引いていくようにしよう.
書いた書いた.
サンプル通過したけど,色々自信なかったので,テストする.
1013の時,-1になる…,1000引いて13をチェックしてるから…,駄目じゃん.
てか,それでいいならmod 1000とればいいので,1000引いていくのは,それじゃダメだからそうしたんだろ!
2000以上のとき1000引いていってください….
修正.
もうちょっといろいろテスト.
最大ケースで間に合うよな?
N=1000000000のとき,答え0….は?
ああああ,N=0なら0個の和とか頭悪いことしてるのか.
修正.
もう大丈夫そうなのでサブミット.

MEDIUM

N人 (47以下) の所持金 (それぞれ10^18以下) が与えられる.
自分の所持金M (10^18)も与えられる.
以下の操作を自分の所持金が尽きるまで繰り返したとき,N人の所持金をソートして返す問題.
 現在のN人の所持金の平均値より大きい最小の整数をZとする
 N人の中で最も所持金の少ない人が,所持金Zになるか,自分の所持金が尽きるまで渡す

さて,550だし,ゆっくりでもいいから確実に解くぞ.
やっぱり,全然方針がわからん.
…,が,これ,別にシミュレーションしても大丈夫な気もするが….
そんなわけないよな.
まぁ,答え検証器にもなるし,とりあえずシミュレーション書く.
その前に,なんで,入力足すだけでlong longでオーバーフローするんだよ….
単なる嫌がらせ以外の何者でもないがな…,でもこういう子どもっぽい引っ掛けもTopCoder.
…,いや,でも,なんか,どうやって書けばいいんだ?
big integer貼り付けるか…?
と思ったけど,あまりにもあんまりなんで思いとどまる.
 div += in[i] / n
 mod += in[i] % n
で最後に
 div += mod / n
とかしてみた.
後は,シミュレーション書くだけ.
で,流石に,全員の所持金が等しくなったら,一気にスキップさせる.
書いた.
さて,最悪ケースではTLEするよな?
これが最悪かな…というのを探る….
….
……….
全部間に合うな….最悪でも300msぐらい.
取り敢えず提出….
いろいろテストする….大丈夫っぽいんだが….
HARDいこ….

HARD

N人 (1000以下) が一列に並んでいて,自分は先頭からM番目にいる.
以下の操作によって,1人を選ぶとき,自分が選ばれる確率を求める問題.
 列に1人しかいなければ,その人を選ぶ.
 そうでなければ,サイコロを振って,
  4がでれば,先頭の人を選んで終了
  2か6がでれば,先頭の人は選ばれなかったとして,権利をなくす
  1か3か5がでれば,先頭の人は一番後ろに並びなおす

何人かに瞬殺されてる.900だから多少簡単なんだろうけど….
問題読む.
へ,すごい簡単なんじゃ?
えっと,N,MでDP…すると,O(N^3)になりそうな気もするな.(うまくやればO(N^2)でできるしこっちのほうが楽だった)
えっと,えっと,自分が先頭にいて,合計N人いるときの選ばれる確率でDPすればO(N^2)でいけるよな.
コンビネーションとか色々計算するとき,doubleでもオーバーフローするよな.
(師匠が,GCJ 2011 予選のD問題でコンビネーション計算してオーバーフローして落ちてたので間違いない)
ってことで,全部log取って計算して,最後にexpかまして戻す.
めんどくさい….
書いた.合わない.
えー.
添字が1ズレてるとか,色々やらかしてた.修正するのに時間かかった.
サンプルあって,N=1000も問題なく動いているように見えたので提出.遅いorz

Challenge

MEDIUMはオーバーフローしてたり,怪しいことしてる人とか,色々いそう.
HARDもコンビネーション計算してオーバーフローしてる人がいそう.
EASYは…,これはまあ,みんな大丈夫だろう.
まぁ,HARDから見ていくかな.
…,開始!
誰もコンビネーションとか使ってねぇ!
てか,皆コード短いな,何やってるんだ….
と思ってるうちに,EASYとかMEDIUMがぞくぞく落ちていく.
へ,てか,なんでEASY落ちてるの??
見ても分からん.てか,4使う回数と7使う回数でループしてる人賢すぎる.
MEDIUMを見ていく.
long longのオーバーフローとかは粗方落とされてて,みんな良さそうに見える.
あ,これ,long longで和計算してるからオーバーフローするんじゃない?
落とせた.
(実は,後で確認するとlong doubleで計算していたけど,最大近くのランダムケースいれたので落ちた)
(10^18を47とかの最大ケースだと落ちなかったらしい,怖い怖い…)
後は,見てるだけしかできなかった.

System tests

全部通った.
250のチャレンジポイントは下1桁が0のとき,0を返す人がいたという物.
てか,自分も1回それに嵌ってテストケース色々試して気づいたのだから,それを他の人がやることだって十分あることを理解しろ!
900はO(N^2)のDPでももっと賢い方法あるし,O(N^2)を100回ぐらいループ回してガウスザイデルっぽくやるだけでも通ったらしい.
いくらなんでも簡単すぎるセットな気がするけど,補填コンテストなのでしょうがないのかなぁ?
ちなみに,550のlong longのオーバーフローは,あまりにもくだらない引っ掛けで,皆怒り心頭してたけど,個人的には嫌いじゃない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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