「Atcoder」一覧

問題 D - マーブル 動的計画法を使って解く。 回答 動的計画法 参考 はやくプロになりたい ABC 004 Hacking to the Gate ! 別館　AtCoder Beginer Contest 004 - D ...

問題 L - Deque 参考 例題 3.EDPC L 問題 - Deque　〜 得点差も最大化したい 〜 Deque 回答 DP PyPyではAC。 import sys # input処理を高速化する input = sys...

問題 K - Stones 参考 AtCoderDPまとめコンテスト K問題 「Stones」 例題 2. EDPC K 問題 - Stones　〜 石取りゲームの一般化 〜 回答 import sys # input処理を高速化する inp...

問題 J - Sushi 期待値DP 期待値DPについて以下分かりやすいです。 確率 DP を極めよう また、Pythonであるということ以外、メモ化再帰は以下のほぼ写経です。 Educational DP Contest の F ～ J...

問題 I - Coins 確率DPの問題。 参考資料 確率 DP を極めよう 回答 TLEだった回答 PyPyではAC。 import sys # input処理を高速化する input = sys.stdin.readli...

問題 H - Grid 1 DP、数え上げ問題。 回答 import sys # input処理を高速化する input = sys.stdin.readline def main(): # input H, W = map(int,...

問題 G - Longest Path 有向非巡回グラフであり、DP の更新順序が非自明な問題です。 メモ化再帰を使うか、トポロジカルソートを使います。 解き方は以下を参考にしています。 Educational DP Contest の F ～ J...

問題 F - LCS 最長共通部分列問題です。 最長共通部分列問題については、以下の解説がとても分かりやすいです。 Common Subsequence 解説 最長共通部分列問題 (Longest Common Subsequence) 回答...

問題 E - Knapsack 2 回答 TLEで間に合わない最初の回答 アルゴリズム的には合っているかな？ import sys # input処理を高速化する input = sys.stdin.readline # 入力 N, W = ...