ABC相当のコンテスト。
結果
4完848位。 EとFが難しかったっぽい。 Dもわからなくて絶望しかけてたけどなんとかコンテスト中に解法を思いついたのでレートの暴落は回避されHighest更新。
A - Number of Multiples
単純に指示された範囲の整数に対してdの倍数かどうかを判定して数えれば良い。 指示された範囲内だけ正確に列挙できるようにループの書き間違いには気をつけよう（1敗）
提出 #15146161 - エイシング プログラミング コンテスト 2020
……というふうにコンテスト中は書いたが、1からxまでのdの倍数の数はx/dで求められるので、 R/d−(L−1)/dのようにすればO(1)で求められると思う。
B - An Odd Problem
普通に条件を満たしているマスを数えれば良い。
提出 #15149181 - エイシング プログラミング コンテスト 2020
C - XYZ Triplets
x2+1以上の数≤n⇒x<√nより、 x,y,z<√n≤√N≤√104=102。 なのでx、y、zの3重ループをx,y,z≤102 くらいの範囲で回してやればx2+y2+z2+xy+yz+zx の値が問題に出てくる範囲の数字になる組み合わせは全列挙できる。 これは十分間に合うので、最初に固定長の3重ループで答えのテーブルを作って、入力に合わせてその値を読んでくれば良い。
提出 #15155662 - エイシング プログラミング コンテスト 2020
D - Anything Goes to Zero
popcnt(n)≤log2nなので、f(n)の値はけっこう小さくなりそうな予感がする。 なので単純に何回操作が可能かシミュレートすればいいのだが、普通にやると入力が大きいのでオーバーフローする。 N≤2×105なので、最初の操作で値は普通の整数型に収まるようになる。 そのため2回目以降の操作は定義どおりに計算してもいいはずだが、1回目だけは特別な工夫が必要。
まずpopcnt(X)をループで1を数えて計算する。 1箇所ビットを反転させたらpopcnt(Xi)=popcnt(X)±1 になる。 Xの上からiビットめが1の場合、Xi%popcnt(Xi)=(X−2N−1−i)%popcnt(Xi)で、 Xの上からiビットめが0の場合、Xi%popcnt(Xi)=(X+2N−1−i)%popcnt(Xi)である。 popcnt(X)、X%popcnt(Xi)=X%(popcnt(X)±1)をO(N)で事前に計算しておけば、 powmodを使ってO(logN)で1回目の操作を行った後の値を計算できる。
あとは愚直にシミュレートしてやれば良い。 popcntが標準ライブラリにあると非常に楽。
提出 #15171056 - エイシング プログラミング コンテスト 2020
E - Camel Train
わかりそうでわからない
F - Two Snuke
まったくわからない