SRM574 Div1 Easy - TheNumberGame

問題

先手が数字a、後手がbを持っており、どちらも0の桁はない
各ターンで各プレイヤーは自分の数字を反転するか最後の桁を消すかを選ぶ
途中で両者の数字が一致したら先手の勝ちで、いつまでも一致しない場合は後手の勝ちになる
両者が最善を尽くすときどちらが勝つか判定せよ

1 <= a, b < 10^9

解法

aか反転したaの連続する部分列にbが存在すれば先手が勝ち、そうでなければ後手の勝ち
前者のときはaの両端を削ってbに近付ければいつかは必ず一致する
(bが逃げるには数字を削るしかなく、最終的に数字が空になって一致する)
後者のときは後手は毎ターン数字を反転させてればいい

class TheNumberGame {
public:
	string determineOutcome(int a, int b) {
		string x = to_string(a), y = to_string(b);
		int n = x.size(), m = y.size();
		if (n<m) return "Manao loses";
		rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins";
		reverse(all(x));
		rep(i,n-m+1) if (x.substr(i,m)==y) return "Manao wins";
		return "Manao loses";
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12474&rd=15494

SRM573 Div1 Easy - TeamContest

問題

大学に人が3n人いて、i人目の強さはa[i]である
これらの3n人から3人チームをn組作る
3人チームの強さは3人の強さの最大値と最小値の和で決まる
0〜2人目が一緒にチームを組むことはもう決まっている
他の3n-3人のチーム分けを工夫すると、このチームより強いチームは最大何組作れるか

1 <= n <= 16
1 <= a[i] <= 10^6

解法

貪欲
ややこしいから最初の3人のチームの強さをkとし、その3人は除外して、残った人数を3nとする

まだ組になっていない人のうち最も強い人をチームの最大値担当として1人選ぶ
この人の強さをxとする
次にk-xを超える最小の強さを持つ人を1人探し、居たらその人を最小値担当として選ぶ
この人の強さはyとする
y以上x以下の強さを持つ人がいれば、そのうち最も弱い人を選び、この3人をチームにする

↑この流れを繰り返すのが最善

class TeamContest {
public:
	int worstRank(vector<int> a) {
		int k = max(a[0],max(a[1],a[2])) + min(a[0],min(a[1],a[2]));
		rep(i,3) a.erase(a.begin());
		sort(a.rbegin(), a.rend());
		int n = a.size(), res = 1, r = n-1;
		rep(l,n) {
			while (r>=0 && a[l]+a[r]<=k) r--;
			if (l+2<=r) res++, r -= 2;
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12470&rd=15493

SRM572 Div1 Easy - NewArenaPassword

問題

topcoderのパスワードをsにしていた
ある日「パスワードの最初のk文字と最後のk文字は一致していないといけない」という新ルールが出来た
新ルールを守るようなパスワードに変更するとき、sから変更する文字数の最小値を求めよ

1 <= |s| <= 50
1 <= k <= |s|

解法

sの長さをnとすると、条件は
「i文字目とi+n-k文字目が一致する (0<=i

class NewArenaPassword {
public:
	int minChange(string s, int k) {
		int n = s.size(), res = 0;
		rep(i,k) {
			int a[26] = {}, sz = 1;
			for (int j=i; j<n; j+=n-k, sz++) a[s[j]-'a']++;
			res += sz - *max_element(a,a+26);
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12386&rd=15492

ARC081 F - Flip and Rectangles

問題

h*wのマス目があり、各マスの色は黒か白である
「ある行[列]を選び、その行[列]の全てのマスの色を反転する」という操作を任意の回数行える
黒いマスのみを内側に含む長方形の面積の最大値を求めよ

2 <= h, w <= 2000

解法

タテかヨコの長さが1の長方形は明らかに自由に選べる
そうでない場合は？
2*2マスの正方形のうち黒マスを偶数個含むようなものは、操作によって4マスとも黒マスにすることができる
そういう正方形のみからなる任意の長方形も全部黒マスにできる (具体的には解説pdfの通り)
逆に奇数個含むような正方形はどう操作をしても無理
よって後者の正方形を内側に含まないような長方形のうち面積最大のものを求めればいい
これは蟻本p298のヒストグラムの最大長方形をスタックで求めるやつとほぼ同じようにできる

蟻本のやつ一回読んで理解できなくて投げたのは覚えてた
そろそろ上級編も読んだ方がいいかも・・

int h, w, ng[2020][2020], x[2020], res;
string s[2020];

signed main() {
	cin >> h >> w;
	res = max(h,w);
	rep(i,h) cin >> s[i];
	rep(i,h) {
		rep(j,w-1) {
			if (i && !(s[i-1][j]^s[i-1][j+1]^s[i][j]^s[i][j+1])) x[j]++;
			else x[j] = 1;
		}
		stack<int> s;
		rep(r,w) {
			while (!s.empty() && x[s.top()]>=x[r]) {
				int t = s.top(); s.pop();
				int l = (s.empty() ? -1 : s.top());
				chmax(res, x[t]*(r-l));
			}
			s.push(r);
		}
	}
	cout << res << endl;
}

https://beta.atcoder.jp/contests/arc081/tasks/arc081_d

EducationalCF53 E - Segment Sum

かなり残念な落とし方をした
4完でもhighest更新したからこれも通ってれば・・😠

問題

L以上r以下の整数のうち、各桁の数字の種類がk以下であるものの和を求めよ

1 <= L <= r < 10^18
1 <= k <= 10

解法

とりあえず求めるものは (r以下の条件を満たす数字の和) - (L-1以下の〜) としてok
1桁ずつ考える
まず1の位に注目し、
Σ (条件を満たし、かつ1の位がxになるような数字の個数) * x (1 <= x <= 9)
を求める
これはありふれた桁dpを、1の位の遷移だけxに絞るようにちょっと書き換えるだけで求められる
10の位以上も同様に求め、それらを足し合わせることで答えが得られる

桁dpのテーブルは
dp[i][j][L][b]: 上からi桁目まで決まり、nより小さいことが確定し(j=1)、leading-zeroは終了し(L=1)、使った数字の組み合わせがbであるような数字の個数
とすればいい
leading-zeroに気を付けないと、例えばnが3桁のとき、11って数字が0と1の2種類の数字を使った数字として扱われてしまう(011)

実装

時間制限が1sで割とギリギリだから無駄な処理はなるべく削った
気を付けたことは
・0〜2^10のpopcountを事前に求めておく(cnt)
・10の0〜18乗も事前に求めておく(ten)
・dp[〜]が空のときはcontinueする

本番では最後のcontinueをしてなくてTLEした
これ書き足しただけで10倍くらい速くなった
これ書かないと無駄な処理が結構増えるのはわかってたけど、そこまで速度に差が出るとは知らなかった & 別にcontinueしなくても答えは変わらないから、別に書かなくてもいいものだと自分の中で思ってた
もう一生continueを省略することはないと思う

関係ないけどコドフォはコードに長めの日本語のコメントが含まれるとJudgement Failedってエラーが出るらしい
ジャッジが詰まってる系だと思ってイラついて連投してたら注意された

#define int long long

int l, r, k, cnt[1<<10], ten[33];

int dig(const string &s, int x, int y) {
	int n = s.size(), dp[22][2][2][1<<10] = {};
	dp[0][0][0][0] = 1;
	rep(i,n) rep(j,2) rep(l,2) rep(b,1<<10) if (dp[i][j][l][b]) {
		if (i==x) {
			if (cnt[b|(1<<y)]>k) continue;
			if (j==0 && s[i]-'0'<y) continue;
			(dp[i+1][j|(s[i]-'0'>y)][1][b|(1<<y)] += dp[i][j][l][b]) %= mod;
		} else {
			rep(t,(j ? 10 : (s[i]-'0')+1)) {
				int bit = (l==0 && t==0 ? b : b|(1<<t));
				if (cnt[bit]>k) continue;
				(dp[i+1][j|(s[i]-'0'>t)][l|(t!=0)][bit] += dp[i][j][l][b]) %= mod;
			}
		}
	}
	int res = 0;
	rep(i,2) rep(l,2) rep(j,1<<10) (res += dp[n][i][l][j]) %= mod;
	return res;
}

int ans(int n) {
	string s = to_string(n);
	int res = 0, m = s.size();
	rep(i,m) reps(j,1,10) {
		if (i==0 && s[i]-'0'<j) continue;
		(res += dig(s,i,j) * ten[m-i-1] %mod * j) %= mod;
	}
	return res;
}

signed main() {
	rep(i,1<<10) cnt[i] = __builtin_popcount(i);
	ten[0] = 1;
	reps(i,1,33) ten[i] = ten[i-1]*10 %mod;
	cin >> l >> r >> k;
	cout << (ans(r) - ans(l-1) + mod) %mod << endl;
}

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

CF518 Div2 D - Array Without Local Maximums

これ割とあからさまなdpじゃない？

問題

いくつかの要素が-1になっている長さnの数列が与えられる
↓の条件を満たすように-1を1〜200に変えるとき、何通りの数列が作れるか
1) a[1] <= a[2]
2) a[n-1] >= a[n]
3) a[i] <= max(a[i-1], a[i+1]) (1 < i < n)

2 <= n <= 10^5

解法

dp[i][j][k]: i-1番目まで埋め終わってて、a[i-1]をjに変えて、a[i-1]とa[i-2]の関係がkであるような数列の個数
k=0) a[i-2] > a[i-1]
k=1) a[i-2] = a[i-1]
k=2) a[i-2] < a[i-1]

条件3よりk=0,1のときはa[i]は自由に決められる
k=2のときはa[i-1] <= a[i]となるようにしないといけない
よってdp[1][j][2]のみ1にしておけば条件1は勝手に満たせる
また条件2より答えは Σ dp[n][j][0,1]

遷移はa[i]≠-1のときは普通に
dp[i+1][a[i]][〜] += dp[i][j][k] (1 <= j <= 200)
そうじゃないときはまともにやると
dp[i+1][j'][〜] += dp[i][j][k] (1 <= j <= 200, 1 <= j' <= 200)
でTLEするけど、imos法を使えばj'のループが必要なくなる

実装

メモリ制限は512mbだから節約しなくても足りる

int n, a[100100], dp[100100][222][3];

signed main() {
	cin >> n;
	rep(i,n) cin >> a[i];
	if (a[0]!=-1) dp[1][a[0]][2] = 1;
	else reps(i,1,201) dp[1][i][2] = 1;
	reps(i,1,n) {
		if (a[i]==-1) {
			reps(j,1,201) rep(k,3) {
				if (k!=2) {
					if (j>=2) (dp[i+1][1][0] += dp[i][j][k]) %= mod,
							  (dp[i+1][j][0] += mod-dp[i][j][k]) %= mod;
					(dp[i+1][j][1] += dp[i][j][k]) %= mod;
					if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod;
				}
				else {
					(dp[i+1][j][1] += dp[i][j][k]) %= mod;
					if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod;
				}
			}
			rep(k,3) if (k!=1) reps(j,1,201) (dp[i+1][j][k] += dp[i+1][j-1][k]) %= mod;
		} else {
			reps(j,1,201) rep(k,3) {
				if (k!=2) (dp[i+1][a[i]][a[i]==j ? 1 : (j<a[i] ? 2 : 0)] += dp[i][j][k]) %= mod;
				else if (j<=a[i]) (dp[i+1][a[i]][(a[i]==j ? 1 : 2)] += dp[i][j][k]) %= mod;
			}
		}
	}
	int res = 0;
	reps(i,1,201) rep(j,2) (res += dp[n][i][j]) %= mod;
	cout << res << endl;
}

http://codeforces.com/contest/1068/problem/D

CF518 Div2 C - Colored Rooks

こんなしょうもない構築が解けなくてまたdiv1に戻れなかった
もう深夜のコンテストはレート落ちるの覚悟で出るべきかな・・

問題

色がn個あり、m個のペア(a[i],b[i])も与えられる
10^9 * 10^9のチェス盤があり、好きな位置にルークを最大5000個置くことができる
各ルークには色を塗る必要がある
↓の条件を全て満たすようなルークの置き方とそれぞれの色の組み合わせを1つ求めよ
1) n個の色それぞれで塗られているルークが少なくとも1つずつある
2) 同じ色のルークは連結である
3) 色aのルークの集合と色bの集合は、ペア(a,b)が存在するときのみ連結である
あるルークの集合が連結であるというのは、どのルークからも同じ集合のルーク上のみを通って同じ集合の任意のルークに辿り着けることを表す

1 <= n <= 100
0 <= m <= min(1000, n(n+1)/2)
答えは必ず1つ以上存在する

解法

まず色iのルークを座標(i,i)に1つ置く これで条件1はクリア
次に各ペアを1個ずつ見ていき、色a[i]のルークを(r+1,a[i])、b[i]を(r+1,b[i])に置く
(r: ルークが1個以上置かれている列のうち最も右の列のx座標)
こうすることで条件2,3を破らないようにペアを全て連結にすることができる

int n, m, a, b, r;
vector<pair<int,int> > res[111];

signed main() {
	cin >> n >> m;
	reps(i,1,n+1) res[i].push_back({i,i});
	r = n+1;
	rep(i,m) {
		cin >> a >> b;
		res[a].push_back({r,a}), res[b].push_back({r++,b});
	}
	reps(i,1,n+1) {
		cout << res[i].size() << endl;
		each(j,res[i]) cout << j.first << ' ' << j.second << endl;
	}
}

http://codeforces.com/contest/1068/problem/C