以下の内容はhttps://kanpurin.hatenablog.com/entry/2021/03/26/183746より取得しました。

ABC196 C - Doubled

ABC 解説競技プログラミング

${O(\sqrt{N})}$ 解法， ${O(\log{N})}$ 解法， ${O(1)}$ ？解法について解説します．

問題はこちら

問題概要

${1}$ 以上 ${N}$ 以下の整数 ${x}$ のうち，先頭に余分な0をつけない十進表記で偶数桁であり，前半と後半が文字列として一致するようなものは何個あるか．

${1\leq N < 10^{12}}$

解説

O(√N)解法

${x}$ を ${1}$ から ${N}$ まで全探索するのは間に合わない．この全探索では，各 ${x}$ について「前半と後半が文字列として一致する」という条件を満たすか調べる必要がある．そこで，そもそもこの条件を満たしている ${x}$ について探索を行うことができれば探索範囲を削減できる．前半と後半が等しいので，前半を決めることで条件を満たす ${x}$ のみについて全探索を行うことができる．

O(logN)解法

${O(\sqrt{N})}$ 解法の ${x}$ の探索において「 ${x\leq N}$ であるか？」の真偽が単調であることを利用して二分探索を用いることで最大の ${x}$ を求めることができる．

O(1)？解法

${O(\log{N})}$ 解法において最大の ${x}$ は，

${N}$ の長さが ${1}$ の場合， ${0}$ (例：3 -> 0)
${N}$ の長さが ${1}$ でない奇数の場合， ${99\cdots 9}$ (例：3141592 -> 999)
${N}$ の長さが偶数かつ「前半の数 ${\leq}$ 後半の数」の場合，前半の数字 (例：31415926 ->3141)
${N}$ の長さが偶数かつ「前半の数 > 後半の数」の場合，前半の数字-1 (例：314159 ->313)

提出プログラム

https://atcoder.jp/contests/abc196/submissions/21262672 ${O(\sqrt{N})}$ 解法
https://atcoder.jp/contests/abc196/submissions/21262749 ${O(\log{N})}$ 解法
https://atcoder.jp/contests/abc196/submissions/21262571 ${O(1)}$ ？解法

感想

本当にO(1)か怪しい

以上の内容はhttps://kanpurin.hatenablog.com/entry/2021/03/26/183746より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14