院生と物理学と+α

大学院生(専攻は相対論と量子情報)が学んだこととかつらつら書いていきます

ABCのちょっと昔の問題を解く (ABC 040 C 柱柱柱柱柱)

プログラミング

ABC040 C 柱柱柱柱柱

最近○柱というのが巷で流行っている。
水柱さん、風柱さん、岩柱さん、炎柱さん、嘘柱誇張しのぶさんだのいろんな柱の方がいてポケモンみたい。
ちなみに私は炎柱さんが好きです。(今回の話に○殺隊は一切関係ありません)
なので(?)今回はちょっと古い2016年の問題
ABC040 C 柱柱柱柱柱
をC++で解いてみた。
(2016年はちょっと前だよね？まだ古いって程ではないよね？？)

問題文

N本の木の柱が左から右へ一列に並んだアスレチックがあります。左からi本目の柱の高さa _ iセンチメートルです。高橋君は左から1本目の柱からスタートし、右へ柱を渡っていきN本目の柱まで行こうとしています。高橋君がある柱にいるとき、次には現在の柱から1個もしくは2個右にある柱のどちらかへ移動することができます。移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。N本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。

制約
2≦N≦100,000
0≦a _ i≦10,000
a _ iはすべて整数である。

解法(壱ノ型)

パッと見典型的な動的計画法の問題だなあという印象。
{\rm dp}[i]:=i本目の柱に着いた時のコストの合計の最小値
とすれば漸化式がたてられます。
状態の遷移を考えて漸化式を立てるというのは大学受験でも割とよくある問題(だと思う)。
具体的には

{\rm dp}[i] = min({\rm dp}[i-1]+ \left|a_{i}-a_{i-1}\right|,\ {\rm dp}[i-2]+ \left|a_{i}-a_{i-2}\right|)

のようにi-1番目から来る場合とi-2番目から来る場合の２通りのうち最小な方を選べば良い。
実装する時には配列{\rm dp}[]に予め巨大な数を入れておいて、それを順番に更新していく。
注意としてはi=1ではi-2番目が存在しないので取り除かないといけないことぐらいだろうか。
ちなみに巨大な数ってなんぼやねんというと

INF = 1ll <<60

とするといいらしい。が、なんでかはよくわかってないので勉強しないといけない。

以上を踏まえて実装したものがこちら

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const long long INF = 1ll<<60;
 

long long N;
long long a[100010];
long long dp[100010];

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    /*初期化*/
    for(int i = 0; i < 100010; i++){
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i = 1; i < 100010; i++){
        dp[i] = min(dp[i], dp[i-1] + abs(a[i] - a[i-1]));  
        if(i > 1){
            dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));
        }
    }
    cout << dp[N-1] << endl;
}

入力例

9
314 159 265 358 979 323 846 264 338

出力

310

とりあえずこれでACになったのでヨシ！
そういえば配列を定義する時、今まで上限を格納するのに必要な最低限数だけ確保してたが、いろんな人のコードを見ると[上限+ちょっと]としてる人が多い(なので今回はa[100010]や{\rm dp}[100010]にしてみた)
なんとなくぴったりにしてた方が何か間違いがあった時エラーでわかるんちゃうかという適当な認識だが、ここら辺もちゃんと勉強しないといけない。

※追記 そもそもvectorで書いたらあかんのか？と思って下のように書いたら普通に通った、しかもこっちのがわずかに速い。が、通ったというだけでもしかしたらいけないことをしている可能性もあるので勉強しよう…

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const long long INF = 1ll<<60;
 

long long N;

int main(){
    cin >> N;
    vector<long long> a(N);
    vector<long long> dp(N);
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    /*初期化*/
    for(int i = 0; i < N; i++){
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i = 1; i < N; i++){
        dp[i] = min(dp[i], dp[i-1] + abs(a[i] - a[i-1]));  
        if(i > 1){
            dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));
        }
    }
    cout << dp[N-1] << endl;
}

解法(弐ノ型)

もしなんか思いついたら書く

感想

鬼滅の刃面白いよね