結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー Andrew8128
提出日時 2025-10-28 20:52:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,928 ms / 2,000 ms
コード長 1,982 bytes
コンパイル時間 2,587 ms
コンパイル使用メモリ 277,172 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-28 20:52:45
合計ジャッジ時間 7,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
long cnt;
long N, X, Y;
long double P, Q, R;
// 通常業務remain回のうち、クビになる選択をx回行うときの期待値
long double f(long x, long remain, long double p)
{
  cnt++;
  long double a = (remain - x) * (Q - (1.0 - p) * R);  // もみ消す
  long double b = Q * ((1.0 - pow(p, x)) / (1.0 - p)); // クビになる
  return a + b;
}
// クビになる選択をする回数をx回からx+1回に変更したときの差分を求める
long double g(long x, long remain, long double p)
{
  long double a = -Q + (1 - p) * R;
  long double b = Q * pow(p, x);
  return a + b;
}
// 研修をt回受ける時の最適値を求める
long double h(long t)
{
  long skill = X + t * Y;
  long double p = 1.0 - 1.0 / skill;
  long remain = N - t;
  if (skill == 1) // 卵をかけてしまう確率が100%のとき
  {
    return P * t + max(0.0L, Q - R) * (remain - 1) + Q;
  }
  long l = 0, r = remain;
  while (r - l > 3)
  {
    long m1 = l + (r - l) / 3;
    long m2 = r - (r - l) / 3;
    long double v1 = f(m1, remain, p);
    long double v2 = f(m2, remain, p);
    if (v1 < v2)
    {
      l = m1;
    }
    else
    {
      r = m2;
    }
  }
  long double ret = 0;
  for (long i = l; i <= r; ++i)
  {
    ret = max(ret, f(i, remain, p));
  }
  return P * t + ret;
}
int main(void)
{
  auto solve = []()
  {
    cnt = 0;
    cin >> N;
    cin >> X >> Y;
    cin >> P >> Q >> R;
    long l = 0, r = N;
    while (r - l > 3)
    {
      long m1 = l + (r - l) / 3;
      long m2 = r - (r - l) / 3;
      long double v1 = h(m1);
      long double v2 = h(m2);
      if (v1 < v2)
      {
        l = m1;
      }
      else
      {
        r = m2;
      }
    }
    long double ans = 0;
    for (long t = l; t <= r; ++t)
    {
      ans = max(ans, h(t));
    }
    cout << fixed << setprecision(10) << ans << endl;
    // cout << cnt << '\n';
  };
  int T;
  cin >> T;
  for (int i = 0; i < T; i++)
  {
    solve();
  }
}
0