今日作る料理をレシピ本で決めてそのレシピをスマホで写真撮っていって材料買いに行こうと思ったら、材料の名前は写ってたけどそれぞれの量が見切れてて致命的だなとか思ったことはどうでもよくて、おはようございます、まがりかどです。
そんなことより今日はARC116のB問題、Products of Min-Maxの解説をしていきます。
ARC116B問題をぱっと見た感じ
Aの空でない部分列Bは\(2^n – 1\)個あります。
と問題文に書いてあるのでまあ愚直にやったら時間計算量は\(O(2^N)\)以上はかかるんだろうなって思いますね。
さらに部分列Bを決めたときに、Bの最大値と最小値を求める必要があるのでそこにも線形時間がかかります。
ここで制約を見てみると\(1 ≦ N ≦ 2 \times 10^5\)とかいてあるので指数時間でやってしまうと人生が終わってしまうのでなにかしら工夫が必要そうです。
最終的な出力を\(ans\)としています。
計算量削減
ソートによりminとmaxをしなくてよくする
この問題では部分列Bを決めたときに、Bの最大値と最小値を求める必要がありますね。
これは普通にすると部分列Bを決定するたびに\(O(|B|)\)かかってしまいます。
しかし昇順にソートしておけば部分列Bを決定したとき左端が最小値、右端が最大値になるので\(O(|B|)\)は不要になります。
最小値と最大値を固定する。
入出力例を見てみると２が最小値で４が最大値として計算されているのが２回あります。
これは次のように説明できます。
2 3 4
ソート後の数列はこうなっているはずです。
\(B\)の左端、つまり最小値を２にしてさらに右端を４にするとき真ん中の３を\(B\)に含めるか否かで\(2^1\)通りあります。
間に二つある場合だと\(2^2\)です。
よって\(B\)の左端が２で右端が４のときについて、出力\(ans\)には\[ans\text{ += }2 \times 4 \times 2^1\]とすればよいでしょう。
一般的には左端が\(i\)番目、右端が\(j\)番目とすると、\(2^{j – i – 1}\)通りあり\(ans\)については\[ans\text{ += } A_i \times A_j \times2^{j – i + 1}\]となるでしょう。
ただし\(i = j\)のときは１通りです。
式変形してみる
上の方針に従って\(ans\)を一つの式にまとめてみましょう。
ここで\(B\)の長さは１でもよくて\(i = j\)のときは無条件に１通りということに注意します。
\[ans = 2 \times 2 + 2 \times 3 \times 2^0 + 2 \times 4 \times \ 2^1 +
3 \times 3 + 3 \times 4 \times 2^0 + 4 \times 4\]
ここで最小値が同じ場合についてまとめてみると
\[ans = 2(2 + 3 \times 2^0 + 4 \times 2^1) + 3( 3 + 4 \times 2^0) + 4 \times 4\]
一般的には、（添え字は１から）
\[ans = A_1(A_1 + A_2 \times 2^0 + A_3 \times 2^1 + ・・・+ A_N \times 2^{N-2}) + \\
A_2(A_2+ A_3 \times 2^0 + A_4 \times 2^1 + ・・・+ A_N \times 2^{N-3}) + \\
・・・A_{N-1}(A_{N-1} + A_N \times 2^0) + A_N \times A_N ・・・ ①\]
となるでしょう。
この数式を求めるには、まず項が\(N\)項あり、さらに一項の中に最大で\(N\)項あるのでこれは愚直に求めれば\(O(N^2)\)にかかります。
制約を見ると\(1 ≦ N ≦ 2 \times 10^5\)なのでちょっと間に合わなさそうですね。
漸化式でもとめる
上の①の式のかっこの中を見てみるとなんか\(i\)項目と\(i + 1\)項目がなんかちょっと似てるように見えませんか？
私には見えます。
そうです。
このかっこのなかは漸化式で求めていくことができます。
漸化式で求めていくときは最初は少ないほうがいいので\(N\)項目から\(１\)項目にかけて求めていきます。
ここで入出力例１にもう一回着目してみます。
入出力例１の１項目と２項目のかっこのなかは
\[2 + 3 \times 2^0 + 4 \times 2^1\]
\[3 + 4 \times 2^0\]
かっこの中の一項目は常に\(A_i\)と等しく、係数も\(2^{i-j+1}\)ではなく変則的なのでこれは最初にひいておいてほっておきます。
すると\(i\)項目のかっこの中を\(val_i\)としたら漸化式は
\[val_N = A_N\]で、
\(1 ≦ i ≦N – 1\)のとき
\[val_{i} = \frac{(val_{i+1} – A_{i+1})}{2} + A_i + A_{i+1}\]
となります。
これで\(O(N)\)で求められます。
計算のたびに\(mod\)を取ることに注意しましょう。
ARC116 B問題 B – Products of Min-Maxの解答
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 998244353;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (lint i = 0; i < (lint)(n); i++)
int main(){
lint n;
cin >> n;
vector<lint> a(n);
rep(i, n) cin >> a[i];
sort(all(a));
lint ans = 0;
lint div = a[n-1];
for(int i = n - 1; i >= 0; i--){
ans += a[i] * div;
ans %= mod;
div -= a[i];
div *= 2;
div %= mod;
div += a[i-1] + a[i];
div %= mod;
}
cout << (ans + mod) % mod << endl;
}これで出来上がりです。
良ければこの色変記事もどうぞ
ありがとうございました。
