結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-15 01:13:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,505 bytes
記録
コンパイル時間 778 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-12-03 23:32:23
合計ジャッジ時間 6,528 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env pypy3
# -*- 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 など）では移植時に注意
        q, c = divmod(c, m)  # q = c // m, c = c % m
        a += b * q  # c の商分を a に足す
        q, d = divmod(d, m)  # q = d // m, d = d % m
        sum_acc += b * q  # 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 or b == 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)


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