初手の発想

abc192_d

問題は、条件を満たす n 進数の種類を求めることだと考えました。

ならば、方針は

1. X の中で一番大きな数を探す。
2. 「X の中で一番大きな数 + 1 」より大きな数を探索して、条件を満たす n 進数を探す。まず、n 進数として考えたとき、X の差上位桁のみから評価して、条件を満たすか確認し、最大の n を探す。
3. 上で探索した n について、X を n 進数として考えて時に条件を満たすか確認する。条件を満たさないときは、n を徐々に小さくして、条件を満たす n を探す。
4. 条件を満たした最大の n と X の一番大きな数の差が答えである。

と、考えました。 (そもそもここの考察が浅い。)

提出したコードは、初手の発想に沿っています。

提出コード

check 関数は、n と文字列 X、数値 M を受け取り、文字列 X を n 進数とみなした際に数値 M 以下であるとき true、M より大きなときに false を返します。

main 関数では、まず、文字列 X 中の最大の数字を探索します。

次に X の最上位桁のみを確認しながら、n 進数の条件を満たす最大の n を探索します。

次に X を n 進数としたときに X が M 以下であるかを確認し、M 以下でないならば、n を小さくし、条件を満たすまで探索します。

間違い

発想自体は大きく間違ってはいないのですが、提出コードにはいくつも問題があります。
上からチェックしていきます。

まず、最上位の桁のみを見て条件を満たす n 進数の最大の n を探すループについて、X が 10 の時、このループは、ほぼ M 回実行されます。したがって最悪ケースで 10**18 回実行されるので TLE します。

また、X が 1 桁の場合に対応できていないので、X=0, 1 の差に無限ループします。

次に最上位以外も確認して条件を満たす n 進数を探すループについて、初期の提出では、条件を満たすまで n を小さくしていたので、条件を満たす数が 0 この時に答えが合いません。

また、ans を int 型で取っているので、X=11, M が非常に大きなときにオーバーフローし、答えが合いません。

修正

諸々の修正をしたのが以下のコード

まず、X が一桁であった場合は 0, 1 のどちらかが答えになるので、回答を出力して終了する処理を追加します。

また、条件を満たす最大の n の探索は 2 分探索にしました。

教訓

最大計算量の見積もりが甘い。

また X が 1 桁のコーナーケースも WA をもらった後に自力で気が付くことができたので、しっかり考察すればできたはずです。

コンテスト中の思考

まず、初手の発想の通りの考え方をしました。

しかし、テストケースの 3 番目が処理できず。
数値を追っていくと、3 の 59 乗が long long に収まらないことに気が付きました。
この部分を処理して提出しました。

最初の提出では、WA と TLE を食らったので、高速化を考えます。
「探索が遅いのだから、2 分探索にすれば早くなるはず。」 と考えて実装。 ここは詰まらずにできました。

TLE は減ったものの、まだ TLE が出ます。
どうやら、答えが 0 のことだってあり得るはずなのに、そこの処理をしていないことに気が付きました。 このせいで無限ループに陥るプログラムになっていることに気が付いたので、処理を加えます。

TLE は処理できたものの、WA は取り切れません。

まだコーナーケースがあるのか？ と考えて、X が 1 桁であった場合に気が付きました。
が、残り時間が 1 分を切っています。 急いで実装を行うも間に合わず。

コンテスト後に実装したものを提出しましたが、まだ WA が出ます。

で、いろいろ考えて、ans の型が悪いことに気が付いて、解説を見るよりも前に AC はできました。

実力ギリギリの問題で、コンテスト中の気がせいてしまう精神状態を制御できれば AC できそうに感じて、非常に悔しいです。難しい発想は必要なくて、丁寧に考察して実装していけば何とかなりそうな問題です。

ただ、今のままでは無理なのもわかっています。コンテスト中に解ける問題が実力です。焦らないために、余裕で解けるように精進します。 C++の実装速度も上げなければ… 途中で python に逃げたくなりました。

あと、数値は何種類か？と聞く問題の尋ね方がうまいな。 と思います。
一瞬、解が発散しそうに思いましたが、よく考えればわかるうまさ。