区間和は「累積和の差分」で考えてみましょう。水色diff です。 問題 数列 の区間 で が の倍数であるものの数を求めよ。 制約 考察 の累積和 を計算し、 とします。 求める値は、 の剰余の数列 で、同じ値が何度出てくるかの総和と等しくなります。 Python…

「条件を手で計算してみる大切さ」を教えてくれる問題です。 ソートしてからナップサックDPで解けます。 問題 種類の活動の中から つ以上を選び、好きな順序で行なう。 最初の体力は であり、活動 を行うと、得点 を得た後、体力が 減少する。 得られる得点…

ワーシャル・フロイド法の理解を問う問題です。 緑diffです。 問題 を 頂点 辺の有向グラフ、 を から へ頂点番号 以下の頂点のみ経由したときの最小距離とする。 を求めよ。 制約 考察 全点間の距離なので、計算量 のワーシャル・フロイド法が思いつきます…