AtCoder AGC 029 C - Lexicographic constraints

問題リンク

解説

解が1となる場合を考えます。

解が1となるのはAが狭義単調増加の場合のみです。

以下、解が2以上である場合を考えます。

明らかに解に単調性があるので二分探索です

解を Xとすると、文字列は X進数の数字と考えるのが簡単で、

  • A _ i \geq A _ {i + 1}のとき

    • S _ {i + 1} = (S _ {i} の上A _ {i + 1}桁を取り出したもの) + 1

  • A _ i \lt A _ {i + 1}のとき

    • S _ {i + 1} = S _ {i} X ^ {A _ {i + 1} - A _ {i}} (要するに S _ {i}の後ろに 0を A _ {i + 1} - A _ {i}個つけた)

これを愚直にやれば、TLEしてしまいますが、 X >= 2なので A _ {i} \leftarrow min(A _ {i}, 100)として問題ないです(高々 nしか増加しないので繰り上がりが起こらない)

以上で解けました！

提出コード

atcoder.jp