Pythonで解くAtCoder(ABC176:E)
こんにちは、クルトンです！
この記事では
AtCoderの「AtCoder Beginner Contest 176」のE問題をPythonを使って解説します。
問題のリンクを載せておきます。
解法
解説が分かりやすかったので、解説を参考にしてください。
解説の補足
解説の「爆発対象が存在するマスは高々個しか存在しないため、調べる回数は
回以下に抑えることができ、全探索することが可能です。」という部分について少し詳しく説明します。
kort0nさんのコードでは「が最大かつ
が最大となる
」について全探索して、爆発対象が存在しない
の組み合わせが存在するかについて調べています。
このとき、「が最大かつ
が最大となる
」についてすべて調べると、計算量は
となり間に合いません。
しかし、爆発対象はM個しかないためM+1個まで調べると、爆発対象が存在しないの組み合わせが必ず見つかります。
よって爆発対象が存在しないの組み合わせを見つけた時点で探索を打ち切ると、計算量は
となり、十分間に合います。
別解
実は上のように全探索をしなくても解くことができます。
まず、が最大かつ
が最大となる
の集合を
とおきます。
ここで「の任意の要素
に対して、爆発対象が存在する」という条件について考えてみましょう。
この条件は「の要素数と爆発対象の内
に含まれる要素の数が等しい」と言い換えることができます。
の要素数は、
が最大となる
の数と
が最大となる
の数の積に等しく、
爆発対象の内に含まれる要素の数は、爆発対象
のうち
と
が共に最大となる
の数に等しいので、
これらが等しければ「の任意の要素
に対して、爆発対象が存在する」ことになります。
このときの計算量は、爆発対象を全探索しているためとなります。
まとめ
今回は
- 計算量に注意しながら全探索する
という問題でした。
ではまたお会いしましょう！さようなら～
