TopCoder SRM481 Div1

ひさしぶりのするめ

250

予言者が「鳥と卵どっちが先にあったの」という問に対してN人の人に答えた。でも何人かにはでたらめな答えを言ったらしい。そのN人の人に質問したら、いくつか「卵」って答えが返ってきたけど、ある人数だけ嘘つきがいるらしい。鳥？卵？っていう問題。

非常にバグ死しやすいやるだけ。落ちた

500

何人かのユーザーがコンピュータに処理をさせようとしている。ユーザーは１人で２つ以上の処理をさせるかもしれないけど、コンピュータは１度に１つしか処理できない。各処理は所要時間が決まっている。コンピュータはユーザーの待ち時間の平均が最小になるような処理順の中から等確率で１つ選ぶ。各処理が終了するまでの時間の期待値を求めよ、という問題。

まず、同じユーザーの処理は１まとめにしていい。その中の順番は自由。あとは、ある２人以上のユーザーの処理の総計時間が同じ時は、どのユーザーから処理してもいい。これに気づけばあとはやるだけ。これだけ通った

900

数直線上にプリンタが何台かあって、プリンタ間の距離は決まっている。プリンタを使って、いくつかの数字を印字したい。数字を印字するためには、プリンタのカウンタを動かして目的の数字にして印刷しなければならない。プリンタはどの数字を印字してもいい。そのためのプログラムが用意されていて、プリンタの場所に着いたらすぐにプリンタは印刷に向けて処理を始める。プリンタの間を移動するのも、プリンタのカウンタを1動かすのも、プリンタの数字を印字するのも時間がかかる。全部印刷するのにどれくらい時間がかかる？という問題。

そのときは順序全探索×二分探索×二部グラフマッチングで解ける気がしたけどSystem Test Failedした。でも同じコードをPracticeに投げたら通った。どうやら1.989[s]かかるテストケースがあってそれの誤差で落ちたらしい。萎え☆

実はこれ二部グラフマッチング必要ないみたい。多分ソート×greedyで解ける
結局「順序全探索×二分探索×greedy」

結果

ジャッジメントが狂っていてDiv1Hardがおかしかったり「System Test Failedするともらえるはずの点数分だけ余計に減点☆」とかいう変なオプションルールを捏造したりしててなかなか結果が出なかったので寝た

xox 303.16(120位)

Rating: 2024 -> 2063 (なぜか少し上がった)

はやく赤色になりたい。というかこの学校黄少年多すぎ