Mister雑記

競プロやります。

ARC099-C 「Minimization」 (300)

与えられた情報が全て必要とは限らない。

問題リンク

概要

数列 (1, 2, \dots , N)の順列 A_iがある。 この数列に対して以下の操作を何度か行うことで、全ての要素を同じにしたい。

  • 連続する K個の要素 A_i, A_{i + 1}, \dots A_{i + K - 1}を選ぶ。
  • これら全てを、その中の最小値で置き換える。

このとき、必要な操作の最小回数を求めよ。

制約

  •  2 \leq K \leq N \leq 10^5

解説

まず数列 A_iが数列 (1, 2, \dots , N)の順列であるということを見逃すとどツボにハマる。 というのも、この条件から全要素の最終的な値が1であることが決まるからだ。これは、1という要素はどのような操作を行っても消すことができないことから明らかである。

では実際にどういった操作をすればいいのか。結論を言ってしまうと、操作をした区間全体の集合は、

  • 区間の和は途中で途切れてはならない
  • 区間の和は数列全体を覆っていなくてはならない

という2つを満たしていなければならない。

これは、上の操作を「区間全体に最小値を広げる操作」と考えると直感的にもわかりやすいだろう。各条件が満たされていないと、

  • 区間が区切れているところから先に1を広げることができない
  • 覆われていない要素に1を広げることはできない

ことになり、条件を達成することができない。

逆に、上の2条件さえ満たされていれば適用順序を工夫することで必ず全要素を1にできる。具体的には、1が含まれている区間から順番に操作していけばいい。

抽象的すぎて分からないという方は、以下の図が参考になれば幸いである。

f:id:misteer:20180627095750j:plain

では実際に答えを求めよう。区間の数=答えだから、区間同士の重なりは1にするのが最も効率的である。このとき、 m個の区間が覆える範囲は [1, (K - 1)m + 1]となる。これが区間 [1, N]を覆っていればいいわけだから、答えは

 (K - 1)m + 1 \geq N \Leftrightarrow m \geq \dfrac{N - 1}{K - 1}

を満たす最小の mとなる。これは、右式右辺の分数を切り上げることで計算できる。

回答例

#include <iostream>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    cout << (N + K - 3) / (K - 1) << endl;
    return 0;
}

 a \div bの切り上げは、 (a + b - 1) / bで計算できるため、上のような式で答えが求まる。

そして今まで見てきた通り、答えは N Kのみに依存していて具体的な数列の要素は一切不要である。こういう場合、上のように標準入力を受け取らずにコードを終了しても問題はない。

感想

  • こういう「実は入力は使いませーん」っていうタイプの問題好き。
  • 実は最初に勘違いで1WAを吐いているので、提出には慎重にならねばと悟った。
    • 実際この回はDが難問だったのでこのミスが大きく響いた。