AtCoder Regular Contest #021 C問題 - 増築王高橋君

Source

AtCoder Regular Contest #021
問題文

問題概要

$N$ 個の建物がある．
建物 $i$ の最初の価格は $A_i$ で，増資をするたびに価格が $D_i$ だけ上昇する．
増資をするには，建物の価格と同じだけのお金を払うことでできる．
$K$ 回増資するために必要な最小金額を求める問題．

解法

$C$ 円以下で増資できるものを，全て増資した場合の総増資回数は簡単に求めれる．
それが，$K$ 以上となる最小の $C$ を二分探索で求める．
$C$ 円以下で増資できるだけ増資して，増資しすぎたものは$1$ 回 $C$ 円で増資しているのでその分引く．
全体的に数が大きいので，オーバーフローに注意．答えの最大値 $\times 2 \geq 2^{63}$．

C++によるスパゲッティなソースコード

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int main(){
  int K, N;
  static int A[200000], D[200000];

  int i, j, k;
  ll AA, BB, CC;
  ll num, res, tmp;

  reader(&K);
  reader(&N);
  rep(i,N) reader(A+i), reader(D+i);

  AA = 0; BB = 10000000000000LL;
  while(AA<BB){
    CC = (AA+BB)/2;
    num = 0;
    rep(i,N){
      if(A[i] > CC) continue;
      num += (CC - A[i]) / D[i] + 1;
    }
    if(num >= K) BB = CC; else AA = CC+1;
  }

  res = 0;
  num = 0;
  CC = AA;
  rep(i,N){
    if(A[i] > CC) continue;
    tmp = (CC - A[i]) / D[i] + 1;
    num += tmp;
    if(tmp%2==0) res += (A[i] + (A[i] + (tmp-1)*D[i])) * (tmp / 2);
    else         res += (A[i] + (A[i] + (tmp-1)*D[i])) / 2 * tmp;
  }
  res -= (num - K) * CC;

  writer(res, '\n');

  return 0;
}

Current time: 2024年04月25日16時55分23秒
Last modified: 2014年04月13日00時34分45秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC021 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：