SRM747 Div1 Medium - TieForMax

人生初黄色記念
次参加してeasy hackとかで即落ちそう

最近競プロより優先してやるべきことが多いせいでだいぶ競プロから離れてる
考察力も落ちたと思うけど、それよりも実装力が落ちたのを強く実感する
前は絶対やらなかったようなバグをよく生んでる

今の感じだと行けたとして黄色が最終到達点になる気がしてる
前ほど競プロをがっつりやる時間が今後たぶんない
人生でここまで熱中できたものは麻雀とlolぐらいしかなかった😢
出来ればその2つより先に出会いたかった・・

解いた問題で使った知識を記憶に定着させるのを主な目的として記事を書いてて、それ自体は全く苦ではなかったんだけど、今時間的にキツイので今後はわからん
変色とかオンサイト参加とかがあったら記念に書くかもしれない

問題

m個のブロックがあり、それぞれのブロックに対して「n個の山のどれかに等確率で積む」という操作をする
操作終了後、ブロックが一番多く置かれている山が複数存在する確率を求めよ

1 <= n, m <= 50

解法

dp[i][j][k][L]: i番目の山まででj個のブロックを置き、ブロックの最大値がkで、k個のブロックが置かれている山がL個ある状態になる確率
Lを0〜50までとると遷移込みでO(n^2 m^3)になって間に合わないけど、L>=2は全部まとめられるのでO(n^2 m^2)で間に合う
遷移は普通にi番目の山に [0, m-j] 個置く場合それぞれを考えて、x個置くなら場合の数は (m-j)Cx 通りあるから〜みたいな感じで

class TieForMax {
public:
	double pa[55][55];

	double comb(int n, int r) {
		if (r<0 || r>n) return 0;
		if (r==0) return 1;
		if (pa[n][r]) return pa[n][r];
		return pa[n][r] = (comb(n-1, r-1) + comb(n-1, r));
	}

	double getProbability(int m, int n) {
		if (n==1 || m==1) return 0.0;
		double dp[55][55][55][3] = {}, p[55] = {};
		p[0] = 1.0;
		reps(i,1,55) p[i] = p[i-1] / n;
		dp[0][0][0][0] = 1.0;
		rep(i,n) rep(j,m+1) rep(k,m+1) rep(l,3) if (dp[i][j][k][l]) rep(x,m-j+1)
			dp[i+1][j+x][max(k, x)][(x>k ? 1 : min(l+(x==k), 2))] += dp[i][j][k][l] * comb(m-j,x) * p[x];
		double res = 0;
		reps(i,1,55) res += dp[n][m][i][2];
		return res;
	}
};

こういう多次元だけど発想はシンプルなdpはtopcoder過去問埋めで結構やった気がする

https://community.topcoder.com/stat?c=problem_statement&pm=15237&rd=17396

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