解いた問題を振り返ります。

A.Frog Jumping

問題概要

Problem - A - Codeforces

以下の操作を k 回実施したときの値を求めよ。

それまで実施した回数の操作が偶数回の場合現在の値 x に a を足す
それまで実施した回数の操作が奇数回の場合現在の値 x に -b を足す

制約

$1 \le t \le 1000$
$1 \le a,b,k \le 10^{9}$

考え方

与えられた操作をシミュレーションすればよい。

Submission #45806387 - Codeforces

B.Disturbed People

問題概要

Problem - B - Codeforces

$n$ つの要素を持つ数列 $\{a_n\}$ が与えられる。 $1 \lt i \lt n$ の $a_i = 1$ なる $i$ について $a_{i-1} = 1$ かつ $a_{i+1} = 1$ である場合は $i$ は良くないとされる。いくつかの $a_i$ を $0$ にすることで良くない数をなくすとき、 $0$ にする必要がある $i$ の最小の数を求めよ。

制約

$3 \le n \le 100$
$a_i \in \{0, 1\}$

考え方

$a_i = 0,a_{i-1} = 1,a_{i+1} = 1$ なる $i$ が存在する場合は $a_{i+1}$ を $0$ にすることで良くない数をなくすことができる。これは数列を前から見ていき、貪欲に上記の方法を適応すれば変更する最小の数を求めることができる。

Submission #45809657 - Codeforces

C.Disturbed People

問題概要

Problem - C - Codeforces

数列のある要素 $a_i$ が $i$ 以外の他の要素の和と一致する時、数列は良い数列という。 $n$ つの要素を持つ数列 $\{a_n\}$ が与えられる。数列のある $1$ つの要素を除いたときに残りの数列が良い数列になる数列の index をすべて求めよ。

制約

$2 \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^6$

考え方

数列がよい数列になるときはどのような数列であるか考える。するとそのような数列は、数列の最大値を max、数列の要素の和を sum とすると max = sum - max となっている。よって与えられた数列の和と最大値、 $2$ 番目の最大値を予め求めておき、 $1 \le i \le n$ なる $a_i$ を除いたときに良い数列になっているか確かめれば良い。

Submission #45815882 - Codeforces

D.Cutting Out

問題概要

Problem - D - Codeforces

$s$ つの要素を持つ数列 $\{a_s\}$ が与えられる。 $\{a_s\}$ の要素をいくつか選択して長さ $k$ の数列 $\{b_k\}$ を作る。以下の操作を最大にするような数列 $\{b_k\}$ を求めよ。

操作 $b_k$ に含まれる各要素を $\{a_n\}$ から $1$ つ除く。

制約

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le a_i \le 2 \cdot 10^5$

考え方

まず最大の操作の回数を決めたい。これは二分探索で求めることができる。つまり操作の回数を $x$ 回としたとき、数列 $\{a_n\}$ に含まれる $a_i$ の出現回数が $cnt_i$ 回とすると少なくとも $cnt_i / x$ 個以上は存在しないといけない。 $1 \le i \le n$ なるすべての $i$ について、 $\sum cnt_i / x \geq k$ であるときはより回数を大きくでき、そうでない場合はより小さい $x$ が解の候補になる。このようにして最大回数 $x$ 回が求まったとする。そのとき $a_i$ は $cnt_i / x$ 個 $\{b_k\}$ に含めることができるので、あとはそのうち $k$ 個を出力すれば良い。

Submission #45879914 - Codeforces

E.Thematic Contests

問題概要

Problem - E - Codeforces

制約

$1 \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$

考え方

数列の要素の出現回数を予め求めておく。降順でソートしておき、前から順番に貪欲に求めることができる。 $i$ 番目について考える時、 $a_{i-1}/2$ と $a_i$ の最小値をとると、これらの和は初項 $min(a_{i-1}/2, a_i)$ 、公比 $2$ 、項数 $i$ の等比数列の和であるから $min(a_{i-1}/2, a_i) \times (2^{i}-1)$ である。これを $0 \le i \le n-1$ について求めれば良い。