結果

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

ソースコード

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
    s: int = int(0)  # 現在の累積和
    r: int = b * (d // m)  # 現在の累積max. 初期値は x = 0 のときの値
    while True:
        # c, d をそれぞれ 正の整数 m で割った剰余にする正規化
        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
        s += b * q  # d の商分を s に足す
        assert 0 <= c < m and 0 <= d < m
        # 現在の小問題における x = 0 のときの値 s を r に反映
        r = max(r, s)
        # 0 ≤ x < n における y = floor((c*x+d)/m) の最大値を計算
        y = (c * (n - 1) + d) // m
        # y == 0 の場合は右端を考慮して終了
        if y == 0:
            return max(r, s + a * (n - 1))
        # y >= 1 の場合は再帰的に解く
        # c > 0, n > 1 のときにのみ y >= 1 となりうる
        if a >= 0:
            # a >= 0 の場合
            r = max(r, s + a * (n - 1) + b * y)
        else:
            # a < 0 の場合
            s += a + b
        # 小問題へのパラメータ変換
        n, m, a, b, c, d = y, 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