はじめに $2 \leq x$を満たす整数$x$に対して、$x$の 最小素因数（least prime factor） とは、$x$の素因数のうち最小のものを指します。 同様に、$x$の 最大素因数（greatest prime factor） とは、$x$の素因数のうち最大のものを指します。 （※名称はOEISに沿って設定しました。 lpfのページ gpfのページ ）

個数制限付きナップサック問題 $N$種類の物がある。$i$種類目の物は重さ$w _ i$、価値$v _ i$、個数$c _ i$個である。 ナップサックの容量を$V$とするとき、容量制限を守った上でナップサックに入れる物を選び、合計価値を最大化せよ。

前提 API Documentationはversion 2.

はじめに AWC0008D - 果樹園の収穫 を$O(N(\log N + \log (\max F _ i)))$時間で解きます。要は$M \leq 10 ^ 9$でも解ける解法ということです。 解説で言及されているので新規性はないです。

はじめに 小ネタです。全人類知っているかもしれませんが、私は比較的最近知ったので共有します。 以下、モノイドは$(M, e, \times)$を考えます。

はじめに 今回は ABC441F - Must Buy を題材にして、ナップサック問題の最適解を与える操作列を復元する手法を解説します。

問題 $N$次多項式$A(x) = A _ N x ^ N + A _ {N - 1} x ^ {N - 1} + \dots + A _ 0$ $M$次多項式$B(x) = B _ M x ^ M + B _ {M - 1} x ^ {M - 1} + \dots B _ 0$ $N + M$次多項式$C(x) = A(x)B(x) = C _ {N + M} x ^ {N + M} + C _ {N + M - 1} x ^ {N + M - 1} + \dots + C _ 0$ がある。$A(x), C(x)$が与えられるので、$B(x)$を求めよ。

まえがき 毎年恒例の年末エントリ。 今年で3年目です。 2023年版と2024年版を見たことある人はこのブログのプロ名乗っていいですよ。

はじめに 本エントリは 電通大プログラミング教室 Advent Calendar 2025 の13日目です。

はじめに 本エントリは 電通大プログラミング教室 Advent Calendar 2025 の8日目です。 少々用事がありまして公開がクソ遅くなりました。JSTで8日中なのでセーフという説にかけます。