久々のratedコンテストに出た。
SRM811 Div1 Med SmoothDivisors
考察過程
- 1及び、単一の素因数からなる整数は条件を満たす。
- 逆に条件を満たさない整数について考えてみる。
- $p$ を素数として、$ p _ {1} p _ {2}$ や、$p _ {1} ^{2} p _ {2}$ のような整数は条件を満たさない。
- $p _ {1} p _ {2} p _ {3}$ , $p _ {1} ^{3} p _ {2}$ , $p _ {1} ^{2} p _ {2} ^ {2} $ は条件を満たし、これらの条件を満たす状態に素数を追加しても条件を満たすことが分かるので、結局除くのは上の状態だけで良い。
技術室奥プログラミングコンテスト#6 Day1
H問題まで解いた。
D. ABS SUM
累積和の引き算の形に変形すると、
$$ \sum _ {i = 1}^{N} \sum _ {j = 0}^{i - 1} | s _ {i} - s _ {j} | $$
という値を求めることになって、これは配列をソートしておくことで正負の寄与分が簡単に分かる。
E. And Xor Or
bit の動きについて観察すると、結局スコアは $A _ {i} \mathbin{\mathrm{AND}} A _ {j}$ の2倍になる。
上位桁から使う桁を固定していく貪欲で解くことができる。
ARC125
B. Squares
$x^{2} - y = p^{2}$ とする(ただし $ p $ は非負整数)。
$1 \leq y \leq N$ より、$1 \leq (x + p)(x - p) \leq N $
$0 \leq p \leq N$ の範囲で動かした時に、上の不等式を満たす $ x $ の個数の総和を求めれば良い。
$p$ の値を固定した時に取りうる $x$ の最大値を、$ x _ { max } = p + m $ とすると、上で述べた条件を満たす $ x $ の個数はこの $ m $ に一致する。
ここで $ m $ の値を固定し、その値を取る $ p $ の個数を数える方向性に切り替える。
これは最初に示した不等式 $1 \leq (2p + m) m \leq N$ から簡単に求めることができる。調べる $ m $ の範囲は $O(\sqrt{N})$ 程度なのでこれで間に合う。
D. Unique Subsequence
問題を簡単にするため、始めに数列の先頭と末尾に番兵を入れて、その2要素を必ず通る部分列を数え上げることにする。
$A _ i $ から $ A _ j $ に遷移できる条件として、$[i + 1 , j -1]$ の範囲に $A _ i$ または $ A _ j$ が存在してはいけない(存在したら明らかに部分列の選び方は一意に定まらない)ことが挙げられる。
逆にこれを繰り返し得られた部分列は条件を満たす。
これをDPすれば良い。貰うDPで考えると、BITなどで高速化でき、$O(NlogN)$ で解くことができる。
August Cook-Off 2021 Division 1
INTEREQ
左から要素を決めていく。もし頻度が1のままだったら、初めて出た要素なのでそこで一意に定まりindexを集合に加えておく。そうでなければ二分探索により要素を決定する。
