AtCoder Beginner Contest 106
Updated:
Source codes
Solutions
A - Garden
$(A-1)(B-1)$ が答え。
B - 105
$1 \leq i \leq N$ のうち、奇数について、地道に約数を数え、 $8$ 個であればカウンタを回す。
C - To Infinity
$k = 0, \dots, \min(K, \lvert S \rvert) - 1$ に対し、 $1$ でない数を発見したら答えはその数字である。そうでないなら答えは $1$ である。
D - AtCoder Express 2
コンテスト中に思いついた解法
終点を index として、列車を vector<int> T[510]; 、質問を vector<tuple<int, int>> X[510]; で持っておく。あとは $r$ の小さい方から BIT を使えば良い。列車の方を add とみなし、質問の方を sum で返せば答えになる。
または $N \leq 500$ に注目し、 imos 法を使ってもよろしい。つまり $r = 1, \dots, N$ に対し、列車を追加、その後 $i$ の逆順に imos[r][i] += imos[r][i + 1];
を行い、その後 $i$ の順番に imos[r][i] += imos[r - 1][i]; とする。答えは imos[r][l] で求まる。
解説放送の模範解答
$N \leq 500$ であるから、実はどのクエリがどの順番で来ても imos 法で応答できる。 $1$-indexed とする。 $0 \leq l, r \leq N$ に対し、まず、
$imos[l][r] = $ 区間 $[l, r]$ を運行する列車の本数を最初に入れておき、後から累積和に変更する
とする。あとは $2$ 次元累積和を更新し、累積和 $\sum_{r \leq i \leq l} \sum_{r \leq j \leq l} imos[i][j]$ を $O(1)$ で求めるようにするだけである。
chokudai さんの実装の仕方が面白かった。 $i = 1, \dots, N$ に対し、 $j = 1, \dots, N$ に対し、 \[ imos[i][j] += imos[i - 1][j] + imos[i][j - 1] - imos[i - 1][j - 1] \] とする。私は $2$ 次元累積和は、縦方向と横方向を別々に実装すると思っていたので、これは盲点だった。あとはクエリ $[r, l]$ に対し、 \[ imos[r][r] - imos[l - 1][r] - imos[r][l - 1] + imos[l - 1][l - 1] \] を応答すればよろしい。ただし、今回の場合全ての列車に対し $l \leq r$ が成立しているので、実は \[ imos[r][r] - imos[l - 1][r] \] を応答すればよろしい。
以上の方法は実装が簡単で、間違いにくい。 AbemaTV で『劇場版 魔法科高校の劣等生 星を呼ぶ少女』を見ながら書いて一発 AC であったくらいである。
ポイント
模範解答については、 区間 $[l, r] \subset \mathbb{N}$ を点 $(l, r) \in \mathbb{N}^2$ とみなす という、私は初めて見る定跡を使う。これは $O(N^2)$ の空間が必要であるものの、柔軟で易しい実装が可能である。
模範解答ではないものの、 仮に $N \leq 10^5$ であれば「区間は終点でソートする」の定跡を使う問題である。 cf. 数え上げテクニック集 by DEGwer 氏の 3.3 節
類題は以下がある。
- AtCoder Beginner Contest 103 D - Islands War 区間 $(a, b)$ を $b$ の昇順にソートする。
- CODE FESTIVAL 2017 Final D - Zabuton $\{ P_i + H_i \}$ の順にソートする。
最後の実装に時間がかかってしまった。 $N$ が小さいから $r$ でソートせず配列で持てば十分だった。これに気づくまで時間がかかった。練習不足でした。
Others
A - sample: 2, tle: 2.000, time: 02:39, from_submit: 29:15
B - sample: 2, tle: 2.000, time: 01:51, from_submit: 27:24
C - sample: 3, tle: 2.000, time: 04:03, from_submit: 23:21
D - sample: 3, tle: 3.000, time: 23:21, from_submit: 00:00
解説放送の chokudai さんのラストの C# の実装のスピードを見て、いやもうこれ絶対勝てないわと思った。私がたまたま上位に食い込む ABC は、実装が早いのではなく、考える時間が極限まで 0 に近いだけである。