Google Code Jam 2010:Round2 Problem A. Elegant Diamond
ダイヤモンドを拡張して上下左右対称にする問題。
拡張する時、追加する文字によってコストが違う物だと思い込んでいた。大きさしか関係ないんだね。
一位とった人のソースコードを読んで気がついた。
自分なりに書きなおしたのが以下のコード。
1行読み取りのでちょっと引っかかって、コストの計算方法でも引っかかった。
あと、6時間と少し・・・こんな調子で大丈夫か自分。
#include <iostream> #include <vector> #include <sstream> #include <string> #include <algorithm> #include <cstring> typedef unsigned long long ULL; typedef long long LL; typedef unsigned long UL; typedef unsigned int UI; typedef unsigned short US; typedef unsigned char UC; #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; int sq(int x) { return x*x; } int solve(int no) { //Input data int K; cin >> K; string dummy; getline(cin, dummy); int S = 2*K-1; string d[200]; rep(i,0,S) { getline(cin, d[i]); } //横方向 int hmin = 1<<20; rep(i,0,S) { rep(j,0,S) { rep(k,0,d[j].size()) { int k2 = 2*i-k; if(0<=k2 && k2<=d[j].size() && d[j][k]!=' ' && d[j][k2]!=' ' && d[j][k]!=d[j][k2]) goto hskip; } } //cout << i << ":" << endl; hmin = min(hmin, abs(K-1-i)); hskip:; } //縦 int vmin = 1<<20; rep(i,0,S) { rep(j,0,S) { int j2 = 2*i-j; if(j2<0 || j2>=S) continue; rep(k,0,S) { if(k<d[j].size() && k<d[j2].size() && d[j][k]!=' ' && d[j2][k]!=' ' && d[j][k]!=d[j2][k]) goto vskip; } } vmin = min(vmin, abs(K-1-i)); vskip:; } //cout << hmin << "," << vmin << endl; cout << "Case #" << no << ": " << (sq(K+hmin+vmin)-sq(K))<< endl; } int main() { int T; cin >> T; rep(no,0,T) { solve(no+1); } return 0; }