Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2011-12-24

Codeforces Beta Round #99 Div. 2

00:32

久々に参加してみたところひどい記録になりました。

o opened o opened x : 1830 pts. 147th. Div. 2であることを考慮するとひどすぎです。主に読み間違いがひどい。

A

ループしながら引き算。愚直に n -= a[i % 7] しました。一週全部で読める量を調べたりすると罠にハマるそうです。具体的にはp週間でぴったり読み終わる場合に7じゃなくて1と出したりする。

B

問題の英語が難しい。

各部屋に最安の壁紙を割り当てるだけでした。が、以下の場所を読み間違えます。

And pieces of the same roll cannot be used to paper different rooms. That is, for each room the rolls are purchased separately.

壁紙の切れ端を別の部屋の壁紙にしないでね、という話です。これを、rollをtypeと読み間違えて、同じ壁紙を複数の部屋に使わないでね、と読んでしまいました。あっという間に最小コスト2部グラフマッチのできあがりです。手元にライブラリが無いのでスルーしてしまいました。

C

やるだけです。韻を踏むだけの母音がない場合に注意しましょう。

D

105桁まで、を105まで、と勘違いして全く通りませんでした。TLEではなくint32 overflowかなにかしていた模様です。正しくは

  • 足して10になるものがなければ、0の数が答え。そうでなければ以下。
  • 1の位になりうるもののうち、0を用いない5通りについて以下を試し、最大の値を返す。
    • 10以上の位になりうる組み合わせの総数を数える。
    • 余った0があれば下の位に集める。

こんなところでしょうか。49060 + 60940 みたいなので落としていてもおかしくは無いです。


E

一次元上に得点源がばらまかれていて、ある確率である範囲の得点源がお釈迦になります。その際の得点の総和の期待値はいくつでしょう。

N(得点源の数) * M (区間の数) をやるとTLEしそうなので注意して、端から順に見ていくだけでO( (N + M) log (N + M) )で解けるなと思いつつ解いていましたがTLE。区間同士が非常に重なり合っている場合に、それすべてを毎得点源について掛け算しているのでO(N * M)かかっていました。

  • 総和を覚えておく時みたいに、掛け算の結果を保持して、区間の出入りの際に差し引きする。
  • 確率100 % で死滅する、という入力が来る。これをそのままかけてしまうと、掛け算の結果は0になってしまい、その区間を抜けても元の確率は復旧しない。0を直接かけず、0が掛かった回数を覚えておくことでそれを回避。
  • 区間の数が10 ^ 5あるので、普通に掛けるとアンダーフローしうる。logを保持する方が無難。

コンテスト終了後に、全部をやって通りました。

 |