結果

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

ソースコード

diff #
raw source code 

import sys
import math

sys.setrecursionlimit(2000000)

def solve():
    try:
        # 入力をリスト形式で読み込む
        data = []
        for line in sys.stdin:
            try:
                # 複数行にまたがる可能性を考慮して、スペースで分割して追加
                data.extend(map(int, line.split()))
            except ValueError:
                break
        
        if not data:
            return

        # N, Mを取得し、残りのデータからaとbのリストを作成
        N = data[0]
        M = data[1]
        
        a = []
        b = []
        # インデックス2から開始
        for i in range(2, 2 + 2 * N, 2):
            if i + 1 < len(data):
                a.append(data[i])
                b.append(data[i+1])
            else:
                break # データが足りない場合は終了
        
        if len(a) < N:
            # 入力形式の問題などがあればここでハンドリング
            pass

        # 特定のkで植物が生き残れるかを判定する関数
        def can_survive(k):
            # 高さがMを超えるまでの日数を格納するリスト
            days_to_exceed = []
            for i in range(N):
                # 既にMを超えている場合、1日目に取り除かないとアウト
                if a[i] >= M:
                    days_to_exceed.append(0)
                # 成長速度が0または非常に遅く、絶対にMを超えない場合（問題の制約ではb_i >= 1なのでこのケースはないが、一般的には考慮）
                # else:
                #     continue
                # Mを超えるまでの日数を計算 (ceil((M - a[i]) / b[i]))
                else:
                    days = math.ceil((M - a[i]) / b[i])
                    days_to_exceed.append(days)

            # 高さMを超えるまでの日数が少ないものから優先的に処理するためソート
            days_to_exceed.sort()

            # 各日数で取り除くべき本数をカウント
            # j日目に取り除かなければならない植物の数
            remove_count = {}
            for d in days_to_exceed:
                # 0日目（初日からアウト）は特別なケース
                day_index = d if d > 0 else 0
                remove_count[day_index] = remove_count.get(day_index, 0) + 1
            
            # 各日 j における取り除き処理のシミュレーション
            removed_total = 0
            # 0日から最大の日数までシミュレーション
            max_day = days_to_exceed[-1] if days_to_exceed else 0
            for j in range(max_day + 1):
                # j日目の朝に、これまでに取り除いた合計が不足していないかチェック
                # j日目に超える予定の植物があれば、その数だけ取り除かなければならない
                if j in remove_count:
                    # その日までに取り除かれた本数(removed_total)が
                    # j日目にMを超える植物の数(remove_count[j])以上必要
                    if removed_total < remove_count[j]:
                        return False
            
            return True

        # 二分探索で最小のkを見つける
        # kの範囲は0からNまで
        left, right = 0, N
        ans = N # 答えをNで初期化

        while left <= right:
            mid = (left + right) // 2
            if can_survive(mid):
                ans = mid
                right = mid - 1 # kをもっと小さくできるか試す
            else:
                left = mid + 1 # kを大きくする必要がある

        print(ans)

    except EOFError:
        pass
    except ValueError:
        pass

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