Lyft Level 5 Challenge 2018 Final Round Div2 E - Optimal Polygon Perimeter

各点間のマンハッタン距離の和 = 長方形の周長ってのが完全に抜けてた
なんで解けなかったんだマジで
そういう問題最近SRMでやったし

問題

n頂点の凸多角形が与えられ、時計回りでi番目の頂点の座標は(x[i],y[i])である
このn個からk個の頂点v1, v2, ..., vkを選び、
Σ(viとvi+1間のマンハッタン距離)
を最大化したい
3 <= k <= nの全てのkについて↑の最大値を求めよ

3 <= n <= 3*10^5
|x|, |y| <= 10^8

解法

冒頭で言ったけどv1, v2, ..., vkについての
Σ(viとvi+1間のマンハッタン距離)
ってのは、これらk個の頂点を全て内側(or境界)に含むような長方形のうち最も小さいものの周長に等しい

○k>=4のとき
答えは明らかに
2{max(x)-min(x) + max(y)-min(y)}
となる

○k=3のとき
各点を↑で言った長方形の右上・右下・左下・左上それぞれにすると仮定したときの周長の最大値で答えを更新していけばいい
例えば点(a,b)を左下に固定するとき、長方形を右と上に出来る限り伸ばせば良いから
2{max(x)-a + max(y)-b}
で答えを更新みたいな感じ
他も同様にやればok

int n, x[300300], y[300300], mxx = -1<<30, mnx = 1<<30, mxy = -1<<30, mny = 1<<30, res3, res;

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> x[i] >> y[i];
		chmax(mxx, x[i]), chmin(mnx, x[i]);
		chmax(mxy, y[i]), chmin(mny, y[i]);
	}
	res = (mxx-mnx + mxy-mny)*2;
	rep(i,n) {
		chmax(res3, (x[i]-mnx + y[i]-mny)*2);
		chmax(res3, (x[i]-mnx + mxy-y[i])*2);
		chmax(res3, (mxx-x[i] + y[i]-mny)*2);
		chmax(res3, (mxx-x[i] + mxy-y[i])*2);
	}
	cout << res3;
	rep(i,n-3) cout << ' ' << res;
}

http://codeforces.com/contest/1075/problem/E

SRM580 Div1 Easy - EelAndRabbit

appletは相変わらず滅多に繋がらない上に最近たまにstatisticsの問題ページが消える

問題

川をn匹のうなぎが泳いでおり、i匹目の長さはa[i]で、時刻t[i]にうなぎの頭がx軸にぶつかる
ある時刻に川に飛び込むと、その瞬間にx軸と交点を持つうなぎを全て捕まえることができる
2回まで川に飛び込めるとき最大で何匹のうなぎを捕まえられるか

1 <= n <= 50
1 <= a[i] <= 10^9
0 <= t[i] <= 10^9

解法

i匹目のうなぎがx軸と交点を持つような時間帯の左端をL[i]、右端をr[i]とする
うなぎの部分集合Sを考えると、(Sの全てのうなぎを1回で捕まえることができる時間帯) = (各うなぎの[L[i], r[i]]の共通範囲) であり、そのような時間帯の左端と右端はSに含まれるあるうなぎの左端と右端に一致する
ということは川に飛び込む時刻の候補は各L[i]とr[i]のみ考えれば十分
たかだか100個しかないから2点の選び方を全部試せばいい

class EelAndRabbit {
public:
	int getmax(vector<int> a, vector<int> t) {
		int n = a.size();
		vector<int> l, r, s;
		rep(i,n) {
			l.push_back(t[i]), r.push_back(t[i]+a[i]);
			s.push_back(t[i]), s.push_back(t[i]+a[i]);
		}
		int res = 0;
		each(i,s) each(j,s) {
			int p = 0;
			rep(k,n) if ((l[k]<=i && i<=r[k]) || (l[k]<=j && j<=r[k])) p++;
			chmax(res,p);
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12575&rd=15500

SRM579 Div1 Easy - UndoHistory

問題

長いから略
与えられるvectorの名前はsとする

解法

s[i]をタイプするとき
L = max(s[i]とs[j < i]の最長共通接頭辞の長さ)
とすると、2回のマウスクリックでL文字復元して、残りの |s[i]|-L 文字は手打ちする必要がある
ただs[i]の先頭がs[j]に一致する場合のみ、前のバッファをそのまま使って |s[i]|-|s[j]| 回タイプするって選択肢もある

class UndoHistory {
public:
	int minPresses(vector<string> s) {
		int n = s.size(), res = 0;
		rep(i,n) {
			int l = 0;
			rep(j,i) {
				rep(k, min(s[i].size(), s[j].size())) {
					if (s[i][k]==s[j][k]) chmax(l,k+1);
					else break;
				}
			}
			if (i==0) res += s[i].size() + 1;
			else {
				int t = 2+s[i].size()-l;
				if (s[i].size()>=s[i-1].size()
					&& s[i].substr(0,s[i-1].size())==s[i-1])
						chmin(t, (int)(s[i].size()-s[i-1].size()));
				res += t+1;
			}
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499

SRM578 Div1 Easy - GooseInZooDivOne

問題

h*wのグリッド上のいくつかのマスにガチョウとアヒルがいるが、見た目で区別はつかない
ガチョウは以下の条件を満たす
1) ガチョウは2以上の偶数匹いる
2) あるガチョウからマンハッタン距離がd以内にいるような鳥は必ずガチョウである
鳥の部分集合のうち、全要素がガチョウであり得るようなものの個数を求めよ

1 <= h, w <= 50
0 <= d <= 100

解法

各鳥を頂点0〜n-1とし、マンハッタン距離がd以下であるような鳥のペア間に辺を引いてグラフを作る
条件2より各連結成分の鳥は全てガチョウかアヒルのどちらかで統一される必要がある
i番目の連結成分のサイズをa[i]として(0 <= i < m)、
dp[i][j]: a[0]〜a[i-1]の範囲でガチョウがj匹になるような選び方の個数
を埋めればok
答えはΣdp[m][even]

実装

辺の情報を全部記録しちゃうとスタックオーバーフローするケースがありそう
(50*50で全マスにガチョウがいるときなんかが怪しい)
記録はせずに再帰で毎回チェックする

dp配列も同様にメモリ節約しないとダメ

class GooseInZooDivOne {
public:
	int h, w, n, m, d, dp[2][2525], res;
	bool f[2525];
	vector<int> x, y, a;

	int rec(int v) {
		f[v] = 1;
		int res = 1;
		rep(i,n) if (!f[i] && abs(x[v]-x[i])+abs(y[v]-y[i])<=d) res += rec(i);
		return res;
	}

	int count(vector<string> s, int d_) {
		d = d_, h = s.size(), w = s[0].size();
		rep(i,h) rep(j,w) if (s[i][j]=='v') x.push_back(i), y.push_back(j), n++;
		rep(i,n) if (!f[i]) a.push_back(rec(i)), m++;
		dp[0][0] = 1;
		rep(I,m) {
			int i = I&1;
			rep(j,n) if (dp[i][j]) {
				(dp[i^1][j+a[I]] += dp[i][j]) %= mod;
				(dp[i^1][j] += dp[i][j]) %= mod;
			}
			memset(dp[i], 0, sizeof(dp[i]));
		}
		int res = 0;
		reps(i,2,n+1) if (i%2==0) (res += dp[m&1][i]) %= mod;
		return res;
	}
};

d以下じゃなくてちょうどdと誤読した

https://community.topcoder.com/stat?c=problem_statement&pm=12539&rd=15498

SRM577 Div1 Easy - EllysRoomAssignmentsDiv1

くだらねえ問題

問題

プログラミングコンテストにn人の参加者がいて、i人目のレートはa[i]である
コンテストの部屋の個数rは r = ceil(n/20) とする
まず参加者をレートの降順に並べ、その後各参加者を順番にr人ずつ見ていき、そのr人それぞれが互いに異なる部屋に入るようにランダムに部屋に入れる
降順ソートする前の0番目の人の部屋のレーティングの平均値の期待値を求めよ

8 <= n <= 500
1200 <= a[i] <= 3923

解法

(0番目の人の名前はElly)
r人ずつ配っていくとn%r(=kとする)人だけ余る
この余りにEllyが含まれる場合は同じ部屋の人数はn/r+1人で確定
そうじゃない場合はn/r人の場合とn/r+1人の場合がある
書いててダルくなったから以下略

class EllysRoomAssignmentsDiv1 {
public:
	double getAverage(vector<string> s) {
		string t;
		each(i,s) t += i;
		vector<double> a;
		for (int i=0; i<t.size(); i+=5) a.push_back(stoi(t.substr(i,4)));
		int n = a.size(), r = (n+19)/20, k = n%r, cnt = n/r;
		double x = a[0];
		sort(a.rbegin(), a.rend());
		int id = find(all(a), x) - a.begin();
		for (int i=0; i<r*cnt; i+=r) {
			if (i<=id && id<i+r) continue;
			rep(j,r) x += a[i+j]/r;
		}
		if (r*cnt<=id) return x/(cnt+1);
		double res = x/cnt*(r-k)/r;
		reps(i,r*cnt,n) res += (x+a[i])/(cnt+1)/r;
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12514&rd=15497

SRM576 Div1 Easy - ArcadeManao

問題

h*wのグリッドがあり、(sx,sy)からx座標がh-1の任意のマスに行きたい
床があるマスとないマスがあり、床があるマスにしか移動することはできない
あるマス(x,y)からは、(x,y±1) には無条件で行ける (床さえあれば)
長さLのはしごを持っている場合は (x±L,y) にも行ける
最初にはしごの長さを選べるとき、目的達成に必要なはしごの長さの最小値を求めよ

1 <= h, w <= 50

解法

はしごの長さを全部試してBFSとかで適当に

class ArcadeManao {
public:
	int shortestLadder(vector<string> s, int sx, int sy) {
		int h = s.size(), w = s[0].size();
		sx--, sy--;
		rep(l,h) {
			bool v[55][55] = {};
			queue<pair<int,int> > q;
			q.push({sx,sy}), v[sx][sy] = 1;
			while (!q.empty()) {
				int x = q.front().first, y = q.front().second; q.pop();
				if (y+1<w && s[x][y+1]=='X' && !v[x][y+1]) v[x][y+1] = 1, q.push({x,y+1});
				if (y-1>=0 && s[x][y-1]=='X' && !v[x][y-1]) v[x][y-1] = 1, q.push({x,y-1});
				reps(i,max(0,x-l),min(h,x+l+1)) if (s[i][y]=='X' && !v[i][y]) v[i][y] = 1, q.push({i,y});
			}
			rep(i,w) if (v[h-1][i]) return l;
		}
		return -1;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12504&rd=15496

SRM575 Div1 Easy - TheNumberGameDivOne

わかりませんでした😠
ゲーム系のeasyにしてはむずくない？

問題

自然数nがある
2人が交互にnから「1とn以外のnの約数」を引き、操作を行えなくなった方が負ける
どちらが勝つか判定せよ

1 <= n <= 10^18

解法

nが奇数 or 2の奇数乗なら後手、それ以外は先手が勝つ
このゲームは素数を渡されたら負けってことになる
素数は2以外は全部奇数なことに注目する

○nが奇数のとき
そもそもnが素数の場合は先手が即負け
そうじゃない場合、nはどんな操作をしても「2の累乗ではないような偶数」になる
(何かしらの操作によってnを2の累乗にできると仮定するとnは2の累乗の倍数 → 偶数になるから矛盾)
そういう数字は必ず奇数の約数が存在するため、返しのターンで後手が奇数にして返せる
よって何度繰り返しても先手には奇数が返ってきて、いつかはそれが素数になる

○nが2のp乗のとき
このnに操作を行うと「2の累乗」or「2の累乗でない偶数」のどちらかを作れる
↑の通り後者を相手に渡すと負けるから前者を選び続けるしかない
前者にするってのはnをn/2に変えるってことで、そうするとターン数はpターンになる
よってpが奇数なら負け、偶数なら勝ち

class TheNumberGameDivOne {
public:
	string find(ll n) {
		if (n%2) return "Brus";
		rep(i,60) if (i%2 && n==(1ll<<i)) return "Brus";
		return "John";
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495