python初心者が３０分で文法を覚えて競プロを始める〜その２〜

こんにちは

前回の記事では、pythonで競プロを解いていくために、
必要最低限の基本文法だけ確認していきました。

greko-engineer.hateblo.jp

今回は、前回覚えた文法を引っさげて、
AtCoderの過去問を解いていきたいと思います。

対象の問題はこれ。

問題

N個の足場があります。足場には、1,2,...,Nと番号が振られています。
各i(1<i<N)について、足場iの高さはhiです。
最初、足場１にカエルがいます。
カエルは次の行動を何回か繰り返し、
足場Nまでたどり着こうとしています。
・足場iにいるとき、足場i+1または、i+2へジャンプする。
このとき、ジャンプ先の足場をjとすると、コスト|hi-hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの
総和の最小値を求めてください。

DP（動的計画法）と言われるパターンで解ける問題のようです。

動的計画法は↓を参考になんとなく理解しました。（とてもわかりやすかったです）
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

何度か失敗を繰り返して、最終的に解答はこのようになりました。

N = int(input())
h = [int(i) for i in input().split()]

dp = [0]*N
dp[0],dp[1] = 0,abs(h[1]-h[0])

for i in range(2,N):
    dp[i] = min(dp[i-2] + abs(h[i]-h[i-2]), dp[i-1] + abs(h[i]-h[i-1]))
 
print(dp[N-1])

とてもシンプルな解答になりました。

ちなみに同じ問題をJavaで書いた時はこうなりました。

import java.util.*;
 
public class Main {
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        
        try(Scanner scan = new Scanner(System.in)){
            int N = Integer.parseInt(scan.next());
            int[] h = new int[N];
            int[] d = new int[N];
            
            for(int i=0;i<N;i++) {
                h[i] = Integer.parseInt(scan.next());
                d[i] = INF;
            }
            d[0]= 0;
            d[1]= Math.abs(h[1] - h[0]);
            
            for(int i = 2; i<N; i++) {
                
                int prepre = d[i-2] + Math.abs(h[i]-h[i-2]);
                int pre = d[i-1] + Math.abs(h[i]-h[i-1]);
              
                d[i] = Math.min(prepre, pre);  
            }
            System.out.println(d[N-1]);
                
        }
    }
 
}

やっぱりpythonは簡潔でいいですね。

そしてこの問題を通して、
↓のような文法を新しく学べました。
・まとめての変数宣言
・リスト内包表記

まず、「まとめての変数宣言」が、 ↓この部分です。

dp[0],dp[1] = 0,abs(h[1]-h[0])

カンマで区切ることで、
１行に変数の宣言をまとめて書けるみたいです。便利ですね。

そして、「リスト内包表記」。 ↓この部分ですね。

h = [int(i) for i in input().split()]

やってる処理としては、
input()で受け付けた複数文字の標準入力を、
split()で１つ１つの文字に分割されたlistに変換し、
そのリストの各要素iに対し、int(i)でintに変換して、
それを配列にするといった感じです。（わかりづらくてすいません。。）

基本的には、 [iの処理 for i in 配列など]と書くみたいです。 i に対して行う処理をfor文の外側に出したような書き方ですね。

まだ簡単な内容しか学べてないですが、
競プロでアルゴリズムを学びながら、並行して、新しい言語を学べていけるのはとても有意義でした。

同じ境遇の人にはぜひ進めたいです。

ryoのぼやき

技術についての学習内容のまとめです。

python初心者が３０分で文法を覚えて競プロを始める〜その２〜

問題