Atcoder Beginner Contest 192 D - Base n WAからの脱却
初手の発想
問題は、条件を満たす n 進数の種類を求めることだと考えました。
ならば、方針は
- X の中で一番大きな数を探す。
- 「X の中で一番大きな数 + 1 」より大きな数を探索して、条件を満たす n 進数を探す。まず、n 進数として考えたとき、X の差上位桁のみから評価して、条件を満たすか確認し、最大の n を探す。
- 上で探索した n について、X を n 進数として考えて時に条件を満たすか確認する。条件を満たさないときは、n を徐々に小さくして、条件を満たす n を探す。
- 条件を満たした最大の 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 に逃げたくなりました。
あと、数値は何種類か?と聞く問題の尋ね方がうまいな。 と思います。
一瞬、解が発散しそうに思いましたが、よく考えればわかるうまさ。