A問題
問題を言い換えると、$1$から$n$までの総和を求める問題です。
($n=5$ならば、 $1 + 2 + 3 + 4 + 5 = 15$ )
単純な繰り返しで解いてもよいし、平均を用いても良いです。
#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;
}
#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問題
0: 文字列の右端に文字 0 が挿入される。
1: 文字列の右端に文字 1 が挿入される。
B: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の1文字が削除される。
上の表に従って作成された文字列を出力します。
おそらく、出入力例を確認したほうが理解しやすいです。
例えば、01B0 という入力が与えられたとすると、
0, 01, 0, 00 と変化していき、最終的な出力は 00 となります。
str.pop_back();
で文字列strの最後の文字を削除できます。(0文字では機能しないので注意)
#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問題
$N$個の整数をすべて同じ値に揃えるのに必要なコストの和を計算します。
コストは 元の数と変化した数との差の2乗です。
例として 3から6 に変化させるとすると、$(3-6)^2=(-3)^2=9$というコストになります。
制約は$-100\leqq a_i \leqq 100$ なので、この間の整数について調べれば良く、すべての場合を試すことによって求められます。
#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問題
文字列tにおいて、その文字列の過半数の文字が同じならば、その文字列tをアンバランスであるとします。(2文字以上)
例えばnoonはアンバランスではなく、（半分は2なので、同じ文字は3つ必要）
meleeはアンバランスです。（半分は2.5なので、eが3つあり、アンバランス）
文字列sが与えられるので、アンバランスな部分があるか判定し、
アンバランスな部分があればアンバランスな位置を示し、（左右の位置を示す）
なければ、 -1 -1 と出力します。
needという文字列なら1文字目から3文字目などがアンバランスな部分。
左側の文字目を$l$,右側を$l+r$と表すと、 $l=1,r=2$となる。
部分点の獲得
$i$が左側（上でいうl）、$k$ が $文字列の長さ-1$ を表しています。(上でいうr)
checkという変数は、$i$ から $i + k$ 文字目に含まれる同じアルファベットの数を表します。checkが過半数ならというif文があり、それがtrueならば、結果を出力します。
#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;
}
正答例
先程のコードだと、$O(n^3)$なので、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 がアンバランスな文字列なので、それを探して出力すればよいです。
#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;
}