そろそろ8問体制のABCにも慣れてきました。(まあ解ける問題数は変わんないんだけど...)
ただ今回は全体的に問題の難易度がならされていて、C, D問題も比較的簡単だった気がします。(直大さんもそういう主旨のツイートをしていました。)
ABC作問に関わってないけど、８問コンテストの予定で言うと、過去４回で、上振れ・上振れ・上振れ・ちょうど良い、って感じで、ようやくちょうど良い感じのが来て安心してる。たまには下振れてもいいのよ。
— chokudai(高橋 直大)🍆 (@chokudai) August 21, 2021
今回は4完2WAでレートが712(+42)になりました。最近調子が良くてウレピイです。
特に言うことはないです。こういう問題はテストケースを確認しないで提出していいと思うのですが、タイプミスが怖いので結局全部試してから提出してます。
いやちょっと言い訳させてほしいんですけど、題名ひどくないですか？？
という訳で題名どおりにfloor(log2(N))を出力したらWAになってしまいました。どうやらfloor(log2((long double)N))だと耐えるらしいです。
このように順当に累乗していく解法の他に、上からbitを見ていって初めに立っているbitのある場所が答え、というのがめちゃくちゃスマートな解法でびっくりしました。(全く思いつかなかった...)
文字列の辞書順の並べ替えはnext_permutationを使うというのを知っていたのですぐに実装できました。やはり過去問ゲーですね。
僕は それぞれのAの要素について素因数列挙して潰す→その倍数も全て互いに素にはならないないので潰す という方針で進めました。
素因数列挙の所はA / i = jだった時にiとjを同時に列挙することで上限をsqrt(A)にすることができます。(エラトステネスの篩)
実行時間は素因数分解の部分でO(N√maxA)、倍数列挙のところでO(NloglogN)、最後の判定でO(M)なので全体では1番大きい項のO(N√maxA)だと思います。(間違ってたらごめんなさい)
N = 10^5、maxA = 10 ^ 5だと最大でループが10 ^ 7.5回回ることになるので結構厳しめの制約ですね。
1度実装が重くてTLEを出してしまいました。2度目で通ったのですが、442msだったので割とぎりぎりでした。
(よく見たら最後の配列名resじゃなくてrepにしてる...)
今回は4完できたのでとりあえずは満足です。この調子で沼らずに緑まで行きたいです。