Codeforces Round #521 div3 - seriruの技術屋ブログ

久しぶりにちゃんとアウトプットします．
Codeforces Round #521 div3 に参加しました.
しっかり理解できたAからDまで解説します.

A. Frog Jumping

問題概要

奇数回目のジャンプで $a$ , 偶数回目のジャンプで $b$ 移動するカエルがいる.
カエルが $k$ 回ジャンプしたときの, カエルの位置を求めよ

考察

カエルが $2n$ 回ジャンプすると, $(a-b)$ だけ移動するので, $k$ が偶数のときは, $(k \div 2) \times (a-b)$ , $k$ が奇数のときは, $(k \div 2) \times (a-b) + a$ を出力すれば良いです.

提出コード: Submission #45807781 - Codeforces

B. Disturbed People

問題概要

$n$ 軒の隣り合った家がある.
電気のついた家を $1$ , ついていない家を $0$ としたとき, 電気がついていない家が電気のついている家に挟まれてしまうことをなくしたい. このためには最低何軒の家の電気を消せば良いか.

考察

受け取った配列を左から見て, $i$ が $0$ で $i-1$ と $i+1$ が $1$ のとき, $i+1$ を $0$ に変更すれば最小で条件を満たす状態が作れます.

提出コード:

Submission #45812416 - Codeforces

C. Good Array

問題概要

数列の一番大きい要素以外をすべて足した結果が1番大きい要素になるとき, その数列を array good と呼ぶことにする.
数列の要素を順番に1つずつ消していったとき, array good になるのはどの要素を消したときかすべて求めよ.

考察

最初に数列が array good かどうか判別する方法を考えます.
最大の要素以外の和は, 数列の要素を全て足した和に最大の要素を引くことで求まります.
したがって, array good な数列は, 「数列全体の和から最大の要素を引いた結果が, 引いた要素と一致する数列」ということになります.

問題では各要素を取り除くので, 上記の条件に加えて, 数列の和から取り除いた要素を引いた上で array good かを調べれば良いです.
ただし取り除く要素が数列の最大値だった場合は, 数列の総和がその次に大きい要素と一致するかを検査する必要があることを忘れてはいけません.

提出コード:

Submission #45819016 - Codeforces

D. Cutting Out

問題概要

要素数 $n$ の数列 $s$ を切り取って, 要素数 $k$ の数列 $t$ を作る.
内容が同じ数列 $t$ を数列 $s$ から最大何個作ることができるか.

考察

例えば, s = [1, 2, 3, 4, 1, 2, 3] という数列 $s$ があるとします．
ここから要素数3の数列 $t$ を切り出すとします.
このとき 1, 2, 3がそれぞれ2つずつあるので, t = [1, 2, 3] という数列 $t$ が2つ作れます.
ここから, 数列 $t$ を $m$ 個作るとき $s_i$ が $m$ 個以上ある場合に $t$ の要素にすることができるということがわかります.
したがって $floor( |s_i| / m )$ 個だけ数列 $t$ に詰めることができます.

次に何個作れるかを考えます.
$n$ と $k$ の最大値は $2 \times 10^{5}$ なので, 作る $t$ の個数を線形時間で探索すると,
$n = 2 \times 10^{5}$ , $k = 2 \times 10^{5}$ とかやられるだけで余裕のTLEをくらいます.

しかし, 数列に詰める作業は要素を1つ1つチェックしていかないといけないためこれ以上短縮できません.
よって線形時間の探索を改善するために, 2分探索という手法を用いて個数の最大値を探すことにします.
2分探索は計算量が $\log n$ なので, 合計で $n \log n$ で個数が見つかります.