HackerRank (unofficial) lay_contest beta round 00001 3問目 - 縁（writer担当）

Source

HackerRank (unofficial) lay_contest beta round 00001 3問目
problem statement（コンテストページ）

問題概要

高橋くんにはフレンドが $N$ 人います．
ダンジョンをクリアするのに $X$ 分かかり，フレンドとクリアすると $A$ ポイント，そうでなければ $B$ ポイントの縁ポイントが貰えます．
同じフレンドは $1$ 時間に $1$ 回までしかダンジョンに連れていくことができません．
高橋くんは $163$ 時間プレイできるとして，$1$ 回 $100$ 縁ポイントで回せる縁ガチャを最大で何回できるかを求める問題．

解法

手に入る最大の縁ポイントを求めれば良い．
まず，各状況において，高橋くんはどのように行動するのが最適なのかを考える．
フレンドを連れていける状態であれば，即座にフレンドを連れてダンジョンに行くのが最適．
フレンドを連れていけない状態であれば，フレンドが連れていけるまで待つか，フレンド以外を連れて即座にいくかの選択肢が生まれる．
しかし，ダンジョンを $1$ 回クリアしてもフレンドをまだ連れていけない状態であれば，取り敢えず $1$ 回ダンジョンに行ったほうが良い．
よって，次にダンジョンに行けばフレンドを連れていける状態になる時に，ダンジョンに行くかどうかというところだけが本質的な選択肢である．
また，その場合，どちらにせよ，その後はフレンドを連れていけるので，その後は同じ状況に戻る．
（$1$ 人目のフレンドを連れていける状態に戻れば，そのフレンドを連れて行っている間に $2$ 人目のフレンドも連れていける状態になっていく）

よって，行動パターンは $2$ パターンしかなく，$k = \lfloor 60/X \rfloor$ とすると，

  1. $60$ 分使って，$k$ 回ダンジョンに行く．その際，縁ポイントは $A \times \min(N,k) + B \times (k-\min(N,k))$ 貯まる
  2. $kX$ 分使って，$k+1$ 回ダンジョンに行く．その際，縁ポイントは $A \times \min(N,k+1) + B \times (k+1-\min(N,k+1))$ 貯まる

というパターンで，最後に中途半端な時間が残った場合は，取り敢えずダンジョンに行くのが良い（それはパターン1ともパターン2とも同じ感じになる）．
（つまり，$2$ 種類しか物がないナップザック問題に近い形をしている）
パターン $1$，パターン $2$ は順番は入れ替えても良いので，パターン $1$（パターン $2$）を何回使うかで全探索して，答えを求めれば良い．
プレイできる時間数を $c=163$ とすると，時間計算量は，各テストケースにごとに $O(c)$ 程度で解くことができる．

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

#include<bits/stdc++.h>
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)

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);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}


int solve(int X, int A, int B, int N){
  int i, j, k;
  int t1, t2, gain1, cost1, gain2, cost2;
  int res = 0, tmp, t;
  int L = 163*60;

  t1 = 60 / X;
  t2 = t1 + 1;
  gain1 = min(t1,N) * A + (t1-min(t1,N)) * B;
  cost1 = 60;
  gain2 = min(t2,N) * A + (t2-min(t2,N)) * B;
  cost2 = X * t2;

  for(i=0;;i++){
    k = cost2 * i;
    if(k > L) break;
    j = (L - k) / cost1;
    t = (L - i*cost2 - j*cost1) / X;
    tmp = gain2 * i + gain1 * j + min(t,N) * A + (t-min(t,N)) * B;
    res = max(res, tmp);
  }

  return res;
}

int main(){
  int T, X, A, B, N;
  int res;

  reader(&T);
  assert(1 <= T && T <= 100000);
  while(T--){
    reader(&X,&A,&B,&N);
    assert(1 <= X && X <= 120);
    assert(1 <= B && B < A && A <= 100);
    assert(0 <= N && N <= 40);

    res = solve(X,A,B,N);
    writerLn(res/100);
  }

  return 0;
}

Current time: 2024年05月08日22時00分05秒
Last modified: 2016年03月19日16時12分30秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_lay-contest-00001
トップページに戻る

Logged in as: unknown user (not login)

ログイン：