累積和クラスを作ってみた

作成動機

• 元となる配列サイズ+1で作ったり、範囲の和を取る時に添え字でミスりそう
• いつも同じ作成をしているので省略したい

Code

struct AccSum{
    vector<ll> Ac;
    ll L;
    AccSum(vector<ll> &A){
        L = A.size();
        Ac.resize(L+1);
        FOR(i, 0, L){
            Ac[i+1] = Ac[i] + A[i];
        }
    }
    // sum of [a, b]
    ll sum(ll a, ll b){
        if(a<0) return -1;
        if(b>L-1) return -1;
        return Ac[b+1] - Ac[a];
    }
};

動作確認

https://atcoder.jp/contests/abc124/submissions/4982319

追記：簡単な累積和の書き方

• partial_sumというのがある
• 添字がずれるのが慣れない

int main(){
    // input
    VI A = {1, 8, 2, 3, 7, 4};

    ll N = A.size();
    VI acc(N+1);
    partial_sum(ALL(A), acc.begin()+1);

    debug(A);
    debug(acc);

    // 2-4までの和 (2+3+7=12)
    ll sum = acc[5] - acc[2];
    p(sum);

    return 0;
}

[A]: {1, 8, 2, 3, 7, 4}
[acc]: {0, 1, 9, 11, 14, 21, 25}
12

C - Infinite Grid

Quiz

https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c

Submit

https://atcoder.jp/contests/s8pc-6/submissions/4981908

解法

• editorialの通り

感想

• 100個くらいつなげて到達可能なら行けそう
• 迷路で到達可能かどうか、ということで幅優先で解いたらTLEだった
  • https://atcoder.jp/contests/s8pc-6/submissions/4981854
  • 190点/400点 まではもらえた
• editorialのようにdpで解いたらAC

学び

• 迷路は可能ならdpで解くべし

(自分的)落とし穴

bool dp[R][C]; // 到着可能か
FOR(i, 0, R){
    FOR(j, 0, C){
        dp[i][j] = false;
    }
}

• フラグは初期化しよう
• 1次元フラグだといつもvectorを使うので初期化は省略できるが、今回は2次元だったので配列で書いたら初期化を忘れていた

最短経路の本 レナのふしぎな数学の旅

No.390 最長の数列

Quiz

https://yukicoder.me/problems/no/390

Submit

https://yukicoder.me/submissions/19573

解法

• 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした
• 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした
• 約数の列挙は計算量がO(N)
• 各 i について列挙を行うのでO(N log N)な気もするが、列挙に時間がかかるのは最後の方だけなのでもっと小さい気もする
• O(N log N)だった場合は、今回はN=10⁶ (値のmax) なので、この見積もりだと10⁹となりTLE
• しかし実際にACしたということは
  • 計算量はO(N log N)より小さい
  • テストケースが全部小さい
• のいずれかであるが、テストケースを見ると前者のようだ

約数列挙

• ミスで同じ約数が入るのを避けるため、今回はsetに入れてみた

set<ll> factorization(ll N){
    set<ll> se;
    for(int i=1; i*i<=N; i++){
        if(N%i==0){
            se.insert(i);
            se.insert(N/i);
        }
    }
    return se;
}

3つ組を重複なしで数える tuple + set

用途

• (1, 5, 3)と(1, 3, 5)は同じものとして数えたいのでsetに入れて重複除去したい
• 値が3つあるのでpairには収まらない
• そこでtuple!

Submit

https://yukicoder.me/submissions/338555

Code

#include <tuple> // new !
set<tuple<ll, ll, ll> > se;
se.insert(make_tuple(a, b, c));
se.size()

このように使う。コンパイルはオプションが必要

g++ -std=c++11 answer.cpp

Codeforces Round #551 (Div. 2) サーバルセット

A. Serval and Bus

• https://codeforces.com/contest/1153/problem/A
• 解法
• サーバルがバス停に着く時刻 t 以降（ちょうども含む）で最初に来るバスを各ルートごとに求めればよい

B. Serval and Toy Bricks

• https://codeforces.com/contest/1153/problem/B
• 解法
• H[i][j] = min(frontから見た高さ, leftから見た高さ)

C. Serval and Parenthesis Sequence

• https://codeforces.com/contest/1153/problem/C
• 解法
• 各文字の数を数えれば、残りいくつ ( を使えるかが求まる
• ?が来たら(を優先的に使う
  • )を使うとcorrectになってしまう可能性があるため
• (を使い切ったら残りは ) で埋める
• カウント count を取っておく
  • ( が来たらcount++
  • ) が来たらcount--
• 最後以外でカウントが0になってしまうと correct になってしまい条件を満たさない
• 最後まで埋めれたら count == 0 であることをチェックして完了

D. Serval and Rooted Tree

• https://codeforces.com/contest/1153/problem/D
• 解けず。解法待ち
• 木DP? dfs?

感想

• Dは解ける気がしなかったが解説は読みたい
• いつもはみんなDiv1に行ってるんだけど今日はDiv2のみだったのでこちらに参加していたようだ
• レート青 (1600以上) になった。Expert!

その他

• こどふぉは毎回1万人近く参加している需要のあるサイト。レスポンスを速くしてほしい