2011-03-30

■ [SRM]SRM501 01:28

2011-03-30 20:00-（JST）

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14430&rm=307626

きつね回。

Level	タイトル	試合中	あとで	ひとこと
250	FoxPlayingGame	AC 13min	-	ヒューリスティックにやるときは慎重に
500	FoxAverageSequence	AC 32min	-	メモリの使い過ぎにハマる
1000	FoxSearchingRuins	Opened	-	読んで捨てた。探索系苦手

• Coding
  • 250
    • 掛け算は全部最初にやるか全部最後にやるかくらいしかないんじゃないの？
    • あとサンプルにもある、最後にBをnB-1個掛ける場合
    • 本当にそれでいいか自信が持てないのでパターンを列挙してみる
      • Aの値の正負
      • Bの値の正負
      • Bの値の絶対値が1以上かどうか
      • これらの組み合わせ2*2*2通りで確認
    • 「Aが負・Bが負・Bの絶対値1未満」の場合はBを最後に1回掛けるのがベストで、サンプルでカバーされていないパターンだということに気づく
    • なので、Bを最後に「0回・1回・nB-1回・nB回」掛けるのを試してそれらの中で最大になるのを答えとする
      • 場合分けはやりたくないので気にせず4通り試してしまえば良い
      • というかもうこの4つに限定せず0回～nB回まで全部やってしまえばよかった
      • nBが0でないかの確認もいらなくなるし
    • 最大ケースや最小ケースも確認して提出
    • でもこの問題たぶん一番速いのは読んだ瞬間DPを書き始めることなのだろうけど
    • そんな瞬発力ないのと、EasyがDPなはずがない理論でうまい解を考えてしまうのとで、なかなかそうはできないものです
  • 500
    • ストレートにDPだなあ
    • 計算量は、単純にやると「数列のi番目の数が」「jである」という状態を更新するのに「i-1番目がkで」「i-1番目までの和がlで」「1つ前から減少している・していない」を調べる必要があるから40*40*40*40^2*2=2億。無理っぽい…
    • でも、i番目を調べるときには、i-1番目までの和は最大40*(i-1)までしか見なくてよい。これで半分
    • それまでの数列の平均値を下回らないという制約を入れると、i-1番目までの和について調べる範囲が限定される
    • あと連続で減少してはいけないという制約もあるからさらに減って、なんとかいけそうな気がしてきた
    • 書いてみたら、手元のテストで最小のサンプルに対してもやたら時間がかかっている（0.8秒とか）
    • とりあえずサーバーで実行してみると、OutOfMemoryExceptionが返ってきた…
    • DP用の配列をint[1601][40][41][2]で一気にとってたのがだめみたい
    • DPを進めていくに従ってint[1601][41][2] を40回確保するようにしたら大丈夫になった
    • 最悪ケース（-1が40個）も1秒ちょうどくらい。これは大丈夫だ。提出
  • 1000
    • パラメタ多い…
    • まずはダイクストラが浮かぶけども状態数が多くてだめ
    • あまり時間もないし諦めてぼんやりしていた
• Challenge
  • 250はサンプルにないケースで落ちる人がたくさんいそう…とわくわくしていたらそこまでいなかった
    • 2人を{1,50,-10000,-1}で撃墜
    • DPでやっている人が思いのほか多かった
• System Test
  • 2問とも通った

結果

• スコア：206.84 + 270.87 + 0.00 + (50*2-25*0) = 577.71
• 順位：60位/710人
• レート：2204 -> 2253

500は一瞬でDPということはわかる問題なのだからもっとスムーズにできないといけないなぁ