Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2009-10-18

SRM450

| 12:26 | はてなブックマーク -  SRM450 - cafelier@SRM

SRM450 の成績・ソース (要ログイン) : AC/WA/WA : ぜんぜんわからない

500開く

  • 『n個の工場とk人の技術者がいると1ターンでn*k円稼げます。price円につき++nもしくは++kできます。最速でtarget円稼ぐには?』
    • 入力の数値は全部1~10^12程度

  • n*kを最大化するには…n+kが同じなら、えーと4*2より3*3の方が大きいから
  • できるだけnとkを近くした方が常にいい。
  • そういう雇い方だけ考えればいいから、そこは探索不要

  • どのタイミングでどれだけprice使えばいいかは…
  • これもgreedyに決まるのかな。
  • わからんなあ。DPで求めるんだろうか。
  • 最悪ケースで何ターンかかるかというと…10^12ターン
  • これは毎ターンシミュレーションでは絶対無理だ…

  • そもそも10^12 * 10^12ってヤバくね?64bit越えてね?
    • 越えてる。
    • target/k<=n だったら即座に1を返すようにしておく。
    • これなら、後の計算は10^12オーダに収まってるはずなので、後は無事だと思う。

  • さて、毎ターンシミュレーションは無理だけど
  • とりあえず、
    • price払ってn,kを適当に一気に増やす
    • targetに達するか、次のpriceの倍数を超えるまでは、n,kは増やさず淡々と稼ぐ
  • というやり方だけ考えればいい。
  • じわじわn,kを増やすくらいだったら、最初に一気に増やして、
  • 毎ターンの増分n*kを早めに増やした方がお得
  • という次の行動ターンまで待つルーチン追加

  • 問題は、「price払ってn,kを適当に一気に増やす」の最適値は何かと言うことで…

  • うーん

  • 全然わからん。

  • たくさんお金使って資金が減りすぎて遅くなることもあるし、
  • ケチりすぎて毎ターンの増分が少なすぎて遅くなることもある
    • C*price 円使うとすると、
    • C*price より f(C,n,k)*turn が上回るターン数(f()はn,kを最適に増やしてn*kを返す)が一番早いのを選ぶ。
    • これはどうだ。

  • どうだろう。turnが一番早くてもそのときn,kが少なかったら後で負けるみたいなパターンがあるような気がしなくもなくも…
  • いや、そのときはそこで更にn,kをこのタイミングで増やせば
  • 資金は多いからそっちのがベターか。

  • うーむ、全然自信ないけど、もう30分以上たってるし、書いてみるしかないかー。
    • たぶん凸関数なので三分探索で最小値を求める
    • ごにゃごにゃ
    • サンプル通った。my最小最大テストケースも通った
    • 出しちゃえー。これは考えててもわからん。

250開く

  • みんなかなり順調に解いてる。瞬殺問題か
  • 『Nim』
  • と見えた。なんだろ。xorする公式を使えば一発とかですか。
  • それは250にしては難しすぎるような…
  • 『小石の山がn個ある。AliceとBobが交互に、左の山から順に、1個以上好きな数だけ石を取る、を繰り返す、山が空になったら次に進む。最後の石を取った方が勝ち。与えられた初期状態から、どっち必勝か計算してね』

  • えーと。簡単なケースから考える。最後を取ったら勝つんだから、
    • {}
  • 空の状態では次の手番のひとは負けてるので、これは後手勝ちの状態
    • {1, 後手勝ちの状態}
  • は、この1個をとれば先手は後手に回って勝つので、これは先手勝ち
    • {1, 先手勝ちの状態}
  • は、逆に先手負け
    • {n, 後手勝ちの状態} n>=2
  • は、n個全部とっちゃえば先手勝ち
    • {n, 後手勝ちの状態} n>=2
  • は、1個だけ残すと{1, 先手勝ちの状態}に持ち込めるので、これも先手勝ち

  • というわけで、配列を後ろから見ていって、
    • 1なら勝利サイド反転
    • 1じゃなければ、先手勝ち
  • 書いた。通った。submit。

1000開く

  • 1000はやめて500を落ち着いて考えようかなーと思ったけど、
  • 新しい問題考える方が楽しいしなー。
  • 『Nマスある双六的なものがあります。マスには整数が書いてあります。初期位置は左端、右向き。0マス以上好きなだけ右に進んでいい。進んだら、さっきいたマスから進んだマスまでの間の全マスinclusiveの和が得点として手に入る。向きは逆になる』
    • をkターン繰り返した時の最高得点は?
    • ただし、途中でスコアがマイナスになってはいけない
    • 最大50マス。スコアとターン数kは4000万くらい

  • greedyに最大得点が得られる所に動き続けりゃいいんでは?
  • ダメか、すごいマイナスのマスを一度乗り越えると、そこにはボーナスゾーンが…みたいなマップがありうる。

  • DP的に「このマスにいる動き方での最大スコア」を50マス全部並列に覚えておくとどうだ
  • これならそういうパターンも全部計算できる。

  • 計算量は…50マス×動き方50通り×ターン数…4000万くらい…orz
  • いやでも、なんか50マスしかないんだから最後の方は動き方ループしてるよきっと

  • とりあえずターン数小さければ解けるルーチンだけでも書いてから考えよう。
  • DPDP
  • 書けた。ターン数大きいの以外は解ける。

  • さて、ループ検出は…うおおあと3分しかない。
    • 最後の方は、二つのマスを行ったり来たりを永遠に繰り返すパターンに収束するはず
    • もっと不規則な振動でループすることは…ない、なさそう
    • というわけで、スコアの増分がかなりのターンの間一定だったら、そのループがずっと続くと仮定して最後まですっ飛ばす!
    • 「かなりのターン」は50*50に書けてTLEしない程度
    • 1000くらいか。意味ありげな値で50*50にしとこう。

    • 書けた。ターン数長いのも通った!
    • いやしかし
      • {低スコアゾーン, マイナスの堀, 好スコアゾーン}
    • で、低スコアゾーンで10万ターンくらい頑張るとやっとマイナスを越えられるようなケース、明らかに誤判定するな
    • しらん、出しちゃえ!
    • こう、こんな解答出すヤツ想定されていなかったら通ったりするかも!

撃墜タイム

  • 500で素直にn*kしている解答を狙って1撃墜、1失敗
    • オーバーフローしても条件式の都合でうまく抜けちゃったりするんだよね
    • そういうのが無さそうなのをちゃんと練っておけば良かった。
  • 1000はACRushのチャレンジを2回防衛するも3発目で撃沈。^^;;;
  • ついでに500も落とされた

感想

  • なんかもう全然わからんな。
  • 500はアルゴリズムミスの以前に、コーディングすらミスってたっぽい落とされ方をしている。うむう

SRM450 Div1 500

| 21:13 | はてなブックマーク -  SRM450 Div1 500 - cafelier@SRM

とりあえず if(target/n <= k)return 1; はあり得ない…

class StrongEconomy { public:
   long long earn(long long n, long long k, long long price, long long target) 
   {
      if( target/n < k )
         return 1;

      LL best = target;
      for(LL money=0, round=0; round+1<best;)
      {
         // ここから何もしなかった場合のラウンド数
         best = min(best, round + roundsNeededToEarn(target-money, n*k));

         // (n,k) を増やせる様になるまで待つ
         if( money < price )
         {
            LL rp = roundsNeededToEarn(price-money, n*k);
            round += rp;
            money += n*k*rp;
         }

         // (n,k) を増やしてみる
         //   - もう増やさない方がいい可能性は「何もしなかった場合」で考慮済み
         //   - 今増やさず後で増やす方がいい、ということはあり得ない
         (n<k ? n : k)++;
         money -= price;
      }
      return best;
   }

   LL roundsNeededToEarn(LL t, LL v)
   {
      return (t-1)/v + 1;
   }
};

これで間に合う、というのが見積もれてない。うっかりround<best を終了条件にすると全然終わらないし。</ppp>

えーと

  • ループが回る回数 = (n,k)を増やしてみる回数
  • (n,k)を増やしてみる回数は、最適解で(n,k)を増やしてみる回数+α回くらい
  • (n,k)をX回増やすと、1ラウンド辺りの稼ぎがO(X^2)になるので、O(√target)回増やせば、1ラウンドで目標金額稼げるようになる。なので増やす回数は最大でも10^6オーダ
    • これは問題ないサイズ
  • 問題は +α 回
    • これも問題ないか。同じ理屈で、X+α≒O(target)回増やした後は1ラウンドで全額稼げるようになるので、そのくらいまで増やしたらループがすぐ終わる

なるほどなあ。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20091018
 | 

presented by cafelier/k.inaba under CC0