Codefestival2016QualC D Friction

http://code-festival-2016-qualc.contest.atcoder.jp/tasks/codefestival_2016_qualC_d
　列ごとに独立にDPすると、あら不思議、その通りに構成できました～という。
　面白いんだけど、なんかこうもやっと感が残る問題だ。
　こういう構成ゲーのエッセンスを多分に含んだ非構成ゲーの問題、最近よく見る気がする。勘が冴えてるときは解けるけど、苦手。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int INF = 1e9;
int dp[301][301];
int cost[301][301];

int calc(const vector<string>& fld, int pos) {
    memset(dp, 0, sizeof(dp));
    memset(cost, 0, sizeof(cost));
    int h = fld.size();
    for(int i : in(1, h + 1)) for(int j : in(1, h + 1)) {
        cost[i][j] = cost[i - 1][j - 1];
        if(fld[i - 1][pos] == fld[j - 1][pos + 1])
          ++cost[i][j];
    }
    for(int i : in(h + 1)) for(int j : in(h + 1)) {
        if(i == 0 || j == 0) {
            dp[i][j] = 0;
            continue;
        }
        int& res = dp[i][j];
        dp[i][j] = INF;
        res = min(res, dp[i - 1][j] + cost[i][j]);
        res = min(res, dp[i][j - 1] + cost[i][j]);
    }
    return dp[h][h];
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    vector<string> fld(h);
    for(auto& x : fld) cin >> x;
    int sum = 0;
    for(int i : in(w - 1))
      sum += calc(fld, i);
    cout << sum << endl;
    return 0;
}

　構成ゲー（というか証明が構成ゲーっぽいのでこう呼んでるだけで分解するパートのことを指してる）が本質で、DPはオマケみたいなもんなのでDPについては触れない。
　
　ところで今回過去最低順位（500位台）をとってしまい、とてもつらい。
　CFのレート（1820)とAtCoderのレート(1500くらい）の相関から導かれる事実、「地頭がない」という感じで少し傷つくんだよなあ。

　かといって競技プログラミングは嫌いになれそうにないので、まあ地頭がないなりにやっていくしかないのかな、という感じ。

　口で悟ったようなことを言うのは簡単なのだが、実際は2,3日落ち込んでいるかもしれない。