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日落ち込んでいるかもしれない。