競プロ日記#25/04/13

アルゴ式-総和クエリ (1)

• 最初はDPみたいな感じを考えたが、解説にもある通り所詮は最大でkパターンの質問しか来ないため最初からk-1までのk個の総和を用意しておく。
• その際にあるi + 1についての総和を求めるためにiまでの総和を使えばよい

// あらかじめ回答を用意しておく
vector<int> acc(N+1);
for (int i=0; i<N; ++i) {
    acc[i+1] = acc[i] + A[i];
}

アルゴ式-総和クエリ (2)

• 誘導に乗れば簡単。
• 総和クエリ (1)と同様にあらかじめNまでの和を求めて回答を用意しておく

int N;
cin >> N;

vector<int> A(N);
for (int i=0; i<N; ++i){
    cin >> A[i];
} 
// あらかじめ回答を用意しておく
vector<int> acc(N+1);
for (int i=0; i<N; ++i) {
    acc[i+1] = acc[i] + A[i];
}

int Q;
cin >> Q;
for(int i = 0;i < Q;i++){
    int l,r;
    cin >> l >> r;
    cout << acc[r] - acc[l] << endl;
}

アルゴ式-繁忙期

• 以下の通りロジックを組んだのだがイマイチ通らない。（REとWAどっちも）

int N,D;
cin >> N >> D;

vector<int> vecX(N);

for (int i = 0;i < N;i++){
    cin >> vecX[i];
}

vector<int> acc(N - D);
for (int i = 0;i < N - D + 1;i++){
    for (int j = 0;j < D;j++){
        acc[i] += vecX[i + j];
    }
    
}

int max = 0;
int ansS,ansT;
for (int i = 0;i < N - D + 1;i++){
    if (max <= acc[i]){
        max = acc[i];
        ansS = i;
        ansT = i + D - 1;
    }
}
cout << ansS << "~" << ansT << endl;

• 解説によると以下の様になるらしいがあまり納得いかない。

// acc[i] = 日 0 から 日 i より前までの合計来場者数
vector<int> acc(N+1);
for (int i=0; i<N; ++i) {
    acc[i+1] = acc[i] + X[i];
}

// max_sum = 答えとなる期間の開始日
// max_period_visitor = 日 max_sum を起点とする連続した D 日間の合計来場者数
int max_start = 0;
for (int i=0; i<N-D+1; ++i) {
    int period_visitor = acc[i+D] - acc[i];
    if (period_visitor >= max_period_visitor) {
        max_start = i;
        max_period_visitor = period_visitor;
    }
}

// max_end = 答えとなる期間の終了日
int max_end = max_start + D - 1;

// 出力
cout << max_start << "~" << max_end << endl;
return 0;

• 普通に考えれば二重ループになっている部分に問題がありそうだがWAが出るのは謎
• でもこれも通らない。というかそもそもCE。max_period_visitorの定義不足らしいが定義しても結局WA。解説のコードがWAって意味わからん過ぎる。