lay_contest beta round 00001 : C - 縁

Cが大ひっかけ問題？だったおかげでC,DでFAを取れました。
https://www.hackerrank.com/contests/lay-contest-00001/challenges/challenge-380

問題

プレイヤーは163時間の間にダンジョンに潜りポイントを稼ぎガチャを引くゲームを行う。
100ポイントで1回ガチャを引ける。

プレイヤーはN人のフレンドのうち誰か1人を連れてダンジョンに潜ることができる。
ただし、各フレンドは一度選ぶと次に再び選ぶまで(前回ダンジョン潜入開始時より)1時間は空けなければならない

1回ダンジョンに潜るのにX分かかる。
フレンドと共に潜るとAポイント、単独で潜るとBポイント得られる。

N,A,B,Xが与えられたとき、最適なダンジョン潜入タイミング・フレンド選択を行った場合、最大で何回ガチャが引けるか。

解法

N人を1回ずつダンジョンにつれて潜った場合、合計時間(X*N)分が1時間を超えるなら毎回フレンドを連れて隙間なくダンジョンに潜ればよい。
以下、そうでない場合((X*N)分が1時間未満の場合)を考える。

まず隙間なくダンジョンに潜る場合を考えよう。
(X*P)が初めて1時間以上となるPを考える。
各フレンドはP回ごとに再度選択可能になるので、P回のうち前半N回はフレンドと共に潜り、後半(P-N)回は単身で潜るのが最適である。

…と恐らく(自分の初発WAも含め)多くの人はここでひっかかったと思われる。
実は間に隙間を作った方が有利な場合がある。
例えばX=59,N=1の場合、あえてフレンドと1回潜った後1分待つことでまだフレンドと潜ることができる。
AがBより十分大きい場合、無駄に単身で潜るより1分まった方が得である。
一方、1時間を超えて無駄に待つメリットはない。

とはいえ、どの程度まで隙間を入れ、どの程度まで隙間なしに潜入するのかは直感的にわかりにくい。
幸い163時間と時間は短いので、総当たりで対応しよう。

0≦h≦163となる各整数hに対し、

• 163時間中h時間は間に隙間を入れて1時間ごとに潜入し、
• 残り(163-h)時間は隙間なく潜入する

場合の合計ポイントの最大値を求めれば良い。

int T;
int X,A,B,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>A>>B>>N;
		
		if(X*N>=60) {
			cout<<163*60/X*A/100<<endl;
		}
		else {
			
			int ma=0;
			int perhour=A*N+B*(60/X-N);
			
			j=(60+(X-1))/X;
			
			FOR(l,164) {
				y=l*perhour;
				i=(163-l)*60/X;
				
				y+=i/j*(A*N+B*(j-N));
				i%=j;
				if(i<=N) y+=A*i;
				else y+=A*N+B*(i-N);
				
				ma=max(ma,y);
			}
			
			cout<<ma/100<<endl;
		}
		
	}
}

まとめ

良い(そしてちょっと憎らしい)ひっかけ問題でした。
これノーミスで解ける人いるのかなぁ。