bouzuya.hatenablog.com

ぼうずやのにっき

アルゴリズムと数学 演習問題集 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


今日のコミット。