ARMERIA

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

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コード

Submission #45595242 - 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コード

Codeforces

C. Meme Problem

Problem - C - Codeforces

問題概要

以下の問題を  t 回解け。

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

制約

  •  1 \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コード

Submission #45602724 - 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

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

ABC113 参加記録&解説

AtCoder Beginner Contest 113 - AtCoder

22分台全完で21位でした。

f:id:betrue12:20181104225338p:plain

A - Discount Fare

A - Discount Fare

解法

 X + \frac{Y}{2} を計算して出力すればよいです。

ACコード

RubySubmission #3531033 - AtCoder Beginner Contest 113

B - Palace

B - Palace

解法

 N 個の地点それぞれについて  |(T - H_{i} \times 0.006) - A| を計算し、それが最も小さい地点を探せばよいです。

ACコード

ちょっとした実装テクとして、上記のコードのようにC++min_element を使うと、「 vector の中で最も小さい要素のインデックス」がスマートに取得できます。

C - ID

C - ID

解法

市を県ごとに分類し、それぞれの県ごとに誕生年でソートします。そうすると、それぞれの市がその県で何番目に誕生した市かが分かります。

…というものを素直に実装すればよいです。300点問題で数学が要らないのは、最近だと珍しいですね…

ACコード

実装テクという点では、

  • 誕生年でのソートをする際に、市のインデックスも巻き込むと後の実装がしやすくなる。そのため市を県ごとに分類する際、C++だと pair などを使って、誕生年と市のインデックスをまとめておく。
  • 指定された桁数になるように左に0を埋める方法(C/C++だと、printf のフォーマット指定子で可能

などを知っておくとよいですね。

D - Number of Amidakuji

D - Number of Amidakuji

解法

ある行までの横線の引き方は、その1つ上の行までの横線の引き方から計算できそうです。上からDPをしていくことを考えます。

 i 行目まで考えた時に、縦線1からスタートしたものが  k 番目の縦線に移動しているような横線の引き方の総数」を  dp\lbrack i \rbrack\lbrack k \rbrack とします。初期条件は  dp\lbrack 0 \rbrack\lbrack 1 \rbrack = 1 で、答えは  dp\lbrack H \rbrack\lbrack K \rbrack です。

 i 行目から  i+1 行目への遷移に必要な情報は、「1行の横線の引き方であって、  j 番目の縦線から  k 番目の縦線に移動する引き方の総数」です。これを  num\lbrack j \rbrack\lbrack k \rbrack とすると、  i 行目から  i+1 行目の遷移は

 dp\lbrack i+1 \rbrack\lbrack k \rbrack = \sum_{j} (dp\lbrack i \rbrack\lbrack j \rbrack \times num\lbrack j \rbrack\lbrack k \rbrack)

と求められます。

次は、この  num\lbrack j \rbrack\lbrack k \rbrack の求め方を考えます。1行の横線の引き方は、線を引くところが  W-1 箇所しかないため、高々  2^{W-1} 通りです。 W \le 8 であることから  2^{W-1} は十分小さいので、全部確認してしまいましょう。

f:id:betrue12:20181104234145p:plain

1行の線の引き方を全部列挙すれば、以下のように  num\lbrack j \rbrack\lbrack k \rbrack が求められます。

  1. 0から  2^{W-1} -1 までの整数をループで回す。この整数をビット列として見た時の  W-1 個のビットがそれぞれ横線の有無を表し、  k 番目のビットが1であることは「  k, k+1 本目の縦線間に横線がある」ことを示す。
  2. これが「どの2つの横棒も端点を共有しない」というルールに違反する、つまりビット列として見た時に連続した1を含む場合、スキップする。
  3. この線の引き方のとき、 j 番目の縦線からどこの縦線に移動するかを各  j ごとに計算する。これを  k_{j} とおく。
  4.  j ごとに、 num\lbrack j \rbrack\lbrack k_{j} \rbrack に1を加算する。

この  num\lbrack j \rbrack\lbrack k \rbrack を用いてDPを行えば、答えを求めることができます。

ACコード

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) も書いてみました。

ARC091 F - Strange Nim

F - Strange Nim

面白い問題だったので記録。公式解説とはちょっと違う解法。

考察・解法

実験と観察

山同士は相互に干渉しないので、それぞれの山のGrundy数を求めることが目的になる。

注目している1つの山について、残っている石の数を  X 、その山が持つパラメータ  A_{i}, K_{i} を単に  A, KGrundy数を  G(X) と記す。「もう操作できない状態」のGrundy数が0であるとして、

  •  X \lt K のとき、 G(X) = 0
  •  X \ge K のとき、 G(X) G(X - \lfloor\frac{X}{K}\rfloor) から  G(X - 1) までに登場しない最小の非負整数。

である。

これがどのような値になるか実験してみる。そうすると、

  •  \lfloor\frac{X}{K}\rfloor が変化しない範囲では、 G(X) 0 から  \lfloor\frac{X}{K}\rfloor までの値がある順序で繰り返される。例えば  X = 30, ..., 39 の範囲では、  G(X) 3, 1, 0, 2 の繰り返しになっている。
  •  X K の倍数のとき  G(X) = \frac{X}{K} となり、それまでの順序のある位置に  \frac{X}{K} が「挿入」される形で、それ以降はまた値が繰り返される。

というような性質がある。この性質を使えば、いくつかの方法でGrundy数が求められそうである。

求め方1:再帰で求める

1つ目の方法は、繰り返しの性質を用いた再帰である。 X K の倍数でないとき、以下のように考えることができる。

f:id:betrue12:20181024211331p:plain

この考え方から、 X K の倍数でないとき  G(X) = G(X - \frac{X}{K} - 1) であることが分かる。 X = A から始めて、これを  X \lt K になるか  X K の倍数になるまで再帰的に繰り返すことで、  G(X) を求めることができる。

この操作1回で、  X はおよそ  \frac{K-1}{K} 倍になる。 K が小さいとこれで十分間に合うが、 K が大きいときにはいくら指数的に減っていくとはいえスピードが遅すぎて間に合わない。

計算量はおそらく  O(\log(\frac{A}{K}) / \log(\frac{K}{K-1})) であり、 O の中身を単純計算すると  A = 10^{9}, K = 10^{5} のときにおよそ  9.2 \times 10^{5} となる。後で  N = 200 が掛かることを考えると、  K \le 10^{5} くらいが限度だろうと思われる。

※公式解法では、後述の「求め方2」は使わず、この求め方1をベースにさらに高速化の工夫をしている。

求め方2:順序への「挿入」をシミュレートする

求め方1の欠点を補うため、  K が大きい時に使えるGrundy数の求め方を考える。

先述のように、 G(X) の遷移はある順序で繰り返され、  X K の倍数になるごとに、その順序のある位置に新しい値が挿入される。これを全てシミュレートしてやることでも  G(X) を求めることができる。

やりたいのは、数列のどこかのインデックス(  k 番目)へ値を挿入すること。そして、最後にどこかのインデックスの値を取ること。これは平衡二分木を使えば、要素数 a として  O(\log a) で実現できる。

この操作は全部でおよそ  \frac{A}{K} 回行われるので、計算量は  O(\frac{A}{K} \log( \frac{A}{K})) である。これは求め方1とは逆に  K が大きいほど計算量が少なくなり、 K \ge 10^{5} くらいであれば十分高速である。

解法まとめ

  1. 山ごとにGrundy数を求める。このとき、 K の値によって2通りの求め方を使い分ける。
    1.  K が小さい場合、再帰で求める。
    2.  K が大きい場合、順列への値の挿入を平衡二分木でシミュレートして求める。
  2. 全ての山のGrundy数のXORを取り、勝敗を判定する。

ACコード

Submission #3462224 - AtCoder Regular Contest 091

求め方を切り替える閾値の設定が難しく、 10^{4} で分けた場合は TLEした。求め方1は処理がとても単純なので定数倍が軽く、求め方2では平衡二分木の処理が重いので、単純に  O の中身を計算して比較したときの閾値より高めにするのがよい。想定解法ではないので、どう調整しても通らないときは仕方がない。

さいごに

一番最後はデータ構造で「殴って」しまったけれど、Grundy数の一見不規則に見えて実は美しい規則性、計算量の落とし方の工夫、ともに面白い問題だった。

九州大学プログラミングコンテスト2018 参加記録&解説(A~F)

九州大学プログラミングコンテスト2018 - AtCoder

6完で31位でした。正答数は良い感じですが、色々バグらせました…

f:id:betrue12:20181020180500p:plain

A - QUPC

A - QUPC

解法

 ans = 4N + 2010 を計算すればよいです。

ACコード

Submission #3436129 - 九州大学プログラミングコンテスト2018

B - Tapu & Tapi

RubyB - Tapu & Tapi

解法

値が大きい方の硬貨から見ていきます。

100円玉が偶数の場合、それを普通に分ければよいです。もし奇数の場合は、余った100円玉の相手になるように、小さい硬貨から100円を借りてこなければいけません。

10円玉についても同様にします。最終的に1円玉が足りて、かつ偶数であればよいです。

ACコード

RubySubmission #3436312 - 九州大学プログラミングコンテスト2018

C - Ito Campus

C - Ito Campus

解法の流れとしては、まずイノシシまで  X 歩以内に到達可能な点を求めます。その後、うしくんさんがそれらの点を避けてゴールにたどり着く最小距離を求めます。これらはともにBFSで求めることができます。

まずイノシシについて考えます。「イノシシまで  X 歩」とはつまり「イノシシから  X 歩」であるため、イノシシをBFSの始点とします。イノシシは複数頭いるため、BFSを複数の始点から開始する必要があります。といっても、最初にキューに入れる点を複数にすればそれでOKです。

同時並行で探索が進み、あちこちが更新されていくので少し違和感があるかもしれません。イメージとしては、1つの始点から探索を広げるのではなく、「距離が0の点(始点)を設定する」→「その隣を見て、距離が1の点を確定させる」→「その隣を見て、距離が2の点を確定させる」…という全体の流れを意識するといいと思います。

イノシシの処理ができたら、イノシシまで  X 歩以内の点を通行不可扱いにして、うしくんさんのBFSをやります。

ACコード

C++Submission #3437495 - 九州大学プログラミングコンテスト2018

このコードでは、イノシシまでの最短距離を全て計算してしまい、うしくんさんの移動の際にその距離を参照しています。実際に必要なのは「 X 歩以内かどうか」の情報だけなので、これを true/false のフラグで管理する、 X 歩以内の場所を # で埋める、などの実装も可能です。

D - Novelist

D - Novelist

解法

「時刻  t に王都にいる(依頼を開始できる)状態であるとき、それまでに完了した依頼の最大数」を  dp\lbrack t \rbrack とします。初期状態は  dp\lbrack 0 \rbrack = 0 です。

時刻  t に王都にいて、それ以降に王都で受けられる依頼を受けることを考えます。そのときの動きとして、次のようなものが考えられます。

f:id:betrue12:20181020190939p:plain

  • 依頼をこなしたあと、戻りの依頼が存在しない場合、合計で  dp\lbrack t \rbrack + 1 個の依頼をこなして依頼終了となる。
  • 依頼を2つこなして王都に戻ってこられる場合、帰りの依頼の終了時刻を  t^{\prime} として、 dp\lbrack t^{\prime} + 1 \rbrack \leftarrow  \max(dp\lbrack t^{\prime} + 1 \rbrack, dp\lbrack t \rbrack + 2) とすることができる。

また、もちろん「時刻  t に依頼を受けない」という選択もできます。その場合は次の時刻に持ち越されるため、 dp\lbrack t + 1 \rbrack \leftarrow  \max(dp\lbrack t + 1 \rbrack, dp\lbrack t \rbrack) となります。

このような「配るDP」をすることで解を求めることができますが…時刻は  10^{9} オーダーで普通に扱うことはできないので、座標圧縮をします。王都を基準にしたDPを考えているため、王都から受けられる依頼の開始時刻、つまり  A_{i} を座標点として採用します。

DPの遷移においては

  • 王都から依頼を受けて都市  X に到着後、都市  X で受けられる依頼のうち最も早いものはどれか
  • その依頼を受けて王都に戻ってきたあと、次に王都で依頼を受けられる最も早い時刻はいつか

が必要になりますが、これらはともに二分探索を使って求めることができます。

最終的な解は  dp\lbrack \infty \rbrack とは限らず、王都以外の都市で依頼を終えることもあるため、遷移の中で逐次更新をしていくとよいです。

ACコード

C++Submission #3438131 - 九州大学プログラミングコンテスト2018

終了後、区間スケジューリングとして見ると楽だという話を見てなるほどと思いました。あまりやっていることは変わりませんが、明示的な座標圧縮も必要ないですし、そちらのほうが楽かもしれません…

E - Treeone

E - Treeone

解法

 A_{i} について、「  A_{i} を含む区間で、合計が0になるものはいくつあるか」を求めます。その数が最も大きい要素の値を変更するのが最適です。変更する際に他の区間に影響を与えてしまわないか心配ですが、5000兆とかの極端な数に変更しておけば他の区間の合計を0にしてしまうことはありません。

ということで、「  A_{i} を含む区間で、合計が0になるものはいくつあるか」の求め方ですが…区間がいくつかあり、各要素について「その要素を含んでいる区間がいくつあるか」というものを求めたいので、いもす法が使えそうです。ただ、合計が0になる区間は最大で O(N^{2}) 個あり、これをバラバラに扱っていると間に合いません。

いもす法は、(インデックスのとり方にもよりますが)区間ごとに始点の位置に+1して、終点の次の位置に-1して、最後に累積和を取る方法です。そのため、各位置について「ここが始点となる区間はいくつあるか?」「ここが終点となる区間はいくつあるか?」を求めることができれば、+1/-1の計算をまとめてすることができます。

「ここが終点となる、合計が0である区間はいくつあるか?」を求めるには、左から累積和を求めていけばよいです。お馴染みの「Zero-Sum Ranges」です。

f:id:betrue12:20181020195935p:plain

「ここが始点となる、合計が0である区間はいくつあるか?」を求めるには、同じことを右からやればよいです。

これらを求め、いもす法で「その要素を含んでいる区間がいくつあるか」を復元し、その最大値を合計が0の総区間数から引いてやれば答えが求められます。

ACコード

C++Submission #3438450 - 九州大学プログラミングコンテスト2018

F - Team Making

F - Team Making

解法

 N がとても小さいので、bitDPなどの解法が使えそうです。「 N 人のうち集合  S に属する人を使ってできるグループの分け方」を  dp\lbrack S\rbrack とするDPをします。

 dp\lbrack S\rbrack を求める際に、 S に含まれている人からグループを1つ作る方法を考えます。そのグループを  T とすると、 dp\lbrack S - T\rbrack を使って遷移を計算することができます。

ただしグループの取り方全てを考えてしまうと、同じ分け方を何度も数えてしまうので、そうならないようにルールを決めます。具体的には、「 S に含まれる人のうち番号の若い人は必ず使う」というルールです。常にこのルールを守っていけば、同じ分け方を何度も数えることはありません。

 S に含まれる人のうち一番若い番号を  i とすると、作られるグループは

  •  i 1人だけのグループ( O(1) 個)
  •  i とあと1人のグループで、レート条件を満たすもの( O(N) 個)
  •  i とあと2人のグループで、レート条件を満たすもの( O(N^{2}) 個)

で、集合1つにつき  O(N^{2}) で遷移を計算できます。

全体計算量が  O(N^{2} \times 2^{N}) となり、単純計算で  18^{2} \times 2^{18} = 84934656 です。億を超えていないので、1つ1つの計算が軽ければ間に合います。

ACコード

Submission #3438778 - 九州大学プログラミングコンテスト2018

ソートしておくと少しだけ枝刈りができたり、各レートから予め  K を引いておくと平均が  K 以下かどうかの判定が楽だったり、ちょっとしたテクニックはあります。

Educational Codeforces Round 52 G. Fibonacci Suffix

Problem - G - Codeforces

面白い問題を自力で通せたので記録。

問題概要

文字列の列  F(i) を、漸化式

 F(0) = "0" , F(1) = "1" , F(i) = F(i-2) + F(i-1)

で定義する。この  + は文字列の結合を示す。

整数  n, m, k が与えられる。 F(n) の接尾辞を辞書順に並べた時、  k 番目に該当する文字列の先頭  m 文字を求めよ。(ただし、その文字列の長さが  m 未満の場合は文字列全体を出力せよ。)

制約

  •  1 \le n, m \le 200
  •  1 \le k \le 10^{18}
  •  k F(n) の長さを超えない

考察・解法

方針を考える

タイトルにもあるように漸化式がフィボナッチ数列のようになっていて、  F(i) の長さは通常の意味でのフィボナッチ数となる。 n=200 のときを計算してみると  |F(n)| \simeq 4.54\times 10^{41} となり非常に大きい数となる。

注目すべきは  m \le 200 であり、要求されているのは高々200文字なので、接尾辞のうち201文字目以降は区別する必要がない。そのため「先頭200文字が○○○になるような接尾辞はいくつあるか?」という分布のようなものを計算できれば、それを辞書順で前から加算し、累積  k 個以上になった時点での文字列が答えである。

接尾辞を効率的に数える

01 で構成される200文字の文字列は最悪  2^{200} 通りあるが、 F(i) には同じ文字列が繰り返し含まれているため、パターン数はぐっと少なくなる。

具体的には、 i を適当に決めて  A = F(i-1), B = F(i) とすると、 F(i) 以降の文字列は全て  A, B を並べたものになる。そのため以下のような方針で、接尾辞の先頭200文字の分布を求めることができる。

  1.  A = F(i-1), B = F(i) がおよそ200文字になるように  i を適当に決める。
  2. それ以降の  F(i) で、文字列の連結も含めて  A, B の組み合わせとして登場し得るパターンを列挙する。
  3. それぞれのパターンで登場する200文字以内の部分文字列と、その登場回数を計算し、全て合計する。

 A, B として固定するものとしては、  |F(11)| = 144, |F(12)| = 233 なのでこれを使う。

 F(n) 内に存在する「200文字以内の部分文字列」の登場パターンとして考慮すべきは、以下のものである。

  • 文字列の最後に存在する  B の接尾辞1~199文字
  •  B の200文字の部分文字列
  •  BA の200文字の部分文字列のうち、前の  B を199文字以下含むもの
  •  BB の200文字の部分文字列のうち、前の  B を1~199文字含むもの
  •  ABA の200文字の部分文字列のうち、最初の  A を1文字以上含むもの

漏れとダブリがないよう、そのパターンが  F(n) にいくつ登場するかの回数も含めて計算していく。各パターンの登場回数はフィボナッチ数に似た漸化式で表せるので前計算しておく。

これで、接尾辞の先頭200文字としてあり得るものについて、それが  F(n) にいくつ登場するかが数えられる。実際にやってみると登場する文字列はちょうど400種類になった(!?)。十分扱えそうな個数である。

 k 番目」を求める

分布が求められたので、実際に  k 番目を求めていく。…といっても、高々200文字の文字列が400個なので、辞書順でソートして前から見ていけば十分間に合う。

最初はTrie木を使うと速いかなと思ってそっちを使ったが、mapに順序関係を保ってもらった状態で個数をカウントし、前から見ていったほうが実行時間も短かった。

ACコード

実装上の注意点としては、

  •  A = F(11), B = F(12) として  A, B の組み合わせだけで考えた場合、  n \le 11 のときはこのやり方では答えが出ない。ただその場合は接尾辞の総数が少ないので、普通に全列挙&ソートして直接  k 番目を取ってしまえばよい。
  • 数え上げた結果がものすごく大きな数になり得るので注意。 10^{18} を超える個数は数えても無意味なので、個数を足し算するごとに「結果が  10^{18} を超えていたら  10^{18} にする」などの処理をしておけばOK。

さいごに

えでゅふぉの最終問は、こういうキッチリ考察して地道に解いていく問題が多いように思う。

公式解説も似たようなことをしてそうなんだけど、書いてあることが難しい…

Codeforces Round #516 参加記録&解説(A~C)

Dashboard - Codeforces Round #516 (Div. 1, by Moscow Team Olympiad) - Codeforces

結果は3完!とはいえ、3完速解き勢が多くてレート上昇はそこそこ。Div1は修羅の世界。

f:id:betrue12:20181016232110p:plain

A~Cを振り返ります。Div2だとC~Eに相当します。

A. Oh Those Palindromes

Problem - A - Codeforces

問題概要

長さ  n の文字列  s が与えられる。 s の文字を並び替えたもののうち、回文になるような連続部分文字列が最も多くなるものを1つ出力せよ。

制約

  •  1 \le n \le 100000
  •  s は英小文字からなる

解法

この問題にはとてもシンプルな答えがあります。ソートなどを使い、同じ文字を全て隣り合うようにまとめてしまえばそれが答えになります。例えば  sabaacb だった場合、 aaabbc は答えです。

これを示すため、まずは回文になる連続部分文字列の数の上界を考えます。「並び替えをどんなに頑張っても絶対にこの値より大きくはならない」という値です。

文字列が回文になっているとき、その文字列の最初の文字と最後の文字は必ず等しいものである必要があります。そのため回文の数は、「文字列の中から、同じ位置または異なる位置にある同じ種類の文字を2つ選ぶ方法の総数」以下になります。これは具体的には、文字種それぞれについてその個数を  k として  \frac{k(k+1)}{2} を計算し、全ての合計を取ったものです。

aaabbc のように同じ文字をまとめた文字列から、同じ位置または異なる位置にある同じ文字を2つ選びその間にある連続部分文字列を考えます。その文字列は1種類の文字しか含んでいないため、必ず回文になります。そのためこのような並べ方は先ほどの上界を実現することが分かり、これが答えとなります。

閃けば一瞬。上位陣は爆速で通していますね…

ACコード

C++Submission #44295304 - Codeforces

B. Labyrinth

Problem - B - Codeforces

問題概要

 n m 列のマスで定義されるマップがあり、いくつかのマスには障害物があり進入できない。

マス  (r, c) からスタートし、マップ内を上下左右に0回以上好きな順番で移動してどこかのマスを訪れる。このとき上下には好きな回数移動可能だが、左には  x 回以下、右には  y 回以下しか移動できない。

障害物がないマスそれぞれについて、「上記の条件で  (r, c) から到達可能か?」を考えた時、到達可能なマスはいくつあるか答えよ。

制約

  •  1 \le n, m \le 2000
  •  1 \le r \le n, 1 \le c \le m
  •  0 \le x, y \le 10^{9}

解法

制限が特殊ですが、「移動回数」をなるべく小さく保ったままマスを探索したい、ということでBFSをしたくなります。

左右の移動回数をなるべく少なくしたいというのは分かります。ただし、左右どちらを優先すべきか?というのは一概に決められません。このため、もしあるマスへの行き方の候補として「左移動は少ないけど右移動は多い」ルートと「右移動は少ないけど左移動が多い」ルートがある場合、どちらを採用すれば良いか決めかねてしまいます。

ただしこの問題の場合、「左右の合計移動回数」だけを管理し、それがなるべく少ないルートを採用すれば、それが各マスへの最適な移動経路となります。このことを確認します。

スタート地点の横軸座標は  c であり、そこから左右合わせて  s 回移動して  c^{\prime} に移動するとします。このとき左右それぞれの移動回数を  a, b とすると、

  •  b+a = s
  •  b-a = c^{\prime} - c

であり、この連立方程式によって  a, b の値が一意に定まります。具体的には

  •  a = \frac{s - c^{\prime} + c}{2}
  •  b = \frac{s + c^{\prime} - c}{2}

であり、合計移動回数  s が小さいほど  a b も小さくなるため、  s を小さくするルートが常に最適というわけです。

ということで、左右の合計移動回数  s をなるべく小さくしつつ、 x, y による制約の範囲内でマップを探索していきます。上下の移動はノーコストと考えることができるので、単純な「幅優先探索」ではなく、 s が小さい順に近隣の探索を行っていく「最良優先探索」をやるとよいです。

最良優先探索の一般的な方法は、ダイクストラ法でお馴染みの優先度付きキューを用いるものです。ただこの問題の場合は、コストを0または1とみなせることから「0-1 BFS」で解くと速いです。0-1 BFSの解説としてはhosさんのスライドや、英語でよければ こちらの記事 などがあります。

ACコード

C++Submission #44303644 - Codeforces

C. Dwarves, Hats and Extrasensory Abilities

Problem - C - Codeforces

問題概要

インタラクティブ問題)以下の処理を行い、最後に条件に合う値を出力せよ。

  1. システムから整数  N が与えられる。
  2. 以下の処理を  N 回行う。
    1. 解答者のプログラムは2次元平面上の整数座標  (x, y) を指定する。これは毎回異なる点である必要がある。
    2. システムはその点に対して、黒または白を回答する。
  3. 異なる整数座標を2つ指定する。この2点を通る直線が、以下の条件を満たす必要がある。
    1. 前項で指定した座標点のうち、黒い点と白い点がこの直線によって分離される。
    2. 前項で指定した座標点は、この直線上には存在しない。

制約

  • システムから与えられる値は  1 \le N \le 30
  • 解答者が出力する整数座標は、いずれも  0 \le x, y \le 10^{9}

解法

1つの点を指定して、その点が2つの分類のうちどちらに属するかを判定し、境界を探る。これはまさに二分探索と同じ処理であり、二分探索のように解くことができます。

使える範囲は  10^{9} \times 10^{9} と広いですが、ほとんど1直線上で十分です。ある直線、例えば  y=1 を考えます。

  1. まず、 (0, 1) のクエリを発行し、色を指定してもらう。
  2. 直線  y=1 上で、 x を二分探索するような要領で  N-1 回のクエリを発行する。すなわち初期値を  x_{lb} = 0, x_{ub} = 10^{9} として、 x_{mid} = \lfloor\frac{x_{lb}+x_{ub}}{2}\rfloor として  (x_{mid}, 1) のクエリを発行する。そこで指定された色が  (0, 1) の色と同じかどうかによって、  x_{lb} または  x_{ub} x_{mid} に置き換える。
  3. クエリを必要回数発行し終わったら、これらの境界となる直線を引く。

のようにできそうです。ここで考えるのは「この方法で毎回異なる点を指定できて、かつ分離できるような直線が引けるのか?」です。

範囲が二分割される機会が最大29回であり、 \lfloor\frac{10^{9}}{2^{29}}\rfloor = 1 であることから、クエリ発行完了後の  x_{ub} - x_{lb} は最も小さい値で1です。クエリが完了する前にこれが1になってしまうと異なる点を指定できなくなりますが、その心配はないです。

距離が1の場合、整数座標を2つ指定して分類直線を引くのが少しだけ難しそうに見えますが、以下のようにすればよいです。 y=0 上でやらなかったのは、ここで両側の点を使いたかったからです。

f:id:betrue12:20181017221832p:plain

ACコード

C++Submission #44443898 - Codeforces

本番は少し違うコードで通しました。距離が1になる場合の対応方法は、いろいろやり方があると思います。

さいごに

確かにこの3問は解きやすく、速解きが求められるのも納得です。D問題以降、AC人数がガタ落ちする感じでした。