cafelier@SRM

SRM450

SRM | 12:26 |

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 |

とりあえず 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ラウンドで全額稼げるようになるので、そのくらいまで増やしたらループがすぐ終わる

なるほどなあ。