情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Grand Contest 029

AtCoder Grand Contest 029 (AGC029)に参加しました!
AtCoder Grand Contest 029 旧版
AtCoder Grand Contest 029 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Grand Contest 029
rated
12/15(土) 21:10 ~ 23:20 (140分)
300-600-700-800-1200-2200 (6問)
ペナルティ: 5分

方針

A早解きを行い、その後BCDを全部読む
順位表と照らし合わせながら、簡単そうなのから順に実装していけば間に合うはず!

A - Irreversible operation

問題文

問題文

N 個のオセロの石が一列に並んでいます。
それぞれの石の状態は長さ N の文字列 S によって表されており、S_i=B のとき左から i 番目の石の表面は黒色、S_i=W のとき左から i 番目の石の表面は白色となっています。
ここで、以下の操作を行うことを考えます。

  • 左から i 番目の石の表面が黒色、左から i+1 番目の石の表面が白色であるような i (1 \leq i < N) を一つ選び、その 2 つの石をともに裏返す。

つまり、左から i 番目の石の表面が白色、左から i+1 番目の石の表面が黒色になるようにする。
最大で何回この操作を行うことができるか求めてください。

制約

  • 1 \leq |S| \leq 2\times 10^5
  • S_i=B または W

さて、まずは実験しながら考えていきます。
まず、一番左側にあるWは絶対にこれ以上変化しません。同様に、一番右側にあるBも変化しませんね。
これを考えていくと、どこかでBが左側、Wが右側になる場所があります。
これは、操作を繰り返すと必ず入れ替えることが可能です。これを証明します。
今、ある部分文字列であって、BB...BBWW...WWとなっているところがあるとします。
これは、一番左側にあるWBの入れ替えをBの文字数だけ繰り返すことで、WBB...BBWW...WWと置くことができます。
もっと複雑にWWBBWBWBWWとかなっていても、同様の手法でWBの手前にうごかす操作を繰り返せば最終的に必ず全てのWBの左側に持ち込むことができます。
では、この時の操作回数はどうなるでしょうか?
これは、あるWについて、自身の左側にあるB全てと入れ替えるので、各Wについて自身より左側にあるBの数を数えれば良いです。
また、この時左から順にみていけば、Bが出てきたときにカウントを1個増やし、Wが出てきたら加算するというコードで済む為、計算量は{\rm O}(|S|)です。
ちなみに、答えはBB...BBWW...WWのときが最大で、(\frac{|S|}{2})^2=10^{10}になるため、32bitの範囲を超えることに注意しましょう。

ソースコード(C++)

#include<iostream>
int main() {
	std::string S;
	std::cin >> S;
	long long ans = 0, B = 0;
	for (int i = 0;i < S.length();++ i) {
		if (S[i] == 'B') ++ B; else ans += B;
	}
	std::cout << ans;
	return 0;
}


B - Powers of two

問題文

問題文

高橋君は正整数が書かれたボールを N 個持っています。i 番目のボールに書かれている正整数は A_i です。
高橋君は N 個のボールからいくつかのペアを作って、それぞれのペアのボールに書かれた数の和が 2 べきとなるようにしたいです。
ただし、同じボールが複数のペアに属することはできません。
最大でいくつのペアが作れるか求めてください。
ただし、正整数が 2 べきであるとは、ある非負整数 t を用いて 2^t と書けることを指します。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^9
  • A_i は整数

さて、ペアに関してですが、ここでA_iがより大きい物から順にペアを決めるものとします。
理由としては、まずA_Nとペアとなる値がA_iであるとして、A_i \leq A_NよりA_N < A_i + A_N \leq 2 \cdot A_Nより、A_iの値はただ一つに定まります。
また、ペアを作らないという選択より作るという選択の方が自明に最適なので、もしそのようなA_iがあるならペアにすべきです(これを逃すとA_Nのペアは無くなるため)。
さて、そうと決まればまずはA_iはソートしておきましょう。
次に決めていくわけですが、そのまま探すと計算量{\rm O}(N^2)でTLEします。
そこで、考え方をちょっと変えて、先にペアの合計値を大きい方から決め打ちます。
これなら、ペアの合計値は2冪なので高々{\rm O}(\log (\max (A_i)))しかないため、計算量は{\rm O}(N \log (\max (A_i)))で、これは十分間に合います。

ソースコード(C++)

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	static int N, A[200000], ans = 0;
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> A[i];
	sort(A, A+N);
	for (int i = 1 << 30;i > 0;i >>= 1) {
		for (int j = 0, k = N - 1;j < k;) {
			if (A[j] < 0 || A[k] > 0 && A[j] + A[k] < i) ++ j;
			else if (A[k] < 0 || A[j] + A[k] > i) -- k;
			else {
				A[j] = A[k] = -1;
				++ ans;
			}
		}
	}
	cout << ans;
	return 0;
}


C - Lexicographic constraints

問題文

問題文

N 個の文字列が一列に並んでおり、どの隣り合う 2 つの文字列に対しても、左に書いてある文字列の方が右に書いてある文字列よりも辞書順で小さいことが分かっています。
つまり、左から i 番目の文字列を S_i としたときに、辞書順で S_1< S_2 < ...< S_N が成り立っています。
S_i の長さが A_i であると分かっているとき、S_1,S_2,...,S_N に含まれる文字の種類数として考えられる最小の値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^9
  • A_i は整数

まず、A_i < A_{i+1}の時を考えましょう。
これは簡単です、単にS_iの後ろにaを文字数と一致するまで付加すれば、いっさい文字数を増やさず作れるので最適です。
では、逆にA_i \geq A_{i+1}の時はどうしましょうか?
これもまた簡単で、まず文字を一致するまで削り、次にその時の一番後ろの文字を1個分先の文字へ進めます。
ここで、もしもあなたが文字数を決め打っているならば、その文字数を超えた文字になった瞬間に今の文字をaに戻し、1個手前の文字を代わりに1個分先の文字へ進め…と文字数を超えない文字になるまで繰り返します。
このシミュレーションは、高々{\rm O}(N)で終わります。
ただ、このシミュレーションは文字数を決め打っていることを前提にしているため、そこを何とかする必要があります。
まず、もし文字数がN個あるなら、各S_ii番目の文字のみを使えば成立するので、つまりN文字以下であることは確定です。
次に。もしある文字数で足りたなら、それより多い文字数では絶対に足ります。逆にある文字数で足りないならそれより少ない文字数では足りません。
ということは、文字数に対して二分探索を、シミュレーションを成功できたかどうかを鍵として行うことができます。
計算量は{\rm O}(N \log(N))です。

ソースコード(C++)

#include<iostream>
#include<stack>
using namespace std;
int main() {
	static int N, A[200001] = {};
	cin >> N;
	for (int i = 1;i <= N;++ i) cin >> A[i];
	int ans = 0, max = N, mid, halfDiff, tmp;
	while(halfDiff = max - ans >> 1) { // 二分探索
		bool check = false;
		mid = ans + halfDiff;
		stack<pair<int, int> > stk;
		for (int j = 1;j <= N;++ j) { // シミュレーション
			if (A[j - 1] >= A[j]) { // 文字数が減るパターン
				while (!stk.empty() && stk.top().first > A[j]) stk.pop(); // 超過部分は削る
				if (stk.empty() || stk.top().first < A[j]) stk.push(make_pair(A[j], 1)); // stackに入ってないならA[j]番目はaでしょ
				while (++ stk.top().second > mid) {
					tmp = mid == 1 ? 1 : stk.top().first;
					if (tmp == 1) goto break_label; // 変化不能、よってシミュレーション失敗
					stk.pop();
					if (stk.empty() || stk.top().first != tmp - 1) stk.push(make_pair(tmp - 1, 1));
				}
			}
		}
		check = true;
		break_label:;
		(check ? max : ans) = mid;
	}
	cout << max;
	return 0;
}


D - Grid game

問題文

問題文

高橋君と青木君は HW 列のマス目を使ってゲームをします。
このマス目上には N 個の障害物があり、i 番目の障害物は (X_i,Y_i) にあります。
ただし、ij 列目 (1 \leq i \leq H, 1 \leq j \leq W) にあるマスを (i,j) で表すことにします。
また、どの障害物も (1,1) にはなく、(1,1) には 1 つの駒が置いてあります。
そこで、高橋君と青木君は高橋君から始めて、交互に以下の行動のいずれかを行います。

  • 駒を隣り合うマスに動かす。

ただし、駒の位置を (x,y) としたとき、高橋君は (x+1,y) にのみ、青木君は (x,y+1) にのみ駒を動かすことができる。
また、動かすことのできるマスが存在しない、もしくは、動かす予定のマス目に障害物がある場合はこの行動をとることはできない。

  • 駒を動かさず、マス目を元の状態のまま行動を終える。

2 回連続で駒が動かされなかった場合、そこでゲームを終了します。
高橋君はできるだけ多くの回数の行動 (駒を動かさないのも含む) を行ってゲームを終えたいですが、青木君はできるだけ少ない回数の行動を行ってゲームを終えたいです。
このとき、高橋君が行うことになる行動の回数は何回か求めてください。

制約

  • 1 \leq H,W \leq 2\times 10^5
  • 0 \leq N \leq 2\times 10^5
  • 1 \leq X_i \leq H
  • 1 \leq Y_i \leq W
  • i \neq j のとき (X_i,Y_i) \neq (X_j,Y_j)
  • (X_i,Y_i) \neq (1,1)
  • X_i,Y_i は整数

さて、まず高橋君が動かなかったらどうなるでしょうか?
答えは、青木君が動かないので即座にゲームが終了します。
よって、高橋君は動ける限り動き続けるしかなく、行動の自由があるのは青木君だけであるということが分かります。
ということは、まず第n回目の高橋君の移動が終わった時点ではx座標はn+1になっているはずです。
青木君がすべきは、なるべくx座標で見て近い障害物のうち移動可能なものを選んで、y座標を合わせてからひたすら移動しないを繰り返すだけですね。
図を見てください。
f:id:CuriousFairy315:20181216024905p:plain
これはサンプル2で、灰色と黒は障害物、赤は高橋君の移動、緑は青木君の移動となっています。
図から分かるように、障害物をX_i昇順に並び替えると、貪欲にシミュレーションするだけで答えが求まるのが分かりますね(これ本当に800点か?)。
もちろん計算量はソートに依存するので{\rm O}(N \log N)です。

ソースコード(C++)

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int H, W, N, diff = 0;
	static pair<int, int> point[200000];
	cin >> H >> W >> N;
	for (int i = 0;i < N;++ i) cin >> point[i].first >> point[i].second;
	sort(point, point+N); // X昇順、同値ならY昇順
	for (int i = 0;i < N;++ i) {
		if (point[i].first - point[i].second - diff > 0) H = min(H, point[i].first - 1); // この障害物を使って邪魔する
		else if (point[i].first - point[i].second - diff == 0) ++ diff; // 青木君が移動できないので、上を抜けるしかない
	}
	cout << H;
	return 0;
}


結果

oox--- 2完(900点) 10:46-92:00(3WA) / 107:00
598位 パフォーマンス: 1649
レート: 16611660(-1)

コンテスト統計
パフォーマンスの算出にはac-predictorを用いています。
スコア0点300点600点800点900点1000点1100点1300点1500点1600点1700点1800点2400点2800点3600点3700点3800点4600点4800点5800点
時間1:4754:5963:389:4275:5454:25175:35128:4752:5624:5554:1538:47103:4167:56137:20111:5768:34150:4187:20
順位17586836816793873773433423412711961895047171615981
パフォーマンス1831563156515671902191619681969197120942265228429602988340434263449362436634347

パフォーマンス040080012001600200024002800320036004000
スコア0点300点300点300点900点1600点2400点2400点3600点4600点5800点
時間184:2046:5813:30140:53152:42131:2169:44116:3568:3499:24
順位1758位1757位1492位1075位646位323位151位69位28位9位2位

感想

これは、解けるべき問題だった……!
C問題はstackとqueueを逆に書いて間に合わない、という大失態でした。
また、D問題がかなり簡単な問題(順位表には出てないけど)だったので、これも解くべきでしたね。
完全にミスです……やっぱり青適性なのかなぁ……。