Codeforces Round 784 (Div. 4) A-D を解いた記録
A – Division?
問題の概要
Codeforcesではユーザーをレーティングにより4つのdivisionに分けている．レーティング $X$ のユーザーがどのdivisionに属するか答えよ．
ただし分け方は次の通りである．
- Division 1: $1900 \leq X$
- Division 2: $1600 \leq X \leq 1899$
- Division 3: $1400 \leq X \leq 1599$
- Division 4: $X \leq 1399$
制約
- $-5000 \leq X \leq 5000$
- 入力はすべて整数
解法
if文を使うだけです．
実装例
B – Triple
問題の概要
要素数 $n$ の数列 $a$ が与えられる．数列中に3個以上ある要素を1つ出力せよ．そのような要素が1つもない場合は$-1$を出力せよ．
制約
- $1 \leq n \leq 2 \times 10^{5}$
- $1 \leq a_{i} \leq n$
- 入力はすべて整数
解法
$cnt[i]$ : 数列中に $i$が登場する回数
という配列を用意し，ある値が何回登場するかを数えるようにすると実装が楽だと思います．
実装例
C – Odd/Even Increments
問題の概要
要素数 $n$ の数列 $a = \{a_{1}, a_{2}, \dots, a_{n}\}$ が与えられる．数列 $a$ に対して，次の操作をそれぞれ任意の回数だけ行う．操作回数は0回でもよい．
- 添字が奇数の要素すべてに$1$を足す．
- 添字が偶数の要素すべてに$1$を足す．
操作を終えたとき，数列を奇数の要素のみ，もしくは偶数の要素のみにできるだろうか？
制約
- $1 \leq n \leq 50$
- $1 \leq a_{i} \leq 10^{3}$
- 入力はすべて整数
解法
数列が以下の2条件の両方を満たしていれば，適切な回数の操作で数列を所望の状態にできます．
- 添字が奇数の要素について，各要素の偶奇が一致する．
- 添字が偶数の要素について，各要素の偶奇が一致する．
実装例
D – Colorful Stamp
問題の概要
長さ $n$ の文字列 $s$ が与えられる． $s$ は文字 $W, R, B$ からなる．
文字 $W$ を $n$ 個連結した文字列 $t$ に対して次の操作をそれぞれ任意の回数だけ行う．操作回数は0回でもよい．
- 隣接する2文字を $BR$ に置き換える．
- 隣接する2文字を $RB$ に置き換える．
操作を終えたとき，文字列 $t$ を文字列 $s$ と一致させられるか？
問題へのリンク
制約
- $1 \leq n \leq 10^{5}$
解法
文字列 $s$ を文字 $W$ で区切った文字列を考えます．区切ったあとの各文字列には文字 $R, B$ のみが含まれますが，区切ったあとの各文字列について1つでも $R$ のみの文字列や $B$ のみの文字列がある場合はアウトです．区切ったあとの各文字列が皆 $R, B$ の両方を含むなら，適切に操作すればそのような文字列 $s$ を作れます．