AtCoder Beginner Contest 250 参加記

ooooo---

A 問題。場合分けをするのは厳しそう。四方のマスが存在するかをそれぞれ調べればよい。

B 問題。丁寧にループを回す。チェック柄は $($ 列番号 $+$ 行番号 $)$ の偶奇で色分けすればよい。

C 問題。$B[A[i]]=i$ となる配列を用意すると、クエリで動かすべき場所が分かる。右端のときは左端と swap すると思ってしまい時間をかけた。

D 問題。$q\le 10^6$ が言えるので $q$ を固定して全探索。$q$ の昇順に調べれば $p$ は今までに出てきた素数すべてが適するので、素数の個数も数えておけばよい。素数判定には atcoder::internal::is_prime_constexpr が便利。

E 問題。これ、hash 使わずに解けるのか？？と思っていた。解けるらしい。hash をいくつか考えて、hack されたら嫌なのですべて実装。結局 sum,product,xor を管理した。区間の左端が固定されているので、$2$ 回目以降に出てきた要素は無視してよいことに注意。任意の区間に対する hash 解が存在するらしいが、要素の重複を回避する方法が分からない。

F 問題。PCK 本選の過去問に 同様の問題 がある。しゃくとり解法はすぐに思いついたがバグを埋め込んで破滅。$2$ 本のベクトルが作る三角形の面積を計算するのに $10^{32}$ を超える精度が必要な方法を選択してしまい、$\sqrt{*}$ の精度のために自前二分探索を書いて TLE もいくらか出た。その後の upsolve でなんとか AC。

G 問題。ちょっとだけ見た。見たことのある雰囲気の問題だった。priority_queue が使えそう。

Ex 問題。見てません。