Atcoder解いてみた AtCoder Beginner Contest D - Raise Minimum

AtCoder Beginner Contest D - Raise Minimum

問題はこちら

回答

Kが10^18なため、O(K)すら許されない
許されるとしたら、O(log K)や、O(N)、O(N logK)あたり
操作を行っていき、各数値を数直線上に並べた時に、規則性を見つけ、計算量を抑えようと思ったがだめだった

解説を見ると、各操作後の数列に対するminAiの単調性に注目した手法をとっていた
minAiは単調増加であり、ある値より大きくなるとその値以降はK回以下で作りだすことができなくなる
そのため、minAiの想定しうる値を用いて二分探索を行い、K回までで作りだせるminAiの最大値を求める
二分探索の中で、minAiの想定しうる値がK回以下で実現可能か否かの判定を行う

今回のポイントは、minAiの単調性に注目し、解を二分探索で求めることだった

計算量はO(N log M)となる
Mは、minAiの取りうる最大値である2x10^18である

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N; // 1~2x10^5
long long K; // 1~10^18 加算操作を行う回数 0回以上K回以下
std::vector<long long> A; // 各値は1~10^18


// O(N)でvalが解かどうか求める
bool Judge(long long val) {

	long long num = 0;
	// Aiにiを何回足せばvalを超えるか
	// 求めた回数は、K以下か
	for (int i = 1; i <= N; i++) {
		long long diff = val - A[i-1];

		if (diff < 0LL) {
			continue;
		}

		long long li = static_cast<long long>(i);
		num += (diff + (li - 1)) / li;
		num = std::min(num, K + 1);  // オーバーフロー防止
	}

	if (num > K) {
		return false;
	}
	return true;
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> K;
	A.resize(N);
	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
	}

	// 解を二分探索
	long long left = 1; // あり得る解の中で最小値
	long long right = 2000000000000000000LL + 1LL; //  // あり得る解の中で最大値 + 1 (あり得る解の中で最大値も探索の対象とするため)

	long long mid;
	while (right - left > 1) {
        // オーバーフローを起こさない書き方
		mid = (right - left) / 2 + left; // isAnsがfalseとなるとき、midは解じゃないため注意

		bool isAns;
		// midが解かどうか求める
		isAns = Judge(mid);

		// midが解の時、さらに大きな解を探索
		if (isAns) {
			left = mid; // leftは答え候補
		}
		else {
			// midが解でないとき、さらに小さな解を探索
			right = mid; // midは答え候補じゃない
		}
	}

	std::cout << left << std::endl;

	return 0;
}

コードを書くにあたってのポイントは以下
・解の二分探索
leftを解の候補とし、rightをあり得ない値とする
そのため、rightがleft+1よりも大きい限り、二分探索を繰り返していく

・minAiがK回以下で実現可能か否かの判定
今回、結局Aiをval以上にするために、何回iを加算すればいいかを考えればいい

また、Judge関数の中で、以下のようにminをとっている
理由は、min処理を適用しない場合、N(2x10^5)のループ内でdiff(最大値 2x10^18)の加算が行われるため
このように、大きな値が蓄積される場合は、気を遣ってあげる必要がある

		num += (diff + (li - 1)) / li;
		num = std::min(num, K + 1);  // オーバーフロー防止