cafelier@SRM

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

なるほどなあ。