かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

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)か怪しい