TopCoder SRM 827 : Div1 Easy ContestTraining

まーたミスしてる…。
https://community.topcoder.com/stat?c=problem_statement&pm=17498

問題

以下の要領で問題を解いていくことを考える。

• 最初のHD日間は、1日HP問題を解く
• 続くのLD日間は、1日LP問題を解く

上記処理を交互に繰り返す。

Q問の問題を解き切るのにかかる日数はいくらか。

解法

1周で(HD*HP+LD*LP)問解けるので、まずfloor(Q/(HD*HP+LD*LP))周しよう。
残りの問題は1周以内に解けるので簡単な計算で日数を算出できる。

class ContestTraining {
	public:
	vector<long long> practice(long long heavyDays, long long lightDays, long long heavyProblems, long long lightProblems, vector<long long> queries) {
		vector<ll> ret;
		__int128 H=(__int128)heavyDays*heavyProblems;
		__int128 L=(__int128)lightDays*lightProblems;
		
		FORR(q,queries) {
			__int128 a=q/(H+L)*(heavyDays+lightDays);
			q%=(H+L);
			if(q<H) {
				a+=(q+heavyProblems-1)/heavyProblems;
			}
			else {
				q-=H;
				a+=heavyDays;
				a+=(q+lightProblems-1)/lightProblems;
			}
			
			
			ret.push_back((ll)a);
		}
		return ret;
	}
}

まとめ

問題のネタ切れを心配してしまうな。