TopCoder SRM 481 (Div 1)

焦りすぎて実力出し切れなかった感。

Result

122.26 / 218.78 / Unopened
1撃墜3ミス
117位
1936->1981

Easy ChickenOracle

赤2人の部屋。最近赤数人の部屋が多くなってきた気がする。
部屋の割り当てってどういう仕組みなんだろ。


今回は250-500-900セットらしい。どうせHard開ける時間はなさそうだけど。

問題

「卵が先か、鶏が先か」という問に対し、oracleがn人に答えを教えた。その答えを聞いて回るとeggCount人が「卵が先と言われた」と答えた。


だが、oracleは丁度lieCount回は嘘の回答をしたと言った。
また、n人のうちliarCount人は嘘つきであり、oracleから聞いた答えと逆のことを言うとも言った。


このとき、「卵が先」「鶏が先」「どちらともつかない」「oracleは嘘を言っている」のどれかを判定せよ。


n≦100万を満たす。

試行錯誤

oracleってなんだっけ。神託みたいな意味?
なんか難しめの250な気がする……


えーと、真実が卵と鶏の場合でそれぞれについて卵の回答のありえる最小・最大、鶏の回答のありえる最小・最大について考えればいいのかな?
ごちゃごちゃして良く解らないorz


落ち着いて考えよう。

  • 本当の答えの数が最小になるのは、正直者に嘘をなるべく教えて、嘘つきになるべく多く真実を教えた場合
  • 本当の答えの数が最大になるのは、嘘つきになるべく多く嘘を教えて、正直者になるべく多く真実を教えた場合

なので、最小の数は……図を描いてみる。
嘘つきと嘘の数を場合分け。
嘘つき≧嘘なら、n-(嘘つき-嘘)
逆ならn-(正直-真実)=n-(嘘-嘘つき)


なので、最小の数はn-abs(嘘つき-嘘)か。
最大の数も同様にして、n-abs(嘘つき-真実)


帰ってきた回答がそれぞれの範囲にあるか見ればいいんじゃないか。
書いた。サンプル合った。やばい遅い!!焦って送信。


Mediumを開く前に見直す。
本当かなあ。中間の数は全部本当に作れる?これ偶奇一致しないとダメじゃないか?
嘘つきに1回嘘を教えたのと、正直者に真実を教えたのを入れ替える。
すると……2変わって、1だけ変わるの無理じゃねーか。


例えば、n=2,eggCount=1,lieCount=1,liarCount=1とかだとoracle嘘つきじゃないとダメじゃん。テストしてみる。
うごー「どちらともつかない」が返るorz


偶奇の条件もつけてリサブミットorz
120点台とか酷すぎる。

Medium BatchSystemRoulette

問題

1台の大型コンピュータにn個のジョブを与える。
それぞれのジョブの実行時間はduration[i],ジョブのユーザはuser[i]で与えられる。


コンピュータは、各ユーザの待ち時間の平均値が最も小さくなるようにジョブを実行する。
そのような実行の仕方が複数あるときは、それらのうちから等確率で一つを選ぶ。


このとき、各ジョブが終了するまでの時間の期待値を求めよ。


n≦50,
duration[i]≦10億を満たす。

試行錯誤

平均を最小にだから、合計を最小にすればいい。


えーと、ユーザが全部異なる場合は単にgreedyに実行時間が小さい順に実行するのが最適。
一つのユーザがジョブを2つも3つも持ってたら?

  • 同じユーザのジョブはどう入れ替えても解に関係なさそう。

ユーザA,BがいたとしてAのジョブが2つ、Bのジョブが1つあったとする。
ABAとかはAABにできる。すると合計は減るので、結局

  • おなじユーザのジョブは一箇所に纏めるのが最適

っぽい。合ってるよな??


なので、ユーザごとにジョブをまとめて->実行時間の小さいユーザから実行かな。
あれ待て、ジョブの実行時間が全部1だと

  • AABB
  • BBAA

どっちでもおkじゃん、てことは、実行時間が同じユーザは入れ替え可能。
うおーごちゃごちゃする。


ユーザごとに纏めたあと、実行時間ごとにまとめる必要がある。
んでその後は……n!とかできないから期待値の線形性でも使うんだろう。


2つのジョブがあったらどっちが先に来るかは全部独立に1/2
なので、
(それまでの実行時間)+Σ(同立のほかのジョブの時間の0.5倍)+(自分)が期待値。
おkコードにすればいい。


残り時間は20分くらい?あんまないが、書けそう。
書いた。コンパイル。テスト。おkサンプル通る。


えーと、値の範囲とか大丈夫だっけ?durationは10億?
あれ、3つ足すと溢れんじゃん。これはチャレンジで使えそうだなー。


intで合計してるとこをlong longに直す。おkSubmit.
っておいいいいいいいいいいコンパイルし直さないでSubmitしてるぞクソがあああああ
あわててコンパイル→サブミット


もうだめだ60点損した。何やってんの。

Hard

Unopened.

Challenge

やばいやばいリサブミットで100点以上損してる。何とか取り戻さないと。
2回〜3回撃墜で70位くらいにはなれるか?


2の剰余チェックしてない奴は絶対居るはず。探す。居た。
落とせた!


あれ?こいつも?あ、あれ失敗。
うん??eggCountの数だけループしてる。うおおこういう解法あったのかー。


別の奴。やたらソース長い。
でもこれも剰余判定してねーよなー。ループもしてない。
だらだら何やってんだろこれ。早く投げないと。


あれ?失敗だとー;
さっきの成功の分0になっちまった。やばいやばいやばい。他に落とせる奴……


500で、期待値の線形性使ってない人とかlong long忘れが居るはず。
long long忘れはー……一人も居ない。居てくれよ!!


えーと、0.5が出てこない奴発見。これは?階乗があるぞ。怪しすぎる。
メモ化再帰してるっぽい。えーこんなの通るわけねーだろ
全部1のケースを投げる。


えー終わりやがった。クソが

System Test

リジャッジが3回くらいあった。凄いぐだぐだ感。


取りあえず二つとも通った。
自分もぐだぐだで色々今回酷かった。