2020-08-18 ABC084 / かんぺぴ
ABC084 考察
ABC084 A - New Year
12 月 31 日の 24 時間と 12 月 30 日の M 時以降の (24 - M) 時間を足した 24 + (24 - M) を求める。
https://atcoder.jp/contests/abc084/submissions/16012834
ABC084 B - Postal Code
先頭から A 文字までは数字 A + 1 文字目は - それ以降は数字の形かを調べる。
A + 1 文字目の - だけを判定して残りがすべて数字かを調べても良かったかもしれない。正規表現を組み立ててマッチさせるなどの方法もありそうだ。
https://atcoder.jp/contests/abc084/submissions/16012852
ABC084 C - Special Trains
N 個の駅ごとに N 駅までの走査によるシミュレーションを繰り返すと O(N^2) になる。 N <= 500 なので指示通りにシミュレーションするこの方法で間に合う。
https://atcoder.jp/contests/abc084/submissions/16012928
ABC084 D - 2017-like Number
1 <= l_i, r_i <= 10^5 から N <= 10^5 で Q <= 10^5 なので O(NQ) では間に合わない。そこで l_i <= N <= r_i における x の個数を求めるのに累積和を使う。 1 <= j <= 10^5 について x の個数を累積和 S として保持しておき S_{r_i} - S_{l_i - 1} で x を求める。
10^5 までの素数を求めるのにエラトステネスの篩を使うと O(N^2) よりは小さいはず。累積和をつくるのは O(N) 。各クエリは O(1) 。クエリの合計で O(Q) 。素数の列挙が一番時間がかかるはずだけど間に合う。
https://atcoder.jp/contests/abc084/submissions/16012998
4 完だ。
リングフィットアドベンチャーを続けている。
育児。昨日書きそびれていたけど子どもの「かんぺぴ（完璧）」が印象的だったのでメモしておく。