エイシングプログラミングコンテスト 2020の感想

（タイトル間違ってたのを修正。ABCではない。）
NoSub。Cから解くと決めていて、Cが解けなかった。

A

atcoder.jp
$1$ 以上 $x$ 以下の範囲にある整数のうち、 $d$ の倍数であるようなものの個数は $x\div d$ で求められる。累積和的な考えを使うと、答えは $R\div d - (L-1)\div d$ である。 $O(1)$
また、普通にループを使って $l$ 以上 $r$ 以下の整数を $d$ で割って行ってもOK。 $O(R)$ だが、制約が $R\leq 100$ なので余裕をもって間に合う。

B

atcoder.jp
ループを使ってすべての要素を見ていく。「前から奇数番目」と「 $a_i$ が奇数」を同時に満たす場合だけカウントする。奇数か否かは、 $2$ で割った余りで判定できる。一番最初の要素は $0$ 番目ではなく $1$ 番目である点に注意。 $O(N)$

C

atcoder.jp
問題文を見たとき、まず等式
$x^2+y^2+z^2+2xy+2yz+2zx=(x+y+z)^2$
を思いつくが、良い変形が思いつかず断念。
とりあえず愚直に解くことを考えると、各 $N$ に対して、変数 $x, y, z$ の値を決め打ちして実際に等式が成り立つならカウントを増やす、という解が思いつく。 $x, y, z$ の上限は指定されていないが、これらは全て正の整数なので、この変数のうちどれか一つでも $\sqrt N$ を超えると明らかに式が成り立たなくなる。よって $1\leq x, y, z\leq 100$ であることがわかる。愚直解の計算量は $O(xyzN)$ で、制約からだいたい $10^{10}$ 回の計算が必要となる。
ここで、 $x, y$ を決めると $z$ の値は一つに定まる（∵未確定の変数が1つしかない）ことを利用すると、式変形して
$z^2+z(x+y)+(n-x^2-y^2-xy)=0$
となり、この2次方程式の解を求めればよいことになる。

（追記：ここの式変形が間違っていた！！正しくは、
$z^2+z(x+y)+(x^2+y^2+xy-n)=0$
です。）

$z$ は $1$ 以上の整数であることに気を付けて実装すると答えが求まる。計算量が $O(xyN)$ 、制約から $10^8$ 回と（ギリギリではあるが）時間内に終わるよう改善された…

と思って実装したのだが、なぜか答えが合わなかった。

（追記：この解法でも一応882msで通りました。）
Submission #15187699 - AIsing Programming Contest 2020

フォロワーさんから聞いた解法を一応残しておく。一度 $N$ を考えず単純に $x, y, z$ を全探索して左辺の値を求め、その値が $1$ から $N$ の範囲内なら配列でカウントしていき、最後に配列の値を順番に出力すると計算量が $O(xyz)$ 、 $10^6$ 回で求まる。確かにこちらの方が計算量も少ないし、スッキリとした解法である…。

D

atcoder.jp
まず愚直解を考える。ある数 $X$ に対して、 $X$ → $popcount(X)$ は必ず減少する。さらに言うと、2進数で表現したときの桁数は $\log N$ だから、 $popcount(X)$ は最大でも $\log N$ である。余りをとる計算の性質から $popcount(X)$ で割った余りは $popcount(X)$ 以下になるので、一度の操作で大きさが $\log N$ 倍になる。
つまり、二進数で表現したときの桁数が $N$ であるような数 $X$ に対して、 $f(X)$ を求めるには $(N+\log N+\log \log N+\dots)$ 回桁を見れば良いことになる。まあ大体 $O(N)$ で求まると考えて問題ない。
全ての $X_i$ に対してこれをやると計算量は $O(N^2)$ となり間に合わないので、高速化を考える。
よく見ると、もとの数 $X$ と $X_i$ を比べると高々 $1$ bitしか違わない。ということは、 $popcount(X)$ と $popcount(X_i)$ も $1$ しか違わない。具体的には、 $popcount(X_i)$ の値は $popcount(X)+1$ か、 $popcount(X)-1$ かの2択である。どちらの値になるかは、 $i$ 桁目が $0$ か $1$ かを見れば決まる。
また、 $X$ をそのまま10進数に直そうとすると $10^{2^{100000}}$ というとてつもなく大きい数字になってしまうが、最後に余りをとることがわかっているなら、最初から余りをとった値を扱えばよい。具体的には、「 $X$ を $popcount(X)+1$ で割った余り」と「 $X$ を $popcount(X)-1$ で割った余り」のデータがあれば、「 $X_i$ を $popcount(X)\pm 1$ で割った余り」を $O(1)$ で求められる。あとは数字がそこまで大きくないので、素直に操作を繰り返すことで $f(X_i)$ の値を $O(\log N)$ で求められる。
これを $X_i$ の個数分（ $N$ 回）繰り返すので、全体の計算量は $O(N\log N)$ となる。 $popcount(X)-1$ が $0$ になる場合、余りの計算が出来ないので例外処理を書く必要がある。