AGC039 参加記録

#AtCoder Grand Contest 039
公式の解説を見る前に記述しています。

## A - Connection and Disconnection

``` c++:ConnectionandDisconnection.cpp
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
 
#define INF 2e9
 
#define REP(i,n) for(int i = 0; i < n;++i)
#define REPA(i,a,n) for(int i = a; i < n; ++i)
#define ALL(a) a.begin, a.end()
 
using namespace std;
 
int main(void) {
 
	string S;
	long long K;
 
	cin >> S >> K;
	int size = S.size();
	char c1, c2; // 現在の文字、一つ前に調べた文字
	int index1 = 0, index2 = size; // 頭から数えて2種類目の文字の位置、末尾版
	int len = 1;
	long long ans = 0;
 
	c1 = S[0];
	c2 = S.back();
	if (c1 == c2) { // 先頭と末尾の文字が同じ
		index1++;
		index2--;
		REPA(i, 1, size) { // 先頭何文字続いてる？
			if (c1 != S[i]) {
				break;
			}
			index1++;
		}
		
		for (int i = size - 2; i >= 0; i--) { // 末尾何文字続いてる？
			c1 = S[i];
			if (c1 != c2) {
				break;
			}
			index2--;
		}
	}
 
	// 文字が全て同じ時index1は末尾を越え、index2は先頭を指している
	if (index1 > index2) {
		cout << (size * K) / (long long)2 << endl;
		return 0;
	}
 
	// 先頭末尾に関係なく置換しなければいけない数を数える
	c2 = S[index1];
	REPA(i, index1 + 1, index2 + 1) {
		c1 = S[i];
		if (c1 == c2) {
			REPA(j, i, index2 + 1) { // 何文字続いてる？
				c2 = S[j];
				if (c1 == c2) {
					len++;
				}
				else {
					break;
				}
				i++;
			}
			ans += len / (long long)2; // 置換回数は[連続した文字列長/2]回(切り捨て)
			len = 1;
		}
		else c2 = c1;
	}
	ans *= K;
 
	// 境界の数 = K-1
	len = index1 + (size - index2);
	ans += (K - 1) * (long long)(len / 2);
 
	// 先頭
	ans += index1 / 2;
 
	// 末尾
	ans += (size - index2) / 2;
 
	cout << ans << endl;
	
	return 0;
}
```

文字が2個連続している場合は左右どちらかの文字を置換し、3文字なら真ん中の文字を1文字置換することで連続した文字はなくすことができる。
4文字以上も同様なので、連続した文字列長の1/2(切り捨て)回置換すると連続した文字は連続でなくなる。

文字列の先頭と末尾の文字が同じだった場合、文字列Sを連結した際に連結部分に連続した文字が現れるので、繰り返し回数K-1回その計算を含めなくてはいけない。

実装したソースコード上では、先頭と末尾の文字が同じだった場合、Sを全て連結した際の先頭と末尾と結合部分とそれらを除いたSの内側の部分で計算を別にした。何文字連続しているかは以下の通り。

 - 先頭の長さ\[index1](末尾と同じ文字でないなら0)
 - 末尾の長さ\[index2](Sの長さ - index2)
 - 結合部分の長さ \[index1 + Sの長さ - index2](掛けるK-1回置換)
 - Sの内部 [index1, index2]の区間(内部に何種類の文字が何個繋がっているかも計算する)

解放はすぐに思いついたが実装にかなりの時間を使ってしまった。もっと簡素な書き方があったはず。

## B - Graph Partition
ACできるコードは書けなかったので省略。

問題の理解に時間がかかってしまった。例題3をもとに図解してみる。

例題3で与えられるグラフは以下のようなグラフ。（説明のために頂点の順序はめちゃくちゃ）
![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277953/1a784ffb-f761-1049-feb7-3d830bc75451.png)
これをK個のグループに分けてV1...Vkと名付ける。例えば3つに分けた場合。
![3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277953/aa5b4a45-4a12-6e12-97c0-3a358746741f.png)
このとき、全ての辺はVnとVn+1(もしくはVn-1とVn)をつないでなければいけない。要はV1に含まれる頂点と結ばれている頂点はV2に含まれている頂点と繋がれてなければいけない。
上記の画像の例だと1と5がつながっているのでNG。もちろん1と4がつながっているのも条件を満たしていないのでNG。
そんな条件を満たすグループ分けのうち最大グループ数はいくつか？というのが問題。

以下考えた解法。ACしていないので解けるとは保証しません。
上記の1と4のようにグループ内に辺があるとNGなので、1と結ばれている頂点は必ず別グループに属する。同様に、2と結ばれている頂点は2とは別のグループ、3と結ばれている頂点は………を繰り返し、2グループに分割する。すると以下の画像のようになる。（ここで2グループに分けられないと分割が不可能）
![4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277953/be682958-007e-585c-0440-7bfb85d49168.png)
辺が多いのでグループ同士で表すと以下。
![5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277953/d8fc4921-b226-b030-8e72-a3dd5f5300b3.png)
ここで、例えば6は245のいずれかと結ばれていることは間違いないが1と3と同じV1である必要はないかもしれないので、V3になれるかを考える。すると、2の所属するV2と結ばれていればいいだけなのでV3にしてよいことがわかる。
これをV1,V2に対して繰り返したあと、新たに生まれたV3,V0(説明上V1の左側に来るのでV0)に対して繰り返して、できたグループの数が答えとなる。
 ![6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/277953/59490400-f3d0-7a5d-2e04-90f22bf59bba.png)

## C - Division by Two with Something
ACできるコードは書けなかったので省略。

Xが2進表記で与えられることと、N≦200000であることから文字列でXを受け取るのは間違いなさそう。
2進数で考えると行う操作は単純で、Xをビット列とし、

- 奇数なら右シフトしてN-1ビット目に0を立てる
- 偶数なら右シフトしてN-1ビット目に1を立てる

Xの偶奇は1ビット目が立っているかどうかなので、ようは右シフトするときに1ビット目を反転させたものをN-1ビット目の値にするだけ。

操作は簡単だが戻らない条件を求められなかったのでここで断念（k > 2^(n-1)の値は戻らない？）