2022-03-03 アルゴリズムと数学 演習問題集 066, 067 を解いた
アルゴリズムと数学 演習問題集 066 - Three Cards を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bd
例題。差が K 以上のものを数えると間に合わない。余事象である K 未満のものを数えて全体から余事象を引いて求めると良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29824904
アルゴリズムと数学 演習問題集 067 - Cross Sum(★2) を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_d
競プロ典型 90 問の 004 と同じ問題。各マスについて縦横を毎回走査して計算すると O(HWHW)
になり間に合わない。そこで先に行の和・列の和を求めておきそこから交わっている二重に足している値を引けば良い。 O(HW)
なので間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29824987
今日のコミット。