はまやんはまやんはまやん

hamayanhamayan's blog

CSAcademy #22 問題と解説

競技プログラミング

https://csacademy.com/contest/round-22/

問題

Triangle Count

N本の棒があり、長さが分かっている。
この中から任意の3本を選んで三角形が作れる組合せは何通り？

Frequency Exception

N要素の配列がある。
この中で配列の中に現れる回数が他と異なる要素が1つある。
それを探せ。

Black Shapes

H(=N)行W(=M)列のマス目がある。
それぞれ白(=0),黒(=1)で塗られている。
マス目の中の白マスをどれか1つだけ黒に塗って、黒を最も多く隣接させる。
最大、何個黒を隣接させられるか。

Distinct Rotations

0と1と?から成る文字列がある。
?に0か1を入れて回転させた時の周期が最小になるものを答えよ。
例）010010ならば 010010 -> 100100 -> 001001 -> 010010なので周期3

Limited Swaps

要素数Nの配列Aが与えられる。
この配列の隣接している要素を最大K回スワップして、辞書順最大となる配列A'は？

以下、解説






















解説

Triangle Count

三角形が作れる条件は「最長の辺 < 他の2辺の和」が満たされることなので、任意の3本を選ぶ組合せを全通り試してチェックしていけばよい。

int N, A[101];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	sort(A, A + N);

	int ans = 0;
	rep(i, 0, N) rep(j, i + 1, N) rep(k, j + 1, N) {
		if (A[k] < A[i] + A[j]) ans++;
	}
	cout << ans << endl;
}

Frequency Exception

  • 「cnt[i] := 数iが何回でるか」を数える
  • 「cnt2[i] := i回出る数が何個あるか」を数える

あとは、cnt2[i] == 1となるiを探して、それをcnt[ii] == iとなるiiを探せば答え。

int N;
int A[1010];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	
	map<int, int> cnt;
	rep(i, 0, N) cnt[A[i]]++;

	map<int, int> cnt2;
	for (auto p : cnt) cnt2[p.second]++;

	for (auto p : cnt2) {
		if (p.second == 1) {
			for (auto pp : cnt) {
				if (pp.second == p.first) {
					cout << pp.first << endl;
					return 0;
				}
			}
		}
	}
}

Black Shapes

merge関数で、UnionFindを使いながら、黒の隣接成分を作っていく。
UnionFindでマージする時にcntを足し合わせながらマージしていくと隣接成分の個数も求まる。
後は、sol関数で、各白マスについて、そのマスを黒にしたときの隣接成分の個数を求め、その最大を取ればよい。

template<int um> class UF {
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------------------------
int H, W;
int B[1010][1010];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
//-----------------------------------------------------------------------------------
UF<1010101> uf;
int cnt[1010101];
void merge() {
	rep(i, 0, H * W) cnt[i] = 1;
	rep(y, 0, H) rep(x, 0, W) if(B[y][x]){
		rep(i, 0, 4) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || W <= xx) continue;
			if (yy < 0 || H <= yy) continue;
			if (!B[yy][xx]) continue;

			if (uf[y*W + x] != uf[yy*W + xx]) {
				int c = cnt[uf[y*W + x]] + cnt[uf[yy*W + xx]];
				uf(y*W + x, yy*W + xx);
				cnt[uf[y*W + x]] = c;
			}
		}
	}
}
//-----------------------------------------------------------------------------------
int sol(){
	int res = 0;
	rep(y, 0, H) rep(x, 0, W) if (B[y][x] == 0) {
		set<int> b;
		rep(i, 0, 4) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || W <= xx) continue;
			if (yy < 0 || H <= yy) continue;
			if (!B[yy][xx]) continue;

			b.insert(uf[yy*W + xx]);
		}

		int r = 0;
		for (int i : b) r += cnt[i];
		r++;
		res = max(res, r);
	}
	return res;
}
//-----------------------------------------------------------------------------------
int main() {
	cin >> H >> W;
	rep(y, 0, H) rep(x, 0, W) scanf("%d", &B[y][x]);
	
	merge();
	cout << sol() << endl;
}

Distinct Rotations

回転周期で全探索する。
以下、実験

0101 -> 周期2 "01"の連続
0000 -> 周期1 "0"の連続
010010 -> 周期3 "010"の連続

周期iの時は先頭から長さiのパターンが連続している時である。
全探索すべき回転周期であるが、これは必ず文字列の長さの約数になっている。
Nは最大10^5だが、これの約数はそんなに多くない(誰かが素因数分解した時の個数の多い数を列挙してくれてたサイトがあったんだけど、見当たらない)。

sol(int len) := 回転周期lenの時に作れる辞書順最小の答え(無理ならば"")
はO(N)で計算ができるため、全体として間に合う。

vector<int> enumdiv(int n) {
	vector<int> S;
	for (int i = 1; i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
	sort(S.begin(), S.end());
	return S;
}
//-----------------------------------------------------------------------------------
string S; int N;
//-----------------------------------------------------------------------------------
string sol(int len) {
	string buf = "";
	rep(i, 0, len) buf += "?";

	rep(i, 0, N / len) {
		rep(j, 0, len) {
			if (S[i*len + j] == '?') continue;
			if (buf[j] == '?') buf[j] = S[i*len + j];
			else if (S[i*len + j] != buf[j]) return "";
		}
	}

	rep(i, 0, len) if (buf[i] == '?') buf[i] = '0';

	string ans = "";
	rep(i, 0, N / len) ans += buf;
	return ans;
}
//-----------------------------------------------------------------------------------
int main() {
	cin >> S;
	N = S.length();

	auto e = enumdiv(N);
	for (int i : e) {
		auto ans = sol(i);
		if (0 < ans.size()) {
			cout << ans << endl;
			return 0;
		}
	}
}

Limited Swaps

先頭から順に埋めていく。
i番目に入れるべき数字は残っている数字の先頭K個分の中で最大のものである。
ここで実現すべきことは

  • 残りの先頭K個から素早く最大値を取り出す
  • 取り出したら消して先頭K個を正しく取れるようにする

セグメントツリーを使えば良さそうだが、単純にやるとダメ。
どうしようか。