2022-03-18 アルゴリズムと数学 演習問題集 094, 095, 096, 097 を解いた
アルゴリズムと数学 演習問題集 094 - Maximal Value を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc140_c
ABC140 C と同じ問題 (https://atcoder.jp/contests/abc140/tasks/abc140_c) だ。
B_i が A_i と A_{i+1} の上限になる。ふたつの上限が重なっている箇所はより小さい側が上限となる。 A_i を B_i の上限である 10^5 で初期化しておき B を走査して A_i と A_{i+1} との MIN をそれぞれとることで上限を更新していけば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30205499 解説: https://atcoder.jp/contests/abc140/editorial
アルゴリズムと数学 演習問題集 095 - Score Sum Queries（★2） を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_j
競プロ典型 90 問の 10 日目と同じ問題 (https://atcoder.jp/contests/typical90/tasks/typical90_j) だ。
Q 回 L..=R を走査して合計を求めると間に合わない。
そこで累積和を使って区間和を求める。 S_R - S_{L-1} で区間和を求められる。組分けがあるので累積和を 2 つ持っておけば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30205740 解説: https://twitter.com/e869120/status/1380652465834532865
アルゴリズムと数学 演習問題集 096 - Cooking を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc204_d
ABC204 D と同じ問題 (https://atcoder.jp/contests/abc204/tasks/abc204_d) だ。以前は本番で通せなかったようだけど今日は通せた。
各料理について 2 つのレンジのいずれかに振り分ける。最終的な 2 つのレンジの合計時間はどう振り分けても変わらない。なので一方の時間が分かれば他方も合計時間から引くことで分かる。ここから各料理の時間の組み合わせで実現できる時間が振り分けの候補になる。つまり N = 100 から単純な組み合わせで考えると 2^100 だけど N = 100 T_i <= 10^3 という制約から実際には 10^5 通りしかない。危なそうな計算量だけど N 回最大 10^5 通りの計算を試しても 10^7 くらいだし実際には重複は無視できるのでそれよりも小さいはず……という考察で通せた。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30206752 解説: https://atcoder.jp/contests/abc204/editorial/2013
アルゴリズムと数学 演習問題集 097 - Primes in an Interval を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt
エラトステネスの区間篩 (ふるい) というものらしい。
R <= 10^12 の制約だけど時間制約的にはエラトステネスのふるいによる素数の列挙は O(√N) なので間に合う。問題は空間制約で 10^12 のメモリは確保できない。
ここで R − L <= 500000 といういかにも怪しい制約に注目する。 10^6 までの数の素数判定と L..=R の区間の数を持てば素数判定ができる。L..=R の区間の数値は素数であるか 10^6 までの素数からなる合成数である。問題は L..=R の素数判定をあたかも続いているかのようにできるかどうかだ。
ここでぼくは諦めて他の人の提出を見た。
10^6 までの素数 (p) で mod p を取る。 L (mod p) を使えばふるいをかける開始位置が分かる。あとはエラトステネスのふるいと同様に p ずつ合成数だとマークしてふるいにかける。
注意が必要なのは 10^6 と重なる位置。特にぼくは 1 のケースを見落としていてサンプルがなかなか通らなかった (逆に気づけるようサンプルケースに入れてある点で優しい) 。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30209717
今日のコミット。