2012-03-10

■ [SRM]SRM536 20:59

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14728&rm=311896

• Coding
  • 250
    • たとえば単純に、正と負の要素がある、と考えたとき、まず負のやつだけを1つにまとめてから他とくっつけると良さそう
    • などのように考えていると、結局小さいものから順に2つずつくっつければ良いのでは、と直感する
    • 証明もやればできそうだし、他の人らも提出してるし、ということでさっと書いて提出してしまう
    • しばらく様子を見ていたが誰も再提出しないので大丈夫だろうと確信
  • 500
    • 頻度のグラフは左右対称な台形になる
    • 一番上の辺の位置と長さだけが分かっていれば更新していける
  • 1000
    • サイズが10^16なので、2進表記でバイナリーなあの感じでやるのだろう
    • 直感的には、何度も多項式を掛けていったら0の項がどんどん増えていきそうな気がするが
    • 試してみると、P^(2^N)のときに1になる項は、Pで1の項の次数を2^N倍したところのみだとわかる
    • ということで、P,P^2,P^4,... のうち必要なものを使うとすると、項が高々50個の多項式を高々50個くらい掛ける、と整理される
    • 単純にDPすると計算量50^50になってだめなので良い方法を考えていたが浮かばなかった
    • 残り10分切ったくらいの時点であきらめて枝刈り探索やっておくべきだった
• Challenge
  • 500で単純に平均を使っている人がいたので落とす
• System Test
  • 2問とも通った

• 244.86 + 375.22 + 0.00 + (50*1-25*0) = 670.08
• 29位/798人
• 2162->2256

念願のデュアルレッドコーダー

■ [SRM]SRM535 20:59

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=15037&rm=311769

• Coding
  • 250
    • √L/Gまで全部調べて2つの約数に分ければ良いというのがすぐ見えたので書く
    • 2つの約数が互いに素でないといけないこと、考えてるときは気にしてたけどコードを書くときには忘れてしまっていた
    • サンプルで拾われて良かった
  • 500
    • 計算量50*500万のDPを書いてしまった。提出してから最大ケース入れてMLEすることに気づく…
    • 計算量落ちないかなーと考えてたけど無理だった
• Challenge
  • 寝落ちしていた
  • 500は落とされた。部屋内の500をwataさんが落としまくっていた
• System Test
  • 250は通った

• 242.89 + 0.00 + 0.00 + (50*0-25*0) = 242.89
• 129位/900人
• 2131->2162