TCCC Round 2

Program

細々とQualification、Round 1、Round 2と参加していたのですが、
なんだかもういろいろと限界を感じる今日この頃。
本日は問題を読むのに辞書を一度も使わなかったのが
微妙にうれしかったところですが、
それよりももうこういう戦いは精神的につらい…。
神経が磨り減ります…。
せめてICPC方式だったらなあ。
Round 4まで行けたら、もう今の私では
よほど運がよくなければ勝てないだろうから、
乾坤一擲、あまり神経を使わずに、全速力で参加してみようと思いますよ。


問題についての感想

http://www.topcoder.com/stat?c=round_overview&er=5&rd=10891

  • 250点 整数 a,b に対して a<=x^k<=b なるx,kのうちkを最大にするものを求める
  • 500点 RLEで現された整数二つを加算する
  • 1000点 コスト最小になるように仕事を割り振る


250点問題は普通にループまわして間に合いそうだったから、普通にループをまわした。
500点問題はどう見てもやるしかなさそうだったからこれもゆるゆると実装。
なんだか伸びに伸びて100行以上も書いてしまった。
最初書いたバージョンには間違いがあったけど、
コード書きながら考えていたテストケースで見つかったのでよかったよかった。
1000点問題は20分ぐらい考えたけどわからず。コストが二乗じゃなければ最小費用流…
というか、そもそもそんなものを持ち出してくる必要も何も無い問題になってしまうが…。
得点の高い人達のソースを見てみると、
とってもグリーディーな感じになっておりました。
ある人にi個目のタスクを追加したときのコストの増分を小さい順にソートして、
それを小さい順になめながら、その人にタスクが追加できるなら追加していく、
という方式で、タスクが追加できるかどうかは、
その人ができるタスクいずれかを割り当てるのですが、
すでにほかの人に割り当てられているタスクがあれば、
そのタスクを行っている人に別のタスクを再帰的に割り当てて、
そのタスクはその人に割り当てる、ということを行うようです。
これでよいのかどうかは、
そもそもコストの増分の小さい順に追加していっていいのか、と、
この方法で本当に割り当てが可能なときに可能であるとわかるのか、
という二つの点において私には不明なのですが、
後者に関しては、この部分の割り当てを
最大流を用いて行っている人もいたので、
それであれば問題の半分は解決したことになります。
しかし、なんというか、こんなの5分やそこらで思いつくってレベルじゃねーぞ。
よくあるタイプの問題なのかなあ。