Educational Codeforces Round 53 参加記録＆解説（A～D）

Dashboard - Educational Codeforces Round 53 (Rated for Div. 2) - Codeforces

4完で256位。キリ番です（？）

Div2オンリーならもっと上を目指したいところ…

f:id:betrue12:20181026194348p:plain

A. Diverse Substring

Problem - A - Codeforces

問題概要

長さ $n$ の英小文字列 $s$ が与えられる。 $s$ の連続部分文字列 $s^{\prime}$ であって、以下の条件を満たすものを1つ求めよ。あるいはそれが存在しないことを判定せよ。

$s^{\prime}$ に含まれるどのアルファベットも、それが $s^{\prime}$ に含まれる個数は $\frac{|s^{\prime}|}{2}$ を超えない。

制約

$1 \le n \le 1000$
$s$ は英小文字からなる

解法

$\frac{|s^{\prime}|}{2}$ を「超えない」ということは、ちょうど半分はOKということです。なので、隣接する2文字が異なる箇所が $s$ に存在すれば、その2文字は答えになります。

もし隣接する2文字が異なる箇所がない場合、全ての文字が同じだということなので、その場合答えは存在しません。

ACコード

（C++）Submission #44846895 - Codeforces

B. Vasya and Books

Problem - B - Codeforces

問題概要

$n$ 冊の本が積み上げられている。上にあるものから順に、相異なる $a_{1}, ..., a_{n}$ の番号が付いている。

以下の操作を $n$ 回行う。

取り出したい本の番号が与えられる。この番号は操作ごとに相異なる。
- その本が積み上げられた本の中に存在する場合、その本とその本より上にある本を全て取り出す。
- その本がもう取り出し済みである場合、何もしない。

各操作において取り出される本の数を求めよ。

制約

$1 \le 2\times 10^{5}$
$1 \le a_{i} \le n$ であり、これらは相異なる
$1 \le b_{i} \le n$ であり、これらは相異なる

解法

$a_{i}$ は「上から $i$ 番目の本の番号はいくつか」という情報ですが、これを「番号 $j$ の本は上から何番目にあるか」という情報に変換しておきます。

各操作を処理する際には、今まで上から何冊の本を取り出したかを記憶しておきます。本の番号 $b_{i}$ からその本の位置が分かれば、追加で何冊本を取り出さなければいけないかが求められます。

ACコード

（C++）Submission #44851092 - Codeforces

C. Vasya and Robot

Problem - C - Codeforces

問題概要

座標平面にロボットがいる。初期位置は $(0, 0)$ 、目的地は $(x, y)$ である。

ロボットの動く方向（UDLR）を示す $n$ 文字の文字列 $s$ が与えられる。この文字列に以下のような変更をして、 $n$ 回の動作完了後にちょうどロボットが目的地にいるようにしたい。

$s$ の0文字以上の連続部分文字列を選択する。その中の文字それぞれを UDLR のうち好きなものに変更する（変更しない文字があってもよい）。

選択する連続部分文字列の長さを最小にしたい。その長さを求めよ。（どうやっても目的地にたどり着けない場合はそれを判定せよ）

制約

$1 \le n \le 2\times 10^{5}$
$s$ の各文字は UDLR のいずれかである
$-10^{9} \le x, y \le 10^{9}$

解法

まず、目的地に到達不可能である条件を考えます。 $d = |x| + |y|$ として、

$d > n$ である（届かない）
$d$ と $n$ の偶奇が異なる（ぴったり止まれない）

のどちらかを満たす時、到達不可能です。以降、到達可能である場合を考えます。

「連続部分文字列を選んでその中を変更する」ということは、裏返すと「左から○文字と、右から○文字は変更しない」ということです。どちらかの「変更しない文字数」を固定してみます。

「左から $i$ 文字目までを変更しないと決めた時、 $i+1$ 文字目から何文字目までを変更すれば目的地に到達可能か？」という問題を考え、その最小値を $j$ とします。そうすると $i$ が増加するにつれて $j$ も（広義）単調増加するため、しゃくとり法を使うことができます。

可能/不可能の判定においては、「変更しないと決めた文字だけでどこまで移動するか」を計算して、その到達点から目的地までの距離を計算します。自由に変更できる文字数がその距離以上であれば、（偶奇の判定は済ませているので）目的地に到達可能です。

しゃくとり法を行う上で必要な「区間に含める」「区間から除く」操作も、「変更しないと決めた文字でどれだけ移動するか」を1文字分足し引きすればよいので可能です。

ACコード

（C++）Codeforces

D. Berland Fair

Problem - D - Codeforces

問題概要

$n$ 軒の店が円形に並んでいて、 $i$ 番目の店はキャンディを1個 $a_{i}$ 円で売っている。

ポリカープは最初に $T$ 円持っており、以下のようにキャンディを買う。

1番目の店から順番に訪れる。
訪れた店で、キャンディを1個買うお金があれば1個買う。その後、次の店に移動する。（ $n$ 番目の次は1番目に移動する）
どの店でもキャンディを買えなくなったら終了する。

ポリカープが買うキャンディの個数を求めよ。

※お金の単位は勝手に円にしました。burlesってどこのお金の単位なんでしょうね…？

制約

$1 \le n \le 2\times 10^{5}$
$1 \le T \le 10^{18}$
$1 \le a_{i} \le 10^{9}$

解法

この問題はいろいろ解法があるみたいですが…私が解いたときのものを書きます。ちょっと面倒ですが、計算量の見積もりは楽です。

まず最初の状態において「全ての店でキャンディを購入する周回を何周できるか？」を考えます。全ての店のキャンディの価格合計を $A$ とします。 $T \ge A$ であるとき、 $k = \lfloor\frac{T}{A}\rfloor$ として全ての店のキャンディを $k$ 個買うことができます。所持金は $kA$ 円減り、キャンディを $kn$ 個入手し、1番目の店に戻ってきます。