ABC174 E問題の考え方

ABC174 E問題 - Logs の考え方を書きました。

問題を理解する

• 丸太の本数Nと、丸太の長さリスト A = [A_1, A_2, ... , A_N] が与えられる。
• この丸太をK回、分割する。
• かしこく分割することで、「どの丸太も○○メートル以内におさめました！」という状態にしたい。
• 最短で何メートル以内を達成することができるか、出力せよ。

例

N = 5
A = [1, 3, 2, 1, 2]
K = 4

このとき、以下のように丸太を K=4 回 分割することで、「どの丸太も 1 メートル以内におさめました！」を達成することができる。

これより短くすることはできないので、この例では 1 と出力すれば正解となる。

制約を確認する

変数名	意味	値の範囲
N	丸太の本数	1 〜 200000 (2x105)
Ai	丸太の長さ初期値	1 〜 1000000000 (109)
K	カット回数	0 〜 1000000000 (109)

• 入力は全て整数
• 答えは小数点以下を切り上げた値で出力すること
• 2秒以内に答えを出力すること

解法1（単純な方法・TLE）

「現状最も長い丸太を選んで、切る回数を1増やす」をK回繰り返すと、答えにたどり着く。
プログラム風に記述すると、以下のようになる。（細かい変数は省略）

丸太リスト[]

class 丸太 {
    初期長さ = Ai
    切る回数 = 0
    function 現在の長さ() {
        return 初期長さ/切る回数
    }
}

function main() {
    # 入力受け取り
    丸太リストを作成
    # シミュレーション
    K回繰り返す {
        対象の丸太 = 最も長い丸太を取得()
        対象の丸太.切る回数 += 1
    }
    # 解答
    最長の丸太 = 最も長い丸太を取得()
    print(最長の丸太.現在の長さ())
}

function 最も長い丸太を取得() {
    ID = 1 〜 N について {
        丸太リスト[ID].現在の長さ()
    }
    return 最も長かった丸太
}

しかし、この実装ではシミュレーション部分のループ回数が膨大になってしまう。

K回繰り返す { # 10^9 ループ
    ID = 1 〜 N について { # 2*10^5 ループ
    }
}

この二重ループでは、必ず K * N 回のループ処理が実行される。
最悪ケース（つまり、N, K どちらも最大値）では
2*10^5 * 10^9 = 2*10^14 = 200000000000000 回のループ処理が発生する。

仮に、1GHzのCPUが1クロックにつき1回ループ処理を行えたとしても、 200000秒 … 2日以上かかってしまう。

「動作の早いC言語なら…」というレベルではないので、 2秒以内 という制約に間に合うよう、アルゴリズムを改善する。

解法2（少し工夫・TLE）

発想を転換する。

考え方

1. 答えを一発で求めるのは難しそうだ。
2. 答えを探索によって求められないか？
3. 答えは、必ず 1 〜 max(A) の範囲内にある
   • 何回分割しても、0にはならない（小数点以下切り上げ）
   • max(A) = 初期状態の最大長 は、分割前から達成しているため、確実に達成可能

「最短で何メートル以内を達成することができるか」ではなく 「Cメートル以内を達成することができるか」ならば、N回以内のループで判定できる。 （Cメートル以内になるように、一括で分割していくことができるため）

そこで、

• 1メートル以内は可能か
• 無理なら、2メートル以内は可能か
• 無理なら、3メートル以内は可能か
• …

短い方から順に試していき、最初に「可能」と判定されたラインが答えとなる。

解法1と同様に、最悪ケースのループ回数を見積もってみる。
工夫により、答えが 1 となるとき（図の一番下のラインのとき）は、ループ回数 N = 200000 回で答えを出力できるようになった。
しかし、答えが max(A) のとき（図の一番上のラインのとき）は、ループ回数が N * max(A) = 200000000000000 回 と、まだ多すぎる。

解法3（AC）

解法2では、初めて「可能」となるラインを特定するために、max(A)回のループ処理を行なっていた。ここを高速化したい。

「ある数直線の範囲内に存在する境界線を特定する」という処理は、 二分探索 というアルゴリズムによって高速に実現できる。

まずは、ちょうど中間地点について実現可能かを判定してみる。

答えが存在する範囲のちょうど中間地点について達成可能かを調べ、範囲を狭めていくことを繰り返す。

可能と不可能の境界を特定できたら、最終的な「可能」のラインが答えとなる。
ループ回数は N * log2(max(A)) で、6000000回 程度となる。

解法の比較

	計算量	最大ループ回数のイメージ
解法1	O(K * N)	200000000000000 くらい
解法2	O(N * max(A))	200000000000000 くらい
解法3	O(N * log(max(A)))	6000000 くらい

回答例

• Ruby (2.7.1)
  • 実行時間 : 397 ms
• Python (3.8.2)
  • 実行時間 : 502 ms