Single Round Match 481 - natrium's reminder

死にました＼(^o^)／

250

「卵が先か鶏が先か」という命題に対して、n人がその答えを知っている。
各人に尋ねたところ、eggCount人が「egg」と答え、n-eggCount人が「chiken」と答えた。
n人の内、lieCount人は嘘をついて自分の知っている答えの逆を言っている。
n人の内、liarCount人はそもそも知っている答えが正答の逆である(正答の逆を答えだと思っている人が嘘をついて更にその逆=正答を言っている場合もある)。
このとき、卵が先か、鶏が先か、どちらともとれるか、どちらもありえないのかを計算する。

eggCount個の0とn-eggCount個の1をlieCount個反転させた後、liarCount個更に反転させて全て0or1になるかを判定すれば良い。
lieCount個反転させる段階で、考えうる0の最小個数と最大個数を算出して、その間にliarCountが入っているか(鶏はn-最swap(小, 大)個数)を判定したのですが
0もしくは1の数って2こずつしか変化しないので、偶奇の検査も要るということに終了1分前に気づいて、修正が間に合いませんでした。
しにました。

Easy: ChallengeSucceeded 0.00points

500

コンピュータのジョブのスケジューリング問題。
名前とジョブの処理時間の組が与えられる。一人が複数ジョブを与えていることもある。
コンピュータは同時に複数のジョブを処理できない。
各人の待ち時間(その人の与えたジョブが全て終わるまでの時間)の平均値を最小化する。
待ち時間の平均が最小なジョブの処理の順番が複数ある場合、コンピュータはその順番をランダムに選択するので
それぞれのジョブが終了する時刻の期待値を計算する。

まず、同じユーザが複数のジョブを与えている場合、必ずそれらは連続して処理される。
また、同じユーザのジョブはどのような順番で処理してもそのユーザの待ち時間は変わらないので、ここで期待値の計算が必要になる。
ジョブは最大50個与えられるので、もしも全部ユーザが同じ人だった場合
一つのジョブJの期待値を計算するのに、他のジョブそれぞれを処理する順序がJの前/後の組合せがあるのでO(50*2^49)とかかかるので全探索だと死にます。
ここでいい方法を思いつけなかったので死にました。
正しい解法は、ある順列はそれと対称な(前/後処理を入れ替えた)順列が必ず存在するので、その二つで相殺し中央値から計算できるようになります。
Challenge Phaseで他人のコードを見て気づきました。

Midium: Opened

1000

あけてないです。
Hard: Unopened

結果

0.00points
1284->1262
Div2へ降格しなくて良かったです。
Easyを安定してAccepted出来るプログラマになりたい。