この記事で使うアルゴリズム
動的計画法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc120/tasks/abc120_d
この問題は動的計画法で解くことができます。
方針
全探索では間に合いませんので、動的計画法により解きます。各クエリに対して計算量はO(MN)
となるので、全体の計算量はO(qMN)
です。これが想定解法と思われますがPython3
の場合はTLE
となってしまいました。
コード
1 | Q = int(input()) |
記事情報
- 投稿日:2020年5月20日
- 最終更新日:2020年5月20日