結果

問題 No.3422 Sazanka's hobby
コンテスト
ユーザー mentos_grape
提出日時 2026-01-11 14:03:20
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
TLE  
実行時間 -
コード長 4,759 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 675 ms
コンパイル使用メモリ 20,800 KB
実行使用メモリ 154,576 KB
最終ジャッジ日時 2026-01-11 14:03:40
合計ジャッジ時間 8,687 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 2 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math

sys.setrecursionlimit(2000000)

def solve():
    try:
        # 入力をリストで受け取る
        input_data = []
        for line in sys.stdin:
            try:
                input_data.extend(list(map(int, line.split())))
            except ValueError:
                break
        
        if not input_data:
            return

        # N, Mを取得し、残りのデータから植物の情報を抽出
        N = input_data[0]
        M = input_data[1]
        
        plants = []
        # インデックス 2 から始まる
        for i in range(2, 2 + 2 * N, 2):
            if i + 1 < len(input_data):
                a = input_data[i]
                b = input_data[i+1]
                plants.append((a, b))
            else:
                break
        
        if not plants:
            return

        # check関数: 仮定したkで雨漏りを防げるか判定
        def check(k):
            # 各植物がいつ天井に到達するかを計算し、日数のリストを作成
            # 日数は 1 から始まる（1日目の夜に成長、2日目の朝に取り除く判定）
            # ceil((M - a_i) / b_i) + 1 で夜を含めた日数を正確に計算
            # M - a_i <= 0 の場合は即座に到達とみなす
            
            # 各植物の限界までの猶予日数を格納
            deadlines = []
            for a, b in plants:
                if a >= M:
                    # 初期高さがすでにM以上の場合、即座に取り除かなければならない
                    deadlines.append(0) 
                else:
                    # 天井に到達するまでの日数を計算
                    # 1日目の夜に成長した結果、Mを超えるかを判定
                    # growth_needed = M - a
                    # days = ceil(growth_needed / b) if growth_needed > 0 else 0
                    # 例えば a=2, b=2, M=5 の場合、growth_needed=3, days=ceil(3/2)=2
                    # 1日目: 2 -> 4, 2日目: 4 -> 6 (超える)
                    # 猶予日数は 2
                    deadlines.append(math.ceil((M - a) / b))

            # 期限が早い順にソート
            deadlines.sort()

            # シミュレーション
            removed_count = 0
            for i, deadline in enumerate(deadlines):
                # deadline日まで（当日朝までに）取り除く必要がある
                # i+1 本目が必要な総除去本数
                # 経過日数は deadline - 1 (1日目朝からdeadline日目朝まで)
                # あるいは、i番目の植物がdeadlineまでに取り除かれていないといけない
                # 全ての植物を取り除く総数は N
                
                # ここでは期限までに取り除かれなかった場合にカウントする
                # deadline日目の朝までに取り除く必要がある
                # deadline日目までの総除去可能数: deadline * k (もし当日朝も除去できるなら)

                # 別のアプローチ：各期限までに必要な除去数を追跡する
                # ある期限 (d) が来たときに、それまでに必要な総除去数が
                # それまでの総除去可能数 (d * k) を超えていないかチェック
                
                # 期限が d の植物は、d 日目の朝までに取り除かれる必要がある
                # i 番目の植物の期限が deadlines[i]
                # 全体で i+1 本が deadlines[i] 日目までに取り除かれないといけない
                
                # ある時点での必要な除去総数（期限がその日以前の植物の数）が、
                # その時点までの合計除去可能数を超えていないか
                required_to_remove = i + 1
                available_removal = deadlines[i] * k
                
                # 注意: deadline が 0 の場合（即時超過）、k>0 であれば防げるはず
                # available_removal = 0 * k = 0
                # required_to_remove = 1
                # 0 >= 1 で False になり、k=0 では防げないことが確認できる

                if required_to_remove > available_removal:
                    return False
            
            return True

        # 二分探索
        left, right = 0, N
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        
        print(left)

    except EOFError:
        pass
    except ValueError:
        pass

if __name__ == '__main__':
    solve()
0