blog.bouzuya.net

2022-05-26 AGC057 の A を解いた

AGC057 : AtCoder Grand Contest 057 の A を解いた。

  • A - Antichain of Integer Strings https://atcoder.jp/contests/agc057/tasks/agc057_a
    • 提出: https://atcoder.jp/contests/agc057/submissions/31962141
    • R <= 10^9 から単純に操作したり全件を前処理することはできない
    • T <= 10^4 から 1 件につき O(logR) くらいならいけそう
    • 解説 AC
    • 解説を読めば解けるけど自分では難しい
    • f(x) を長さ n の x を部分文字列として含む最小値と定義すると MIN(10x, 10^n+x) となる
      • 先頭に 1 つけるか、末尾に 0 つけるかのうち小さい側
    • f(x) は狭義単調増加になることから二分探索が使える (ここが難しい)
    • L <= x <= R で f(x) > R となる個数を求めると良い
    • それ以上右側に部分文字列として含むものがないものを選ぶ……ということだと思う
    • f(x) > R を ok として範囲を求める
    • x = R は ok
    • x = L は試してみて ok なら R - L + 1 個、 ng なら二分探索する

暑い。

bouzuya/rust-sandbox clap を入れてサブコマンドを定義している。もうすこしで使える状態かな。

今日のコミット。