2015-06-05

SRM 660 Div1 250 Coversta

10:36 |

N*M のグリッドがあり、各マスに 0-9 の数字が書いてある。Pos[ ] も与えられ、あるマス p に駅を置くと p+P (P in Pos[ ]) なマスがカバーされる。
異なる場所に2駅置いたとき、2駅がカバーするマスに書いてある数字の合計の最大値を求めよ。
2≦N,M≦100, 1≦K=|Pos[]|≦10, -(N-1)≦Pos.x≦N-1, -(M-1)≦Pos.y≦M-1

カバー範囲が重なった時の処理がポイントっぽいぞ
naiveにやると置き方全てに対して Pos[] のとこを塗って確かめるので N^2 M^2 K -> 10^9 程度 -> むり

カバー範囲の重なり方は最大で K^2 個なことに気づく
なので「カバー範囲が重なるように2駅置いた時にカバーするマスのパターン」を最大10*10個持っておいて、
(1)カバー範囲が重なる2点を置いたときの最大値(N^2 M^2 K)と
(2)カバー範囲が重ならない2点を置いたときの最大値(事前にマス→カバー範囲の合計値をNMKで計算しておき重複かどうかをmapで覚えておくとN^2M^2logK)
の最大値が答え
(1)では、重なり方すべてK^2について最初の点から見た2点目の相対座標と最大K*2点(最初のカバー範囲∪ちょっとずらした範囲)のパターンを覚えておく
(2)では2点目の相対座標が(1)で計算した相対座標セットに含まれない＝2点のカバー範囲が重ならない、という感じでチェックすればいい。

ていうことで N^2M^2logK なので良さそうではあるが、...
これで250か, 書いてピッタリ答えが合うとは思えない...
IN_RANGE(Value, Min, Max) マクロ大活躍の巻き

なぜかサンプルが合った → 3x3 で10ケースくらい手動テストしてOKそうなので 95pt くらいで提出

Accepted

おー通るのかよ

(あとで)K^2+α個で打ち切る NMK^2 解もあるのか。(そっちはなぜそれでいいか腑に落ちてない)

struct Pos {
	int x, y;
	bool operator<(const Pos v) const {
		return x*1000+y < v.x*1000+v.y;
	}
	bool operator==(const Pos v) const {
		return x==v.x && y==v.y;
	}
};
std::ostream& operator<<(std::ostream& os, const Pos& v) {
	os << "("<<v.x<<", "<<v.y<<") ";
	return os;
}

struct Pat {
	Pos ref;
	vector<Pos> pos;
};

class Coversta {
	public:
	int place(vector <string> a, vector <int> X, vector <int> Y) {
		int W=a.size(), H=a[0].size();
		int N=X.size();
		VVI one(W, VI(H));
		vector<Pat> pat;
		map<PII, int> ng;
		REP(x, W) REP(y, H) REP(i, N) {
			if(IN_RANGE(x+X[i], 0, W) && IN_RANGE(y+Y[i], 0, H)) {
				one[x][y]+=a[x+X[i]][y+Y[i]]-'0';
			}
		}
		REP(i, N) REP(j, N) if(i!=j) {
			// i-j
			int dx = X[i]-X[j];
			int dy = Y[i]-Y[j];
			auto key = MP(dx, dy);
			if(ng.count(key)) continue;
			if(dx==0 && dy==0) continue;
			ng[key] = 1;
			vector<Pos> v;
			REP(k, N) v.PB(Pos{X[k], Y[k]});
			REP(k, N) v.PB(Pos{X[k]+dx, Y[k]+dy});
			sort(ALL(v));
			v.erase(unique(ALL(v)), v.end());
			pat.PB({Pos{dx, dy}, v});
		}
		REP(i, pat.size()) {
//			cout<<pat[i].ref<<" -> "<<pat[i].pos<<endl;
//			cout<<pat[i].ref.x<<" "<<pat[i].ref.y<<endl;
		}
		ll ans = 0;
		REP(pi, pat.size()) {
			auto& p = pat[pi];
			REP(x0, W) REP(y0, H) {
				int xx = x0+p.ref.x;
				int yy = y0+p.ref.y;
				if(IN_RANGE(xx, 0, W) && IN_RANGE(yy, 0, H)) {
					ll lans = 0;
					REP(i, p.pos.size()) {
						int ex = x0 + p.pos[i].x;
						int ey = y0 + p.pos[i].y;
						if(IN_RANGE(ex, 0, W) && IN_RANGE(ey, 0, H)) {
							lans += a[ex][ey]-'0';
						}
					}
					ans = max(ans, lans);
				}
			}
		}
//		cout<<"one "<<one<<endl;
		REP(x0, W) REP(y0, H) REP(x1, W) REP(y1, H) if(!(x0==x1 && y0==y1)) {
			int dx = x0-x1;
			int dy = y0-y1;
			PII k = MP(dx, dy);
			if(!ng.count(k)) {
//				cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<" -> "<<one[x0][y0]+one[x1][y1]<<endl;
				ans = max(ans, one[x0][y0]+one[x1][y1]);
			}
		}
		return ans;
	}
};

kojingharangの日記

2015-06-05

SRM 660 Div1 250 Coversta