2022-03-15 アルゴリズムと数学 演習問題集 086, 087, 088 を解いた
アルゴリズムと数学 演習問題集 086 - Parentheses Check を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bp
例題。有名な典型問題。スタックのように考えると良さそう。 ( で push ) で pop する。 empty のとき pop するなら No 。最後にスタックが empty でないなら No 。そうでなければ Yes 。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30149208
アルゴリズムと数学 演習問題集 087 - Simple Math Easy を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bq
\sum_{i=1}^{N} \sum_{j=1}^{N} ij を求める。
分配法則から \sum_{i=1}^{N} i \sum_{j=1}^{N} j と変形できる。 \sum_{j=1}^{N} j の部分は等差数列の和なので (1 + N) * N / 2 で求められる。これを S とする。 \sum_{i=1}^{N} iS 。分配法則から S \sum_{i=1}^{N} i 。 \sum_{i=1}^{N} i は先ほどと同様に S になる。つまり S^2 を求めれば良い。 10^9 + 7 で mod を取るのを忘れないようにする。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30149733
アルゴリズムと数学 演習問題集 088 - Simple Math を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/arc107_a
ARC107 A と同じ問題 (https://atcoder.jp/contests/arc107/tasks/arc107_a) 。
考え方は 087 - Simple Math Easy と同じ。 N がそれぞれ A B C に分かれているけど分配法則で \sum の外に出すことと等差数列の和を求めることを繰り返すだけで良い。 f(x) = \sum_{i=1}^{x} i とすると f(A) * f(B) * f(C) を 998_244_353 で mod をとったものが答えになる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30149824
今日のコミット。