Pythonでchmaxが実装できなーーい！
けんちょんさんの記事「動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集」にでてくるchmaxとchminをPythonで書こうとすると困った。
chmin の意味は
- a より b の方が小さかったら、a の値を b の値に置き換える (そして true を返す)
- そうでなかったら、何もしない (そして false を返す)
といったもの。
これを使うと、
1
| dp[hoge] = min(dp[hoge], dp[huga] + foo)
|
という処理を
1
| chmin(dp[hoge], dp[huga]+foo)
|
と書ける。
記事ではC++で以下のように実装されている。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
|
しかしこれをPythonで書くのに苦労した…という話。
解決策1：つくる
以下のように書いてみた。注意点として、各要素を[[0], [0], [1]]のように一要素のリストとしている。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def chmax(a: list, b: list) -> bool:
assert len(a) == len(b) == 1, "1要素のlistを指定してください"
if a[0] < b[0]:
a[0] = b[0]
return True
return False
def chmin(a: list, b: list) -> bool:
assert len(a) == len(b) == 1, "1要素のlistを指定してください"
if a[0] > b[0]:
a[0] = b[0]
return True
return False
|
使用例は以下。DPまとめコンテストのA - Frog 1を解いてみた。（解答を見たくない人は注意）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| INF = 10**18
def chmin(a: list, b: list) -> bool:
assert len(a) == len(b) == 1, "1要素のlistを指定"
if a[0] > b[0]:
a[0] = b[0]
return True
return False
N = int(input())
H = [int(x) for x in input().split()]
dp = [[INF] for _ in range(N)]
dp[0] = [0]
for i in range(1, N):
b = [dp[i-1][0] + abs(H[i] - H[i-1])]
chmin(dp[i], b)
if i > 1:
b = [dp[i-2][0] + abs(H[i] - H[i-2])]
chmin(dp[i], b)
print(*dp[-1])
|
実行時間は236msで、chminを使用しない実装だと136msなので遅くはなる。Flogだとうまみがわかりにくいが、dp配列が二次元とかになると嬉しそう
解決策2：スニペット
スニペット登録する手もあるようです。天才！
たぶんこれが一番はやいと思います。
おまけ
なぜわざわざ一要素のリストを使っているか気になる人は以下のように、idを調べてみるとなんとなくわかるかも。
intの場合。
1
2
3
4
5
6
7
8
9
| def f(i: int):
i = 0
print(f"f(i), i={i}, id={id(i)}")
i = 1
print(f"Before f, i={i}, id={id(i)}")
f(i)
print(f"After f, i={i}, id={id(i)}")
|
listの場合。
1
2
3
4
5
6
7
8
9
| def f(l: list):
l[0] = 0
print(f"f(l), l={l}, id={id(l)}")
l = [1, 2, 3]
print(f"Before f, l={l}, id={id(l)}")
f(l)
print(f"After f, l={l}, id={id(l)}")
|
mutable, immutableで調べてました。
どうでもいいけど
chminってチミンっぽくない？
でもスペルは"Thymine"らしい。残念。
