Atcoder Beginner Contest 192 D – Base n WAからの脱却

初手の発想

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に逃げたくなりました。

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

コメント

タイトルとURLをコピーしました