結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-16 21:14:16
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
TLE  
実行時間 -
コード長 3,461 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 385 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 18,468 KB
最終ジャッジ日時 2025-12-03 23:32:37
合計ジャッジ時間 5,858 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# -*- coding: utf-8 -*-
"""
Max Weighted Floor (mwf) を求める。
"""


def mwf(n: int, m: int, a: int, b: int, c: int, d: int) -> int:
    """
    Max Weighted Floor (mwf) の非再帰実装。
      mwf(n,m,a,b,c,d) = max_{0 <= x < n} a*x + b*floor((c*x + d)/m)

    前提:
      - n > 0, m > 0

    計算量/メモリ:
      - 時間: O(log m)（ユークリッド互除法的再帰による構造縮約）
      - 追加メモリ: O(1)
    """
    assert n > 0 and m > 0
    sum_acc: int = int(0)  # 現在の累積和
    max_acc: int = b * (d // m)  # 現在の累積max. 初期値は x = 0 のときの値
    while True:
        # c, d をそれぞれ 正の整数 m で割った剰余にする正規化
        # Python の divmod は Flooring Division に基づくので、除数 m が正であるため
        # 元の c, d が負でも正規化後の剰余は 0 <= c < m, 0 <= d < m が保証される
        # 負の整数 % 正の整数 = 負の整数 となる言語（C++/Java など）では移植時に注意
        qc, c = divmod(c, m)  # qc = c // m, c = c % m
        a += b * qc  # c の商分を a に足す
        qd, d = divmod(d, m)  # qd = d // m, d = d % m
        sum_acc += b * qd  # d の商分を sum_acc に足す
        # 以降は 0 <= c < m, 0 <= d < m が保証される
        assert 0 <= c < m and 0 <= d < m
        # 0 ≤ x < n における y = floor((c*x+d)/m) の最大値 y_max を計算
        # c > 0, n > 1 のときにのみ y_max >= 1 となりうる
        y_max = (c * (n - 1) + d) // m
        # 現在の小問題における x = 0, n-1 のときの値を max_acc に反映
        max_acc = max(max_acc, sum_acc, sum_acc + a * (n - 1) + b * y_max)
        # x = 0, n-1 のいずれかで最大値を取るのが確定したら終了
        if y_max == 0 or (a >= 0 and b >= 0) or (a <= 0 and b <= 0):
            return max_acc
        # 小問題へのパラメータ変換
        if a < 0:
            sum_acc += a + b
        n, m, a, b, c, d = y_max, c, b, a, m, (m - d - 1)
        assert n > 0 and m > 0 and c > 0 and d >= 0


def mwf_lr(L: int, R: int, m: int, a: int, b: int, c: int, d: int) -> int:
    """
    max_{L <= x < R} a*x + b*floor((c*x + d)/m) を計算して返す。

    既存の mwf(n, m, a, b, c, d)（0 <= x < n）を用いる。
    前提: L < R, m > 0
    計算量: 既存の mwf に準ずる（O(log m) スタイルの再帰）。
    """
    assert L < R and m > 0
    n = R - L
    q, d = divmod(c * L + d, m)
    return a * L + b * q + mwf(n, m, a, b, c, d)


def min_of_mod_of_linear(n: int, m: int, a: int, b: int) -> int:
    """
    min_{0 <= x < n} ( (a*x + b) % m ) を計算して返す。

    (a*x + b) % m
      = a*x + b - m * floor((a*x + b)/m)
      = b - ( -a*x + m*floor((a*x + b)/m) )

    これは b - mwf(n, m, -a, m, a, b) を求める問題に帰着する。
    前提: n > 0, m > 0
    https://judge.yosupo.jp/problem/min_of_mod_of_linear
    """
    assert n > 0 and m > 0
    return b - mwf(n, m, -a, m, a, b)


def solve():
    """
    入力を受け取り、各ケースについて mwf(N, M, A, B, C, D) を求めて出力します。
    """
    import sys
    input = sys.stdin.readline

    T = int(input())
    for _ in range(T):
        N, M, A, B, C, D = map(int, input().split())
        assert 1 <= N
        assert 1 <= M
        ans = mwf(N, M, A, B, C, D)
        print(ans)


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