124. AtCoder参加記録（AtCoder Beginner Contest 259）

28回参加でレート 1328 です。

今回はパフォーマンス 1348です。

ABCEを通して、GExは未解答です。D, Fは通せず。Cで1ペナ、Eで1ペナ。

各問題の思考過程など。

A

5分9秒。

いつもと違って問題文を読むだけでは状況整理が困難だったので、数直線を使って考えました。0歳のときの身長を出して、そこから逆算するような方法を取りました。

B

4分53秒。

回転行列適用するだけか…これ中高生可哀想な問題では、と思いつつ、ラジアン変換周りで何故かバグを埋めたりで若干時間がかかりました。悲しい。

C

初回提出4分35秒、そこからACまで2分20秒。

ランレングス圧縮して色々考えればよさそう。

圧縮後のリストサイズが異なっていればNG
そうでない場合、順番に圧縮後の要素を見ていって
1. 文字の種類が異なればNG
2. 連続数が等しければ次の要素を見に行く
3. $S$ 側の連続数が1なら操作できないのでNG
4. $S$ 側の連続数が $T$ 側より多ければ、減らすことはできないのでNG（ここで 1WA）
ここまでNGが出てなければOK

D

初回提出6分16秒。5WA で正答に至らず。

円の交差判定は「円の内側にすっぽりはまっている」「円同士が交差している」「それ以外」を見ればOK。各円同士を見るのも $O(N^2)$ で十分。あとは、円同士が同じ連結成分に属していればよいので Union-Find でくっつけていけばよい…と分かってはいましたが、誤差にやられました。

冷静に考えると、2乗距離で判定すると浮動小数点数を避けられたんですね…。というか、いつもならこちらで考えていたのに何故か今日は sqrt を使ってしまいました。無念。

E

初回提出22分50秒、そこからACまで5分40秒。

LCMがどのようになるか考察すると、すべての $p_{i, j}$ について $e_{i, j}$ の最大指数を採用したものの積になります。つまり、ある $i$ について $a_i = 1$ に書き換えたならば、 $a_i$ を構成する素数の指数が先ほど考えた最大指数と等しければ、LCMは変化します。ただし、厳密には他の $a_j (i \ne j)$ で、同じ素数について最大要素がある場合はそれが残るので、その素数については変化しません。

以上より、まずはこの前計算を行います。

各 $p_{i, j}$ について、 $\max e_{i, j}$ と、 $e_{i, j} = \max e_{i, j}$ であるような要素数 $c_{p_{i, j}}$ を求める。
各 $p_{i, j}$ について、HashSet $S_p$ に $p_{i, j}$ を追加する。
$c_{p_{i, j}} \ne 1$ である $p_{i, j}$ は $S_p$ から除去する。

あとは、「何種類あるのか？」の判定ですが、指数の変化する素数集合の種類数を見ればよいので、Zobrist-Hash を使うと楽です。

HashSet $S_{ans}$ を用意する。
を走査する
1. ハッシュの集合 $S_h$ を用意する。
2. を走査する
  1. $S_p$ に $p_{i, j}$ が含まれる、かつ、 $e_{i, j} = \max e_{i, j}$ であれば、 $S_h$ に $H(p_{i, j})$ を追加する。ここで、 $H$ はハッシュ関数。
3. $S_h$ の Zobrist-Hash を $S_{ans}$ に追加する。
$S_{ans}$ のサイズが答え