【AtCoder】PythonでDPマスターその1〜初めの一歩〜

2021.07.10

2024.03.24

競技プログラミング

AtCoderPython幅優先探索深さ優先探索

本ページはAmazonアフィリエイトのリンクを含みます。

はじめに

動的計画法(DP: Dynamic Programming)について、AtCoderの「DPまとめコンテスト」を利用しながらDPの理解と実装ができるようになることを目指します。

DPについてはなんとなく理解していてもAtCoderの問題でうまく使いこなせないことが多かったので、このDPまとめコンテストを通してマスターしたいと思います。

まずはDPがどんなものなのかを、DPまとめコンテストのA問題とB問題（比較的シンプルな問題かと思います）を解きながらざっくり理解していきます。

動的計画法（DP）とは

動的計画法とは、求めたい問題に対して部分的な解を順番に求め、その解を利用しながら本来求めたい解を導き出す手法です。

本来の問題を部分問題に分割して解を求め活用していくため、同じ計算を何度もする必要がなくなり計算量を抑えることができます。

疑似コードとしては以下のようになります。

1dp = 問題に応じた初期値で初期化された配列(0や考えられる最大値+1など)
2dp = 初期条件
3
4解を求めるまで繰り返す
5  dp = dpテーブルの解を利用して解を求める

DPまとめコンテスト

DPまとめコンテスト(EDPC)は、DPの練習を目的とした典型的なDP問題をまとめたコンテストです。

Educational DP Contest - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題はA~Zまで26種類あり、典型的で簡単な問題が出題されているそうです。

また、ある程度速い言語が推奨されており、実際にB問題ではPythonだとTLEになるテストケースがありました。

A問題: Frog 1

カエルが柱をジャンプしながらゴールにたどり着くまでの最小コストを求める問題です。コストは移動した時の柱の高さの差となり、移動できるのは1つ隣もしくは2つ隣のみとなります。

A - Frog 1

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

全探索するとゴールまでの全てのたどり着き方の組み合わせのコストを計算する必要があるため、DPで1本目の柱までの最小コスト、2本目の柱までの最小コストと順に求めていきます。

1n = int(input())
2h = list(map(int, input().split()))
3
4# 初期化
5# 最小化のため最大値で初期化
6dp = [10**5+1] * n
7
8# 初期条件
9# 柱0の移動コストは0
10# 柱1への最小コストは柱0からの場合のみ
11dp[0] = 0
12dp[1] = abs(h[1]-h[0])
13
14# 解を求めるまで繰り返す
15for i in range(2, n):
16    # dpテーブルの解を利用して解を求める
17    # 柱iまでの最小コストは柱i-1からの移動か柱i-2からの移動の小さい方
18    dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
19
20print(dp[-1])

B問題: Frog 2

A問題と同じカエルが柱をジャンプしながらゴールにたどり着くまでの最小コストを求める問題です。ただし、k本隣の柱まで移動できるようになっています。

B - Frog 2

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A問題と考え方は同じでk本隣までの移動の中から最小コストを計算します。

また、この問題はPythonだとTLEが出てしまうため、PyPy3を使って提出しました。

1n, k = map(int, input().split())
2h = list(map(int, input().split()))
3
4# 初期化
5# 最小化のため最大値で初期化
6dp = [10**5+1] * n
7
8# 初期条件
9# 柱0の移動コストは0
10# 柱1への最小コストは柱0からの場合のみ
11dp[0] = 0
12dp[1] = abs(h[1]-h[0])
13
14# 解を求めるまで繰り返す
15for i in range(2, n):
16    # dpテーブルの解を利用して解を求める
17    # 柱iまでの最小コストは柱i-1, ... ,柱i-kからの移動の中で最も小さいもの
18    dp[i] = dp[i-1] + abs(h[i]-h[i-1])
19    for j in range(2, k+1):
20        if i - j >= 0:
21            dp[i] = min(abs(h[i]-h[i-j])+dp[i-j], dp[i])
22
23print(dp[-1])