競技プログラミングの鉄則 A12 - Printer

記事概要

競技プログラミングの鉄則 演習問題集のA12のとりあえず動くコードと説明．
問題 -> https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_l

注意

アルゴリズム初心者が書いてます．時間内の動作は確認してますが、必ずしも最適解ではないです．

とりあえずコード

A12_main.cpp

/////////////////
// A12-Printer //
/////////////////

// 問題解決に使う技法
// ・二分探索

#include <iostream>
#include <vector>

using std::vector;

int main(void)
{
	//============================= 入力 =============================//
	long long N, K;
	std::cin >> N >> K;

	vector<long long> printer(N + 1);
	for (auto i = 1; i <= N; ++i) {
		std::cin >> printer[i];
	}

	//============================= 計算 =============================//
	long long inf = 1'000'000'000;						// 求める答えの最大値

	// 計算の方針
	// 1～10^9の範囲の内、K枚のチラシをプリントできる時間の最小値を二分探索で求める．
	long long left = 1, right = inf;
	while (right > left) {
		long long mid = (left + right) / 2;
		
		// 時間midまでにプリント可能なチラシの枚数と求める
		long long print_sum = 0;						// 時間midまでにプリント可能なチラシ数．
		for (auto i = 1; i <= N; ++i) {
			print_sum += mid / printer[i];				// printer[i]が時間midの間にプリント可能なチラシの枚数をprint_sumに加える．
		}
		
		if (print_sum >= K) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}

	//============================= 出力 =============================//
	std::cout << right << std::endl;
}

コード説明

この問題の特徴は、ある時間tの間に全プリンタがプリントできる枚数kを求めることは簡単であるのに対し、ちょうどk枚プリントすることができる時間tを直接求めることは困難であることである．つまり、必然的に前者のアプローチで問題をとる必要がある．

ある時間tの間にプリント可能な枚数kはしたの式で求まる．

さて、問題の前提条件より、ちょうどk毎プリントする時間tは1~1'000'000'000の範囲に存在することが分かっている．この範囲で二分探索を行う．
探索を行う範囲の左端leftと右端right、その中間のmidを見る．ある時間tをmidでおく．この時、時間midの間にプリントできた枚数を k_mid でおく．k > k_midであれば、求めるtはmidからrightの範囲に存在し、k < k_mid であれば求めるtはleftからmidの間に存在することがわかる．これをright == leftとなるまで繰り返すことで、tを求めている．