ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

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 回行う。

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

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

制約

  •  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番目の店から順番に訪れる。
  2. 訪れた店で、キャンディを1個買うお金があれば1個買う。その後、次の店に移動する。( n 番目の次は1番目に移動する)
  3. どの店でもキャンディを買えなくなったら終了する。

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

※お金の単位は勝手に円にしました。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番目の店に戻ってきます。

その後、次の周回でキャンディを買おうとすると、どこかの店でキャンディを買えなくなります。所持金が増えることはないので、その店では今後1つもキャンディを買えず、通過するだけになります。そのため、この店を消してしまうことを考えます。

店を1つ消すと、1周あたりのキャンディの価格合計が減り、キャンディの個数も減ります。その状態で改めて「全ての店でキャンディを購入する周回を何周できるか?」を考えることができます。これを全てのお店が消えるまで繰り返すことで、答えを求めることができます。

この解法において必要なのは「どの店でキャンディを買えなくなるか」を判定することと、「その店を消す」ことの2つです。これはすなわち、

  • 操作途中の所持金  t について、  t > a_{1} + \cdots + a_{i} となる最小の  i を求める。
  • ある要素  a_{i} の値を0にする。

の2つの操作であり、これはBITでデータを保持し二分探索を行うことで実現できます。

BITでの二分探索は、毎回独立に合計クエリを処理していると全体計算量が  O(n\log^{2} n) になりますが、上手くやると   O(n\log n) にできます。今回の制約だと  O(n\log^{2} n) で十分間に合いました。

ACコード

C++Submission #44869480 - Codeforces

本番コード。これは   O(n\log^{2} n) です。

C++Submission #44911558 - Codeforces

  O(n\log n) も書いてみました。