【8日目】大敗したABC198を再考してみる
一昨日大敗したABC198について、昨日は全体的な課題点を考察したが、今日は個別の問題について見ていく。Fは今のレベルではかなり無謀な問題なので、大きな敗因だったDとEの失敗について。
D - Send More Money
覆面算の問題。これに関しては解けなかった原因はただ一つ。
計算量の見積もりを誤った。
愚直に全探索した場合の時間計算量はO(10!)。これはおおよそ3E6なのでTLEにならない、、のだが、ここを早とちりしてTLEになると思ってしまい、無駄に複雑に考えてしまったようだ。前も似たような失敗をやらかしたので気を付けていたつもりだったのだが…。
今回の教訓として、
- 全探索での時間計算量はしっかりと計算し、TLEになる場合のみより良い解法を考える
- O(N!)時間の場合、N=11まではTLEにはならない
という2点を抑えておこう。
この問題はどちらかというと実装がちょい難しかった。無駄な計算を減らすために少し工夫が必要。実装にはnext_permutationを用いた。便利。
E - Unique Color
MLEの最大の原因は、「1からxまでの最短パス中に使われている色の一覧」の情報を各ノードごとに個別に保持していたことと思われる。
DFSを使う場合、このような情報は共通に一つ配列を用意して、各ノードへの進入・退出時に更新すればメモリ使用を大幅に減らせる。(分かりづらくなるのでメモリ問題がなければあまり使いたくない気もするのだが)
このことができるのはDFSの(BFSに対する)大きなメリットでは？という気もする。 ちなみにDFSは、再帰関数を使ったものとwhileループのものと両方試してみたが、どちらもほとんど実行時間、メモリ使用は変わらなかった。完全に好みの問題かな。
明日OR今夜もう一つABCの過去問を解いてみようと思います。最近のものですが197をまだやっていなかったのでそれを。
