2022-03-08 アルゴリズムと数学 演習問題集 075 - Pyramid を解いた
アルゴリズムと数学 演習問題集 075 - Pyramid を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bi
例題。愚直に二重ループしてしまうと O(N^2) で N <= 2 * 10^5 という制約なので間に合わない。何かしらの工夫が必要になる。昨日 (2022-03-07) と同じだ。
a b c d
a+b b+c c+d
a+2b+c b+2c+d
a+3b+3c+d
まず係数部分に注目する。ある数が何回足されるかはそこから一番上までの経路の数になる。ピラミッドは斜めなので分かりにくいが、右上への移動を上、左上への移動を左と考える。こう考えると下に並んだ各点から左上の点へ移動すると考えられる。上への移動はどれも N - 1 回で左への移動は左端なら 0 回で右端なら N - 1 (i 番目の点からは i - 1) 回だ。ここまで来れば 051 - Combination Hard (2022-02-23) と同じだ。 _{N-1}C_{i-1} (1 <= i <= N) で係数部分が求められる。
係数部分が求められればあとはそれぞれに A_i を掛ければ良い。
\sum_{i=1}^{N}{_{N-1}C_{i-1}A_i} 。 O(N) 。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29956619
今日のコミット。