ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 54 参加記録&解説(A~F)

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

今回はなんと17位!…なんですが、本番中のD問題のジャッジに致命的なミスがあって正常なコンテストではなかったため、素直に喜べない感じです…

f:id:betrue12:20181113205852p:plain

6問振り返ります。

A. Minimizing the String

Problem - A - Codeforces

問題概要

英小文字  n 文字からなる文字列  s が与えられる。この文字列から最大1文字を取り除いてできる文字列のうち、辞書順最小のものを求めよ。

制約

  •  2 \le n \le 2\times 10^{5}
  •  s は英小文字からなる

解法

文字列の  i 文字目よりも  i+1 文字目のほうが辞書順で小さいとき、 i 文字目を取り除くことで元の文字列よりも辞書順で小さい文字列を得ることができます。

辞書順で小さくするためにはできるだけ前のほうの文字を改善したほうがよいため、前から文字列を順番に見ていって、最初に  i 文字目よりも  i+1 文字目のほうが辞書順で小さくなるところで  i 文字目を取り除くのが最適です。ただし、s = aaas = abcde など最後までそのような  i がない場合は最後の文字を取り除きます。

ACコード

Codeforces

B. Divisor Subtraction

Problem - B - Codeforces

問題概要

正整数  n が与えられる。  n = 0 になるまで以下の操作を繰り返す時、その操作回数を求めよ。

  •  n から、「その時点での」  n の最小の素因数を引く。

制約

 2 \le n \le 10^{10}

解法

もし  n が偶数の場合、最小の素因数は2です。偶数  n から2を引いてもやっぱり偶数なのでまた2を引き…を最後まで繰り返すので、操作回数は  \frac{n}{2} です。

もし  n が奇数の場合、最小の素因数を  p とするとこれは必ず奇数です。そのため1回目の操作で値は  n - p となり、これは奇数同士の差なので偶数です。あとは2を引き続けるため、合計の操作回数は  1 + \frac{n-p}{2} となります。

ACコード

Submission #45598676 - Codeforces

C. Meme Problem

Problem - C - Codeforces

問題概要

以下の問題を  t 回解け。

  • 非負整数  d が与えられる。非負の実数  a, b であって  a+b = ab = d であるものが存在するか判定し、もし存在すればその値を求めよ。

制約

  •  1 \le t \le 10^{3}
  •  1 \le d \le 10^{3}

解法

連立方程式を解く常套手段として、片方の変数  b を消去します。 b = d-a ab = d に代入して整理すると  a^{2} - ad + d = 0 となり、これは  a についての2次方程式なので解の公式を用いると  a = \frac{d \pm \sqrt{d^{2} - 4d}}{2} となります。

 a = \frac{d + \sqrt{d^{2} - 4d}}{2}, b = \frac{d - \sqrt{d^{2} - 4d}}{2} のとき実際に計算すると確かに  a + b = ab = d になっているため、この2つが非負の実数であれば答えになります。もちろん逆でもよいです。

まず実数である条件は  d^{2} - 4d \ge 0 で、これが満たされない場合は条件を満たす  a, b が存在しません。またこの条件が満たされる時、  d \ge \sqrt{d^{2} - 4d} \ge 0 が成り立つことから  a, b はともに非負となるため、それぞれ計算して出力すればよいです。

ACコード

Codeforces

D. Edge Deletion

Problem - D - Codeforces

問題概要

 n 頂点  m 辺の重み付き単純連結無向グラフと、整数  k が与えられる。辺  i の重み(長さ)は  w_{i} である。このグラフにおける頂点1から頂点  i までの最短路の長さを  d_{i} とする。

このグラフから  k 本以下の辺を残す方法の中で、「残した辺だけを使った頂点1から頂点  i までの最短路を求めた際に、その長さが変わらず  d_{i} となるような頂点  i の個数」が最大となるような残し方を1つ求めよ。

制約

  •  2 \le n \le 3 \times 10^{5}
  •  n-1 \le m \le 3 \times 10^{5}
  •  0 \le k \le m
  •  1 \le w_{i} \le 10^{9}
  • グラフは重み付き単純連結無向グラフ

解法

頂点1から各頂点への最短距離はダイクストラ法で求めることができます。このとき、一緒に「各頂点への最短路に使う辺」も調べることができます。全ての頂点に対する最短路に使う辺を集めると、これは「最短経路木」と呼ばれる木になります。

※1つの頂点への最短路として長さが同じ複数の経路がある場合は、ちゃんと木になるよう経路を適切に選ぶ必要がありますが、よくあるダイクストラ法の実装のように「新しい経路の長さが、それまでに見つかった最も短い経路より真に短い場合だけ経路を更新する」という実装をしておけば大丈夫です。

辺を全て取り除いた状態から、1本ずつ辺を足していくことを考えます。このとき頂点1からの連結性を保ったまま、先ほどの最短経路木に含まれる辺だけを足していくと、新しく連結になった頂点へは頂点1から最短路を辿って到達することができます。このようにして辺を  k 本まで(または、全域木となる  n-1 本まで)足していけばそれが答えとなります。

ACコード

Submission #45615172 - Codeforces

ダイクストラ法において最短路の復元を行う場合、始点以外の頂点それぞれについて「最短路における、1つ前の頂点」を記録しておくのが常套手段です。ただし今回は辺の番号のほうが後々使いやすいため、代わりに1つ前の頂点からの辺番号を記録しています。

E. Vasya and a Tree

Problem - E - Codeforces

問題概要

頂点1を根とする  n 頂点の根付き木が与えられる。各頂点には値が書かれていて、初期値は全て0である。

頂点  x k -subtreeを、頂点  x の子孫(自身を含む)であり  x との距離が  k 以下である頂点の集合と定義する。以下のクエリが  m 個与えられる。

  • 整数  v_{i}, d_{i}, x_{i} が与えられる。頂点  v_{i} d_{i} -subtreeに含まれる全ての頂点の値に  x_{i} を加算する。

クエリを全て処理した後の、各頂点に書かれている値を求めよ。

制約

  •  1 \le n \le 3\times 10^{5}
  • 与えられるクラフは木
  •  1 \le m \le 3 \times 10^{5}
  • 各クエリについて、
    •  1 \le v_{i} \le n
    •  0 \le d_{i} \le 10^{9}
    •  1 \le x_{i} \le 10^{9}

解法

各クエリを独立に処理し、影響を受ける全部の頂点にいちいち値を足していては間に合いません。効率的な計算方法を考えます。

頂点  v_{i} の根からの深さを  D_{i} とします。するとクエリ  i で値が足されるのは、 v_{i} の子孫であって深さが閉区間  \lbrack D_{i}, D_{i}+d_{i}\rbrack に含まれる頂点であると表現することができます。範囲について値を足すクエリを大量に処理する方法として、「いもす法」のようなことができないか考えてみます。

普通のいもす法と比べるとかなり変則的ですが、以下のような方法を考えます。このようにすると、根から頂点をDFSしつつ、足される値の合計を差分更新することができます。

スライド最終ページにも書きましたが、いもす法を用いるメリットは「範囲に対する多数のクエリをまとめて処理できる」ことです。最初にクエリを全て読み込んで  v_{i} ごとに振り分けておけば、スライドで示したようなDFSで同時並行的にクエリを処理しながら全頂点の値を求めることができます。

ACコード

Submission #45682359 - Codeforces

F. Summer Practice Report

Problem - F - Codeforces

問題概要

 n ページのレポートがあり、 i ページ目には  x_{i} 個の表と  y_{i} 個の数式を好きな順序で一列に並べて書く。このとき、ページをまたいで連続するものも含めて、表だけ・または数式だけが連続して  k+1 個以上続いてはいけない。そのような並べ方は可能かどうか判定せよ。

制約

  •  1 \le n \le 3\times 10^{5}
  •  1 \le k \le 10^{6}
  •  1 \le x_{i} \le 10^{6}
  •  1 \le y_{i} \le 10^{6}

解法

表だけ・または数式だけが連続して  k+1 個以上続かないような並べ方を、正当な並べ方と呼ぶことにします。

ページの境目の扱いがやっかいなので、ここを上手く扱うことができないか考えます。ページの最後には表か数式のどちらかが書かれていますが、同じものが連続することを避けるためには「ページの最後に書かれている表/数式が、そのページの最後でいくつ連続で続いているか」の値をなるべく小さくしたいです。もちろん、1個であれば最も理想的です。

そこで、各ページ  i について

  •  i ページ目までの並べ方が正当であり、  i ページ目の最後が表であるとき、その連続個数を最小でいくつにできるか?
  •  i ページ目までの並べ方が正当であり、  i ページ目の最後が数式であるとき、その連続個数を最小でいくつにできるか?

をそれぞれ計算します。これをそれぞれ  X_{i}, Y_{i} とおくと、それらの値を使って次のページの値  X_{i+1}, Y_{i+1} が計算できます。これを最後のページまで続けて、途中で  X_{i} \gt k かつ  Y_{i} \gt k となってしまうページが出てしまったら答えは「不可能」ですし、最後のページまでそうならなければ「可能」です。

ということで遷移を考えます。(注目するページを  i にしたいので、1つ添字をずらして  X_{i-1}, Y_{i-1} から  X_{i}, Y_{i} への遷移を考えることにします。)

以降、表が連続でいくつか並んでいる塊を X 、数式の塊を Y と表記します。 i ページ目の表と数式の並べ方として、以下の4パターンを考えることができます。

  • XYXY......XY
  • XYXY......XYX
  • YXYX......YX
  • YXYX......YXY

すなわち、最初が X/Y どちらか、最後が X/Y どちらか、の4パターンです。

ここで、例えば最初が X である2パターンを考えます。最初の X の中にある表は、最大でいくつまで並べられるでしょうか?ページをまたいで表が  k+1 個以上連続してはいけないので、この値は  X_{i-1}, Y_{i-1} に依存しています。

  •  Y_{i-1} \le k であるとき、前ページの最後が Y である並べ方が可能であるため、それを採用すれば最初の X k 個並べられる。
  •  Y_{i-1} \gt k であるとき、前ページの最後を Y にはできない。そのため、
    •  X_{i-1} \lt k であるとき、最初の X k - X_{i-1} 個並べられる。
    •  X_{i-1} \ge k であるとき、最初に X を置くことはできない。

このようにして、最初の X にいくつまで表を並べられるかを求めることができます。

それでは具体的に  X_{i}, Y_{i} を求めていきます。4パターンのうち XYXY....XY を使って求め方を説明します。残りのパターンも同様に考えることができます。

連続する同じ要素を減らしたいので、要素をばらけさせる、つまり X Y の塊をなるべく多くしたいです。このパターンでは XY の個数が等しいため、それぞれの塊の個数は最大で  \min(x_{i}, y_{i}) 個まで増やすことができます。この値を  m と置きます。

塊がそれぞれ  m 個のときに

  •  x_{i} 個の表を、(最初の X に置ける個数を考慮して)それぞれの塊に含まれる要素数 k を超えないように  m 個の X に分配できるか?
  •  y_{i} 個の数式を、それぞれの塊に含まれる要素数 k を超えないように  m 個の Y に分配できるか?またそのとき、一番右の Y に含まれる数式は最小でいくつにできるか?

を計算します。実際に並べてみたものが以下の図です。

f:id:betrue12:20181114214859p:plain

具体的には、先ほど求めた「最初の X に最大でいくつまで表を並べられるか」を  a として

  •  a + (m-1)k \ge x_{i} のとき、表を X に正当に分配できる。
  • 一番右の Y に含まれる数式の最小個数は  \max(1, y_{i} - (m-1)k) であり、その値が  k 以下であれば数式を Y に正当に分配できる。

という結果になります。

このようにパターンを4つ試して、

  • XYXY......XYYXYX......YXY のうち、「正当な並べ方」を実現できて、かつ一番右の Y に含まれる数式の個数が少ない方を  Y_{i} とする
  • XYXY......XYXYXYX......YX のうち、「正当な並べ方」を実現できて、かつ一番右の X に含まれる表の個数が少ない方を  X_{i} とする

ことで遷移が求められます。これをバグらせずに全パターン実装するのはなかなか神経を使いますが、結果的には  O(n) で解くことができます。

ACコード

Submission #45627726 - Codeforces

私の実装の癖もあって、上の説明とは変数名がかなりずれています…すみません。適宜読み替えてください。