mayoko’s diary

プロコンとかいろいろ。

SRM 499 div1 med:WhiteSpaceEditing

本番「あってる気がするけどどうなんでしょ」と思いながら出したら通った。このときはよく考えてなかったがこのコード考えを非常に簡潔にまとめていてすごい。dpでやった方が安定するよね。

問題:TopCoder Statistics - Problem Statement

解法:とりあえず10,20,30および30,20,10はどのように作るのが最短であるかを考える。これらは,
10->10,10->10,20->10,20,20->10,20,30
10->10,10->20,10->20,20,10->30,20,10
とやれば最短であることがわかる(無駄がないしこのように作れるなら最短であることは明らか)。
要するに,単調減少するような場合も単調増加するような場合もDELETEなしに最短で目的の文章を構成する方法が存在する。次に,一般的な場合を考える。これは,単調減少する区間と単調増加する区間が交互に存在するものであると解釈できる。説明しにくいが,このような一般的な場合についても,単調増加する場合のメソッド及び単調減少する場合のメソッドを使って文章を構成することができる(イメージとしては谷になっているところを最初に作ってそこから周りにより大きくなっているところを広げていくイメージ)。

で,その考えをソースコードにまとめると下のように書くこともできます。
lines[i+1] >= lines[i] の場合については想像通りだと思います。一方lines[i+1] < lines[i]の場合はちょっと解釈が難しいですが本当はlines[i+1]->lines[i]と作るところも回数的にはlines[i]の途中でスペースの数がlines[i+1]になった時にコピペしてその後またlines[i]にスペースを増やすと解釈しても良いのでその場合の回数はコードのようになるとすることができます。

以下ソースコード

class WhiteSpaceEditing {
public:
    int getMinimum(vector <int> lines) {
        int ans = lines[0];
        int N = lines.size();
        for (int i = 0; i < N-1; i++) {
            if (lines[i+1] >= lines[i]) {
                ans += 1+lines[i+1]-lines[i];
            } else {
                ans += 1;
            }
        }
        return ans;
    }
}