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

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

第3回ドワンゴからの挑戦状 本戦 A - 計算ドリル

俺のrated500埋めの最後の問題がこれ
atcoderでこういう実装ゲーはかなり珍しい

問題

'0'〜'9'、'+'、'-' のみからなる文字列sが与えられる
これをk文字まで書き換えて得られる、逆ポーランド記法で計算できる正しい文字列のうち、計算結果の最大値を求めよ

1 <= |s| <= 52
0 <= k <= |s|

解法

メモ化しながら区間dp
数式の一番最後の文字は '+' か '-' である必要があり、それ以外の部分は2つの式に分けることができるってのがポイント
この区切りとそれぞれの区間に割り振るkを全探索して更新していく
詳細は↓のコメントの通り

string s;
int n, k, dp[55][55][55][2];
bool fin[55][55][55][2];
const int M = 10000;

// [l,r]をk文字まで変えたときの最(b?大:小)値
int rec(int l, int r, int x, bool b) {
	if (fin[l][r][x][b]) return dp[l][r][x][b];
	fin[l][r][x][b] = 1;
	int &res = dp[l][r][x][b];
	res = (b ? -M : M);
	// どう変えても正しい式にならない場合
	if ((r-l+1)%2==0) return res;
	// 1桁の場合
	if (l==r) {
		if (x) res = (b ? 9 : 0);
		else if (isdigit(s[l])) res = s[l]-'0';
		return res;
	}
	// 一番右の文字は+か-にする
	int xp = x - (s[r]!='+'), xm = x - (s[r]!='-');
	// 2つの式の和の最大値は (最大)+(最大) or (最大)-(最小)
	if (b) {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xp-j,1);
				if (tx!=-M && ty!=-M) chmax(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xm-j,0);
				if (tx!=-M && ty!=M) chmax(res, tx-ty);
			}
		}
	}
	// 最小値は (最小)+(最小) or (最小)-(最大)
	else {
		reps(i,l,r-1) {
			rep(j,xp+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xp-j,0);
				if (tx!=M && ty!=M) chmin(res, tx+ty);
			}
			rep(j,xm+1) {
				int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xm-j,1);
				if (tx!=M && ty!=-M) chmin(res, tx-ty);
			}
		}
	}
	return res;
}

signed main() {
	cin >> k >> s;
	n = s.size();
	int res = rec(0,n-1,k,1);
	if (res==-M) cout << "NG" << endl;
	else cout << "OK" << endl << res << endl;
}

https://beta.atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a