DIV1 Medium Random Challenge第2回。
1. (n, k) を増やせるだけのgoldが入ったらすぐに投資していった場合の折れ線の始点と傾斜から、というか、そこで投資しなかった場合に目標に達するのがいつかを算出しておく
ってやって行って最速の時期を出す。ループの止め時は「そこ」がここまでの最速より後になった時
買い増すのは少ない方 ← (a+1)b - a(b+1) = b-a;
どうせ同じだけ買うなら早い時期に買ったほうがいい
って感じでテストケースは通るんだけどさ
- long longだと、n=k=1e12, (≒2e40) のとき nk =1e24=2e80 になって破綻
- n, k は 1e12でキャップすべし。1e6でいいかと思ったけど、例えばprice=1e12のとき1つずつしか買えないので初回に困る
cf. int128
// #include <bits/stdc++.h> これは要らない？ typedef __int128_t Int128; typedef __uint128_t UInt128;
→WA
テストケース1つ落としたから調べたら、分配間違ってるじゃん
2. (n, k) に bought を分配するところで均等割しちゃってる
1) n <= k として n+bought <= k なら、nに全額 ←これ 2) そうでなければ (n + k + bought) を計算して、半分ずつにする（余りはkに載せる）
→AC
Editorial
https://apps.topcoder.com/wiki/display/tc/SRM+450
初回以外は1つだけ買えればいいのか？ とするとnもkも1e6でいいのか？ ↑それだけあればtargetのgoldを1回で稼げるんだから、price無視できる
二分探索解法あるのね
現在のラウンドNo.が、目標金額を稼ぐのに十分かをチェックしながら解答を探索する。
check(n, k, price, target, result)
いま (n, k) として、result回以内に行けるかというpred
いまのn,kでtarget稼げるならtrue さもなければ新ユニットをつくるための金を稼ぐべきで 残りラウンド数 ＜ 新ユニット作成のラウンド数、ならfalse
実装
int128_tとか言ってるけど（使ってみたかった）別にそこまでしなくていいのでは
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout11.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n) for(int var=0;var<(n);++var)
#define rep1(var,n) for(int var=1;var<=(n);++var)
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
inline llll next_nk(llll& n_k) {
ll n = n_k.first, k = n_k.second;
if (n <= k) {
return llll(n+1, k);
} else {
return llll(n, k+1);
}
}
inline ll product(llll& n_k) { return n_k.first * n_k.second; }
inline ll cp(ll t, llll n_k) {
ll nk = product(n_k);
return (t + nk-1)/nk;
}
typedef __int128_t Int128;
Int128 T;
Int128 fastest(Int128 t, Int128 gold, Int128 nk) {
// m(x-t) >= target - gold;
// x >= t + (T - gold)/m;
return t + (T - gold + nk-1)/nk;
}
class StrongEconomy {
public:
long long earn(ll _n, ll _k, ll _price, ll _target) {
printf("earn(n:%lld, k:%lld, price:%lld, target:%lld)..\n", _n, _k, _price, _target);
Int128 n=_n, k=_k, price=_price, target=_target;
n = min(n, (Int128)1000000000000LL);
k = min(k, (Int128)1000000000000LL);
T = target;
// (t, gold, n, k) = (0, 0, n, k)
Int128 t = 0, gold = 0;
if (n > k) swap(n, k);
assert(n <= k);
Int128 f = fastest(t, gold, n*k);
Int128 fmin = f;
while (true) {
Int128 nk = n * k;
Int128 g_plus = gold + nk;
Int128 bought;
Int128 term;
if (g_plus < price) {
term = (price - gold + nk-1) / nk;
bought = 1;
} else {
term = 1;
bought = g_plus / price;
}
gold = (gold + nk*term) - price*bought;
t += term;
{
assert(n <= k);
Int128 diff = k - n;
if (bought <= diff) {
n += bought;
} else {
Int128 sum = k + n + bought;
n = sum/2; k = sum - n;
}
assert(n <= k);
}
n = min(n, (Int128)1000000000000LL);
k = min(k, (Int128)1000000000000LL);
Int128 f = fastest(t, gold, n*k);
fmin = min(f, fmin);
if (f <= t) break;
if (f > fmin) break;
}
return (ll)fmin;
}
};