けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1610 竹の花 (ICPC 国内予選 2016 C) (250 点)

AOJ ICPC国内予選 調和級数 入力が定数個 Greedy Greedy:端から順に決まっていく 最大スコア AOJ-ICPC250点 AOJ-ICPC 最適化問題

面白い。けど問題文長い...。問題概要を短くまとめてみた。

問題概要

正の整数 M, N が与えられる。

あなたは、 M 以上の整数を N 個用意する ( x_{1}, \dots, x_{N} とする)。この N 個の整数のスコアを、以下の条件を満たす最小の整数 S として定める。

  • S \ge M
  • S は x_{1}, \dots, x_{N} のいずれでも割り切れない

N 個の整数 x_{1}, \dots, x_{N} を適切に定めたときの、スコア S の最大値を求めよ。

制約

  • 2 \le M \le 100
  • 1 \le N \le 5 \times 10^{5}

考えたこと

x_{1} \lt x_{2} \lt \dots \lt x_{N} であるとしよう。まず当然ながら

  • x_{1} = M

とするのがよい。さもなくばスコアは M となってしまう。さて、もし N = 1 ならばスコアは M+1 で確定となる。 N \ge 2 ならば、次に

  • x_{2} = M+1

とするのがよい。以後同様に考えて、次のようにするのが最適となる。

すでに x_{1}, \dots, x_{i} を決めたとき、これらの倍数とならない最小の整数を Y とする。このとき

x_{i+1} = Y

と定めるのがよい。

実装

具体的に実装するにあたって、あらゆる状況におけるスコアの最大値として考えられる上限を L としたとき、次のようなサイズ L+1 の配列を用意してあげる。

  • iscovered[ v ] := v がいずれかの x_{i} の倍数であるかどうか

x_{i} の値を新しく定めるたびに

for (int y = x; y <= L; y += x) iscovered[y] = true;

という感じに更新してあげれば OK。これは存外計算量が少なくて O(L \log L) の計算量となる。

L の見積もり

本来なら L を見積る必要があるところだが、サンプルに答えが書いてある (実際の問題文でもそれを見るように誘導されている)。

L = 7368791

であることがわかるので、これを使う。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 7500000;
int solve(int M, int N) {
    vector<bool> iscovered(MAX, false);
    int x = M;
    for (int iter = 0; iter <= N; ++iter) {
        while (iscovered[x]) ++x;
        for (int y = x; y < MAX; y += x) iscovered[y] = true;
    }
    return x;
}

int main() {
    int M, N;
    while (cin >> M >> N, M) cout << solve(M, N) << endl;
}