ABC 437 C 問題：貪欲法だと思ってから解法に至るまでに足りなかったこと
はじめに
ABC 437 にバーチャルコンテストで参加しました。A, B 問題は解けたものの、C, D 問題で詰まって 2 完でした。
特に C 問題は「貪欲法が使えそうだ」という直感はあったものの、時間内に解法へ落とし込めませんでした。
私は過去に、貪欲法の解き方や難しそうでも手を止めない方法について記事を書いてきました。本記事では、それらの考え方が実戦でどこまで機能し、どこが不足していたのかを ABC 437 C 問題を題材に振り返ります。
問題
各トナカイは重さ
コンテスト中にできたこと
以下、箇条書きでコンテスト中にできたことを時系列で述べていきます。
- ぱっと見で解法を思いつかなかったため、まずは
2^N -
N - 続いてランダムテストを実装しました。これで解法コードが書ければ比較検討できるようになりました。
- 直感的にわかっている以下のことを言葉に起こしました。
- 重くて力の強いトナカイにはソリを引かせたほうが得である
- 軽くて力の弱いトナカイはソリに乗せたほうが得である
- この「得である」という考え方から、貪欲法が使えないか検討しました。
- しかし、貪欲に選ぶために必要な「適切な順にソートする」という操作ができず、ここで手が止まりました。
解けなかった理由の分析
今回は貪欲法を検討したところまではうまくいっていましたが、「貪欲法だと気づくこと」と「具体的な解法を構成すること」の間にあるギャップを埋めきれませんでした。
ここを詳しく分析していきます。
貪欲法だと思ってから解法に落とし込むまでのギャップ
制約などから「貪欲法が使えないか」と考えた時点では、（本当に貪欲法を使うかどうかも含めて）まだ何も決まっていません。
この時点で「なぜ貪欲法がうまくいくのか」を考えるのは当然ながら不可能です。
過去の記事で述べた「証明の方法」と「貪欲法だと思った時点」との間にギャップがあり、ここが手が止まった原因でした。
今回わからなかったポイント
私が引っかかったポイントは「何を基準にソートするか」でした。これはすなわち、貪欲に選択するための比較量を定義できなかったということです。
比較量として思いつく限り、たとえば
比較量を式で定義する作業に入らず、何か良い指標を思いつくのを待つ「ひらめき待ち」の状態であったことも、問題が解けなかった一因です。
解くために必要だったこと
総重量とソリを引く力の総和の 2 軸で考えると、「力が強いが軽いトナカイ」と「重いが力の弱いトナカイ」にどう順序付けを行うかが定義できません。
本問では以下の観察が必要でした。
- 1 匹のトナカイにソリを引かせたとき、残りのトナカイの制約はどう変わるか？
- ソリに乗せたトナカイとソリを引かせたトナカイを交換したとき、全体で何が増減するか？
これらを考えることで比較すべき量を定められ、トナカイに優先順位をつけることができます。
過去の記事を振り返って
比較に使う量がわかってからは初めに述べた過去の記事を参考にして交換法を使った証明ができました。
しかし実戦で活用するためには、記事の内容に加えて「いつ貪欲法を使うのか」「何を基準に比較するのか」というステップが必要でした。
また、試行錯誤すること自体は実践できていましたが、「ひらめきを待つ」という姿勢を取ったことで手が止まっていました。これは過去の記事で述べていなかったことです。
次の問題ではどう行動するか
まずは「貪欲法ではないか」と考えたときに確かめることをまとめます。
- 2 軸のパラメータがある場合は 1 軸にまとめられないか考える
- 反転・交換による差分を式に表してみる
- その差分が単一の指標になることを確かめる
また、闇雲に試してうまくいくケースをひらめくことに期待するより、疑った実装法をいったん仮定として受け入れ、検証を進めることの重要性も感じました。
コンテスト中はまったくわからないと思っていても案外答えに近づいている、という点は過去の記事で述べたとおりでした。
おわりに
「解けなかった」という事実は心理的に厳しいものでしたが、落ち着いてから「どこでつまずいたのか」を言語化することができました。
今回は「解説を見たらすぐに解けた」というケースでした。これを「単にひらめかなかった」と解釈するのではなく、解法に至るための具体的な思考のステップが抜けていたのではないか、と見直すことが大事だと考えます。
問題を解けなかったとき、「どうすれば思いつけたか」を補完すれば、その経験は必ず次の問題に活かせるはずです。私もがんばります。
Discussion