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

4完。面白かったけどこのセットを100分でやるのはもったいないよー(2時間にしてくれ(なおその20分でパフォーマンスは下がるだけだったと思われる))。

A - Number of Multiples

愚直。R以下のdの倍数の個数からL-1以下のdの倍数の個数を引けばいいだけなのだが、最近こういうの思いつかなくなった。

B - An Odd Problem

添字の偶奇が反転してることに注意。

C - XYZ Triplets

どこにも正整数と書いてないので焦りながら式変形。((x+y)^2+(y+z)^2+(z+x)^2)/2 になるのでこれは非負だとわかる。ここで、1以上という条件を見落としていたことに気づく。はい。そもそも、xが100以上だとyも1以上なのでNを超えることは確定。問題の答えに寄与するのが高々100^3通りしかないので、それぞれfが1以上N以下ならカウントすればいい。

D - Anything Goes to Zero

不安でしょうがないのでまず通知欄の自分のツイートから__builtin_popcountllをコピペしてくる。問題文を読み進めると、使わないか?1回の操作で一気にXからlog(X)のオーダーまで小さくなるので、1個のf(X)だけなら愚直で求まりそう。また、0以上N以下のxについてf(x)を前計算しておくことも可能。問題はビット反転による変化が高速にわかるか。よく考えると、1回目の剰余を求める操作はpopcnt(X)+1かpopcnt(X)-1でしか行われない。よってその2つについてあまりを求めておく。いやこんなクソ長い2進法の数で割り算させるか?AtCoderで?と思い一旦Eに行った。

5分くらいして戻ってくると、単に指定modで2冪を求めるだけじゃんと気づく。実装へ。最後に前計算部分を書いたが、ここで__builtin_popcountllを使った。サンプル通らず。2冪を計算するところで向きが逆だった。文字列で数値を扱うとここが本当に面倒。またサンプル合わず、それの和を計算するところも逆にする必要があった。修正自体はすぐできて、AC。実装にかなりの時間を食われてしまった。こういうところで力の差が出る。

ところでここまで4問全て何かをカウントする問題。変数名を、A問題で使ったcでずっと固定していた(なんかいい)。

E - Camel Train

最初に読んだときはL>Rと誤読していた。しかし、しばらく考えていると、左に行きたいやつと右に行きたいやつを分けてしまって損しないことに気づく。1番目(左)の位置の争奪戦を考えると、単にL-Rが大きいものが取って損しないように思える。入れなかったらもうどこでも一緒(価値ゼロ)。しかし、もう少し先まで考えると1位じゃないとダメなやつが1位をとる必然性はなくて、3位以内じゃないとダメな価値の高いやつらが1,2,3位を独占するのが最善という可能性もある。難しいので、ここからFと交互に考えていた。

左から考えたり右から考えたりしたけど、どうもダメ。ここで、L-R(が正の人たちについて(ラクダは思い浮かべにくいんじゃ(人を思い浮かべていたわけでもないが)))の大きい順に空席があれば一番右のをとるという貪欲を思いつく。これ損しなくない?最初の人は高々1人の席を奪うだけだし。2番目以降も。あまり考えてないけど、この時点で残り17分とかだったので、他にできることもないし実装して時間を使う。空いてる一番右の場所はセグ木でわかりそう。BITでもいいかな(追記:BITだと更新ができないくさい)。いや思考停止でできるセグ木で。これ左右やるのに逆にする必要があるけど?2種類のセグ木を使うかあ。何とか1分前に書き上がったけどコンパイルが通らず終了。

コンストラクタを書いてないのにemplace_backを使うな(みんな使ってるので、自分のスタイルだと使うメリットがほぼないというのをいつまで経っても覚えない)。そして、右側も右端からの距離で(左側と)同じようにできるじゃんと気づいて書いていたためそもそも2種類のセグ木は必要なくなっていたのだが、そのことに気づいていなかった。それを修正し、まだサンプルが通っていない。

(追記)K=Nを左右反転させてK=1としていた(正しくはK=0)。制約でたまたまK=0が除かれているだけで、Kは0以上N以下と考えるのが自然だった。K=NのときはどうやってもRが選ばれないと気づいていたのに、軽視していた(ここは不自然だから忘れるなよと強く意識すべきだった)。

F - Two Snuke

N個の玉があり仕切りを10個入れる。いや、2個ずつの大小関係も条件にあるからかなり扱いづらい。しかも、最終的に2個ずつの差の積の総和が知りたいので、何を固定しても計算しづらそうに見える。