ABC043 ARC059 の問題を解いてみました

## A問題
https://atcoder.jp/contests/abc043/tasks/abc043_a

問題を言い換えると、$1$から$n$までの総和を求める問題です。
($n=5$ならば、 $1 + 2 + 3 + 4 + 5 = 15$ )
単純な繰り返しで解いてもよいし、平均を用いても良いです。
~~~C++:繰り返しを用いる
#include <bits/stdc++.h>
using namespace std;
//Created by Karaju

int main() {
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) { //すべての数を足す
		ans += i;
	}
	cout << ans << endl;
	
	return 0;
}
~~~
~~~C++:平均を用いる
#include <bits/stdc++.h>
using namespace std;
//Created by Karaju

int main() {
	int n, ans = 0;
	cin >> n;
	ans = n * (n + 1) / 2; //平均を求める
	cout << ans << endl;
	
	return 0;
}
~~~
## B問題
https://atcoder.jp/contests/abc043/tasks/abc043_b

0: 文字列の右端に文字 0 が挿入される。
1: 文字列の右端に文字 1 が挿入される。
B: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の1文字が削除される。

上の表に従って作成された文字列を出力します。
おそらく、出入力例を確認したほうが理解しやすいです。

例えば、__01B0__ という入力が与えられたとすると、
0, 01, 0, 00 と変化していき、最終的な出力は __00__ となります。

~~~C++:pop_back
str.pop_back();
~~~
で文字列strの最後の文字を削除できます。(0文字では機能しないので注意)

~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	string s;
	cin >> s;
	string ans = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0') {
			ans += "0"; // 0 を挿入
		}
		else if (s[i] == '1') {
			ans += "1"; // 1 を挿入
		}
		else {
			if (ans.size() >= 1) {
				ans.pop_back(); //末尾の文字を削除
			}
		}
		
	}
	cout << ans << endl;
	
	return 0;
}
~~~
## C問題
https://atcoder.jp/contests/abc043/tasks/arc059_a

$N$個の整数をすべて同じ値に揃えるのに必要なコストの和を計算します。
コストは 元の数と変化した数との差の2乗です。
例として 3から6 に変化させるとすると、$(3-6)^2=(-3)^2=9$というコストになります。
制約は$-100\leqq a_i \leqq 100$ なので、この間の整数について調べれば良く、すべての場合を試すことによって求められます。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	int n;
	long long ans = 1e15;
	cin >> n;
	int li[n];
	for (int i = 0; i < n; i++) cin >> li[i];
	for (int i= -100; i <= 100; i++) { // -100 から 100 まで試す
		long long sum = 0;
		for (int j = 0; j < n; j++) {
			sum += (li[j] - i) * (li[j] - i); //コストを計算し加える
		}
		if (ans > sum) ans = sum; //最小コストを記録しておく
	}
	cout << ans << endl;
	
	return 0;
}
~~~
## D問題
https://atcoder.jp/contests/abc043/tasks/arc059_b

文字列tにおいて、その文字列の過半数の文字が同じならば、その文字列tをアンバランスであるとします。(2文字以上)
例えばnoonはアンバランスではなく、（半分は2なので、同じ文字は3つ必要）
meleeはアンバランスです。（半分は2.5なので、eが3つあり、アンバランス）
文字列sが与えられるので、アンバランスな部分があるか判定し、
アンバランスな部分があればアンバランスな位置を示し、（左右の位置を示す）
なければ、 <code>-1 -1</code> と出力します。


#### 部分点の獲得 

文字列にアンバランスな部分があるかを全探索で確かめれば、部分点は獲得できます。

~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		for (int j = 'a'; j <= 'z'; j++) {
			int check = 0;
			for (int k = 0; k < s.size(); k++) {
				if (j == s[i + k]) {
					check++;
					//同じアルファベットをカウントする
				}
				if (k >= 1 && check >= (k + 1) / 2 + 1) {
                    //文字列が2文字以上 かつ
                    //同じアルファベットが 過半数を占めているなら
					cout << i + 1 << " " << i + k + 1 << endl;
					return 0;
				}
			}
		}
	}
	cout << -1 << " " << -1 << endl;
	//アンバランスな部分がなかった場合
	return 0;
}
~~~

#### 正答例
先程のコードだと、sの長さが長い場合に対応しきれません。
なので、アンバランスな部分が含まれる文字列の法則を考えます。

n文字の部分がアンバランスになるには、（Xはすべて同じものであるとすると）
2文字なら XX
3文字なら XXX / XX-  / X-X  / -XX
4文字なら XXXX / XXX- / XX-X / X-XX / -XXX
5文字なら XXXXX / -XXXX / X-XXX / XX-XX / XXX-X / XXXX- / --XXX / X--XX / 
XX--X / XXX-- / -X-XX / -XX-X / -XXX- / X-X-X / X-XX- / XX-X-
という様になる必要があります。

これらのことから アンバランスな文字列は必ず XX か X-X を含む といえます。
そもそも、__XX, X-X がアンバランスな文字列__ なので、それを探して出力すればよいです。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == s[i + 1]) { // XX の判定
			cout << i + 1 << " " << i + 2 << endl;
			return 0;
		}
		if (s[i] == s[i + 2]) { // X-X の判定
			cout << i + 1 << " " << i + 3 << endl;
			return 0;
		}
	}
	cout << -1 << " " << -1 << endl;
	
	return 0;
}
~~~