AtCoder Beginner Contest 124(ABC124)全完

A - Buttons

問題文

$2$ 個のボタンがあり、大きさはそれぞれ $A, B$ です。

大きさ $X$ のボタンを押すと、 $X$ 枚のコインを獲得し、そのボタンの大きさが $1$ 小さくなります。

あなたは、いずれかのボタンを押すことを $2$ 回行います。同じボタンを $2$ 回押しても構いません。

最大で何枚のコインを獲得できるでしょうか。

制約

入力は全て整数である。
$1 \leq A, B, C \leq 100$

考察

この問題は「Aを二回押す」「Bを二回押す」「AとBを一回ずつ押す」の3種類しか数字が出てこないので、この中の最大値を出力してあげれは良さそうです。

実装例

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18,MOD=1e9+7;
int main(){
	int a,b,c;
	cin>>a>>b;
	c=max(a+a-1,a+b);
	c=max(c,b+b-1);
	cout<<c<<endl;

}

B - Great Ocean View

問題文

東西に $N$ 個の山が連なっており、西の果てには広大な海が広がっています。

各山頂には旅館があり、あなたは海を眺められる旅館を選ぶことにしました。

西から $i$ 番目の山の高さは $H_{i}$ です。

西から $1$ 番目の山頂にある旅館からは必ず海を眺めることができます。

西から $i$ $(i = 2, 3, . . ., N)$ 番目の山頂にある旅館については、 $H_{1} \leq H_{i}$ , $H_{2} \leq H_{i}$ , $. . .$ , かつ $H_{i - 1} \leq H_{i}$ のとき、その旅館から海を眺めることができます。

これら $N$ 個の旅館のうち、海を眺められる旅館はいくつあるでしょうか。

制約

入力は全て整数である。
$1 \leq N \leq 20$
$1 \leq H_{i} \leq 100$

考察

自身の数字がそれ以前の数字全て以上であれば、「合計++;」してあげればよさそう。

二重ループでクルクルさせてあげましょう。

実装例

atcoder.jp

C - Coloring Colorfully

問題文

左右一列に $N$ 枚のタイルが並んでおり、各タイルの初めの色は長さ $N$ の文字列 $S$ で表されます。

左から $i$ 番目のタイルは、 $S$ の $i$ 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。

あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う $2$ 枚のタイルも異なる色で塗られているようにしたいです。

最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

制約

$1 \leq | S | \leq 10^{5}$
$S_{i}$ は 0 または 1 である。

考察

結局最終型は、「0101010101.....」か、「10101010101....」のどちらかになるのは自明なので、上の２つの文字列を予め入力された文字列Sと同じ長さで生成してあげる。

その後2つの文字列をそれぞれ、Sと何個違う箇所があるかをカウントしてあげてその違いの最小値を出力してあげればよさそう。

実装例

atcoder.jp

D - Handstand

問題文

$N$ 人の人が左右一列に並んでいます。

0, 1 からなる長さ $N$ の文字列 $S$ と正整数 $K$ が与えられます。

左から $i$ 番目の人は、 $S$ の $i$ 文字目が 0 のとき直立し、1 のとき逆立ちしています。

あなたは $K$ 回まで以下の指示を行います。一度も行わなくても構いません。

指示: $1 \leq l \leq r \leq N$ を満たす整数 $l, r$ を選ぶ。左から $l, l + 1, . . ., r$ 番目の人の状態を反転する。すなわち、 $i = l, l + 1, . . ., r$ について、左から $i$ 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

$K$ 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

制約

$N$ は $1 \leq N \leq 10^{5}$ を満たす整数である。
$K$ は $1 \leq K \leq 10^{5}$ を満たす整数である。
文字列 $S$ の長さは $N$ である。
文字列 $S$ の各文字は 0 または 1 である。

考察

最初区間が出てきたので「累積和か？？」と思ったけど、実装できるイメージが湧かなかったのでスルー。手元で実験していくと、先頭の番号によって以下のように場合分けできることが分かった。

HOGE1

下の画像は先頭が[0]のときの実験。(*上の画像とは0,1の上下が逆転しています)

HOGE2

ここから、([0]の塊の個数-k+1)回ループさせて、各回の値の最大値を出力させてあげれば良さそう！！！！！！と分かる。

N<=100000なのでこの実装ならTLEにならなそう。

実装

入力
0,1の連続した個数を保管する配列を用意。
がんばって上の画像の配列みたくなるように実装する。(while文で回してあげればできそう)
先頭の文字によって場合分け(これをすることで、5(次のセクション)の「先頭||最後)の[0]の塊を含む処理」の実装を楽にすることができます)
(先頭||最後)の[0]の塊を含む処理のときには、前後どちらかの[1]の塊を含まないので、それを踏まえて各回の連続する[1]の個数を求める部分を実装
出力

大まかに言うと、このような流れになります。(わかりづらくてすみません... )

コードを見るとなんとなーーく伝わるかなと思います。(0,1の個数を数える配列を長めに宣言しておいてから全要素を0で初期化すると、先述の5のめんどくさい場合分けの部分を少し楽にできます。等訳わからんことたくさんやってるけど)

実装例

atcoder.jp

感想

ABCに出始めて約1年(プログラミングを始めたのも同時期)。ようやく全完することができました！(なお、遅解きで水色パフォだった模様)

目標の水色まであと146?かな。この調子で水色になれたらいいなーと思います。

しかし2019年になってからAtCoderのコンテスト参加者数、レベルが加速度的に増加しているので、爆死したときが怖いですね。(今回もDが1000人以上に通されてるし)

マジで取り返しがつかなくなる前に水色になれるように頑張ります。

というか、自分の考え方の説明って難しいですね...　この記事を見て「は？」ってなった方々ほんとにすみません。

こっちも精進していけたらなーと思います。

ご意見や間違い、意味不明なところ(たくさんあるけど)等ございましたら、コメントやリプにお願いします。

記事を見てくださりありがとうございました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18,MOD=1e9+7;
int main(){
	int a,b,c;
	cin>>a>>b;
	c=max(a+a-1,a+b);
	c=max(c,b+b-1);
	cout<<c<<endl;

}