Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

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

A - Number of Multiples

R以下の整数でdの倍数の個数からL-1以下の整数でdの倍数の個数を引くという算数をしてもよいですし、LからRまでの範囲を全部調べるでもよいです。

私は過去の反省から、ノータイムで全探索を選びましたw 算数でしくじったら目も当てられません。

B - An Odd Problem

これこそループを回して1からNまで全部を調べればよいです。

C - XYZ Triplets

一瞬「うっ」となりそうな問題文です。

しかし、二番目の式をよく見ると、それがNの条件10000以下を満たすためには、x, y, z がそれぞれ100未満でないといけないことが分かる(100の2乗だけで10000に達してしまう)ので、100 * 100 * 100通りの全探索をすればよいだけの問題であることがわかります。

結局ABCのCは全探索のCという最近の傾向そのまんまでした。

D - Anything Goes to Zero

Xに対する剰余はO(N)で求まりますが、それを逐一やってしまうとそれだけで2 * 10^5の2乗となってしまい間に合いません。何か工夫する必要があります。

私は、前計算でX % (popcount(X) - 1)X % (popcount(X) + 1)をやっておいてから

  • 1が0になる反転のときは2 ^ (n - 反転位置 - 1) % (popcount(X) - 1)を前者から引く(それにさらに剰余を取る)
  • 0が1になる反転のときは2 ^ (n - 反転位置 - 1) % (popcount(X) + 1)を前者に足す(それにさらに剰余を取る)

をすることで、一回目の処理の答えを求めました。あとは充分小さい数になるので愚直に計算すればOKです。

要するに、反転前の数と反転後に増える(減る)数とに分解して、別々に計算したということです。

文章にすると何言ってるかわからないかもなので、ソース見てください。ソースも実戦のものなので相当汚いですけど・・・。

Submission #15179061 - AIsing Programming Contest 2020

E - Camel Train

残り5分でどうしろと・・・。

F - Two Snuke

見てません。

まとめ

いやー、コンテスト本番で発揮される底力は本当に侮れませんね。すんでのところで冷えを回避できました!

Cの全探索を初見で気づけなかったのは若干反省点ですが、まあ2分もロスしていないのでとりあえずはよいです。

f:id:mdstoy:20200711230925p:plain