ABC433 D 問題：「難しそう」でも手を止めないための記録

はじめに

ABC433 の バーチャルコンテストに参加し A, B, C 問題の 3 完と相成りました。
悔しかったのは D 問題が解けなかったことで、ヒントを少し見たらあっさり解けて拍子抜けしました。つまり、私は 「難しそう」という印象に引きずられて手を止めてしまっていました。
本記事では自分がコンテスト中にどう思考停止したのかを言語化・分析し、「難しそう」な問題に対する対策を考えました。

今回引っかかった D 問題

問題全文：ABC 433 D - 183183

実際にコンテスト中に考えたこと

以下、この問題に対する初見の反応と行動を述べていきます。

直感的な反応

まずタイトルを見て 「嫌だ！」 と思いました。難しかった 183184 問題 を連想したからです。
私はこの手の「数を文字列として結合して新たな数を作る」タイプの問題に強い苦手意識があります。外見は”文字列っぽい”のに、往々にして数学的な発想が問われるからです。

問題文から読み取って注目したポイント

制約が非常に厳しいです。数列 $A$ の個数 $N$ が最大で $2 \times 10^5$、数列の各要素 $A_i$ が最大で $10^9$、剰余に使うであろう $M$ が $10^9$ といずれも大きく、単純に全探索することはまず不可能です。
また $i, j$ の組み合わせについて順序を区別する必要があるため、単純な組み合わせよりも管理すべきパターン数が多くなります。

当時思い浮かんだアイデア

• まずは倍数判定をすればいいということで $\mod M$ を取って集計すればよさそうだと考えました。
• 2 数を文字列と見て結合し新たな数を得る操作 $f(x, y)$ は、$y$ の桁数を $d$ として $x \times 10^d + y$ を計算することと言い換えられます。
  • すなわち、なんらかの $k$ に対して $A_i \times 10^k \bmod M$ を求めればいいはずです。
• DP 的なアプローチも考えましたが、$A_i \bmod M$ の種類が $10^9$ 通りになるのでは？ と推測（誤解）しました。
• ここから二分探索などの $\mathcal{O}(\log M)$ で済むアルゴリズムなど、もっとスマートな方法を模索し始めました。

結果として取った行動

ここまでで「おそらく発想問題なのだ」と判断し、Blute-force による実装をためらってしまいました。
また、小規模な問題から解いてみるということも頭になく、最初からすべてを解こうとしか考えていませんでした。
結局、私は 50 分近くの時間を残しながら 「3完でいいや」と諦めた のです。おなかもすいたし。

なぜ解けなかったのか

以上から、なぜ解けなかったのかを分析してみます。

外観的要因

• タイトルから難易度の高い過去問を連想した
  • 過去問の難しさとこの問題の難しさはほとんどの場合関係ありません。
• 制約の厳しさを必要以上に意識した
  • 初めから厳しい制約を見据えるのではなく、制約を緩めた小問題を考えると解法が見えてくることがあります。
• 数え上げパターンの多さに萎縮した
  • パターンが多いことと難しさはイコールではありません。この問題の場合はむしろ $x < y$ の条件下で $f(x, y)$ を数えるほうがややこしくなります。

認知的要因

• 「余りが $10^9$ 通りあるので最悪 $10^9$ 個の要素を管理しなければならない」と思い込んだ
  • 実際には余りの種類は要素数 $N \le 2 \times 10^5$ で押さえられるため、辞書型などで十分管理できました。

心理的要因

• 自分の能力に対する自信のなさ
• ゼロから発想するのは厳しいという諦めの気持ち
  • 結果として十分に試行錯誤できず、気づきを得る機会を逃してしまいました。

その他の要因

• ごはん食べてなかった（重要）
  • 実際問題、空腹は頭の回転を鈍らせます。

コンテスト後の考察

しばらく考えた後に公式解説を読んだところ、そこでは「辞書型で数え上げる」という方法が取られていました。ここでようやく「管理すべき余りの数が最大で $10^9$ 通りある」という誤った思い込みに気がつきました。

この問題を解くうえで必要なポイントは以下の 2 点でした。

• 左側の数 $A_i$ は右側の数 $A_j$ の桁数に応じて $\bmod M$ の値が変わります。よって、結合のためにずらす桁数 $k$ に対して $A_i \times 10^k \bmod M$ の個数を辞書型で事前集計することで、$A_i$ を左側に置いたときの $\bmod M$ の個数を右側の数 $A_j$ の桁数から高速に求められます。
• 最終的に和が倍数になればいいので、$A_i \times 10^k + A_j \equiv 0 \pmod M$ となるパターン数を $A_j$ ごとに数え上げれば解が得られます。

実は 当時思い浮かんだアイデアで十分に考察できていた のに、正解に近づいていることを信じられなかったのです。

今回得られた学び

1. 問題の外観に萎縮しない

問題の難しさと本質的に関係のない部分で萎縮してしまうと、問題文の読み解きや考察に悪影響が出ます。
たとえば文字の多さ、制約の厳しさ、類題で苦戦したという記憶などは必ずしも問題の難しさを左右しません。
特に制約の厳しさについては、それ自体がヒントとなる場合もあります。

2. とにかく具体例を手計算する

手計算している間に、直観的に理解しやすい構造に気がつける可能性があります。少なくとも何もしなかったら思いつくこともありません。
与えられた入力例を問題文のとおりに計算するだけでも問題の意図が理解しやすくなります。

3. 試行錯誤すれば着実に前進できる

たとえば制約の緩い問題を解いてみるというのは試行錯誤の方法の一つです。その解法を工夫すればスケールアップできるかもしれません。

4. 諦めない

「制限時間がある」という思いに縛られすぎず、時間切れになってもその場で解く つもりで挑めば拾える問題が必ずあります。
また、食べ物と飲み物を用意すると気分を身体的に切り替えられるのでおすすめです。

終わりに

今回私が得られた学びが少しでも読んでくださった皆さんの力になれればとても嬉しいです。
制限時間や能力のせいにして諦めず、試行錯誤で問題に対する「気づき」を増やせると確実に解ける問題が増えるはずです。

最後に、ごはんはちゃんと食べろ！