ARMERIA

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

Codeforces Round #528 参加記録&解説(A~D)

Dashboard - Codeforces Round #528 (Div. 1, based on Technocup 2019 Elimination Round 4) - Codeforces

配点の高いDを通し、なんとDiv1で81位!これはそうそう出るものじゃないですね。レートも爆上げ。

f:id:betrue12:20181225203444p:plain

A~Dを振り返ります。Div2ではC~Fに対応します。

A. Connect Three

Problem - A - Codeforces

問題概要

2次元グリッド上の3つのマス  A, B, C の座標が与えられる。マスを選んで道を作り、これら3マスを相互に通行可能にしたい。道同士は辺で連結されている場合に通行可能であり、マス  A, B, C も道にする必要がある。

最小のマス数で道を作る時、その道の例を1つ示せ。

制約

  • 与えられるマスの座標は  1 \le x, y \le 1000

解法

色々場合分けが必要そうに見えたり、コーナーケースが怖くなるような問題ですが、私の解法を書きます。

  1. 3点の  x 座標のうち真ん中のものを1つ選び  x_{c} とする。3点の  y 座標の最小値・最大値をそれぞれ  y_{m}, y_{M} として、 x= x_{c}, y_{m} \le y \le y_{M} の点を全て道にする。
  2.  x_{c} として選んだもの以外の2点から、先ほどの線に垂直に道を作る。  x 座標が  x_{c} と一致している点については何もしない。

図で表すと以下のようになります。座標が重複している場合等も含めてこれで上手くいきます。

f:id:betrue12:20181225231315p:plain

ACコード

B. Minimum Diameter Tree

Problem - B - Codeforces

問題概要

 n 頂点の木が与えられる。この木の各辺に非負実数の重みを割り当て、重み合計が  s となるようにする。

この木におけるパスの重みを通る辺の重みの合計とし、木の直径を全てのパスの重みの最大値とする。木の直径を最小にするように重みを割り当てるとき、その直径の値を求めよ。

制約

  •  2 \le n \le 10^{5}
  •  1 \le s \le 10^{9}
  • 与えられるグラフは木

解法

結論から言ってしまうと、葉から伸びる各辺に重みを均等に割り振ってしまうのが最適となります。葉の数が  k のとき1辺の重みは  \frac{s}{k} であり、任意のパスは葉を高々2個含むので、直径は  \frac{2s}{k} となりこれが答えです。

コンテスト本番はサンプルの例から類推するか、「中途半端な辺は多くのパスに含まれるので、ここに重みを割り振るのは損になりそう」という感覚で解いてしまうかもしれません。一応証明します。

証明

異なる葉同士を繋ぐ全てのパスを考えます。木における任意のパスの重みの最大値  D は、異なる葉同士を繋ぐパスの重みの最大値と一致します。葉と葉をつないでいないパスは、適当に両端を葉まで伸ばすことでそれ以上の長さのパスが作れるからです。

異なる葉同士を繋ぐパスは葉の数を  k として  _{k}C_{2} 本あります。これらの重みの総和を  S とします。

任意の割り振りで辺に重みを割り当てたとします。ある辺  e に割り振った重みを  w_{e} とすると、 w_{e} はどれほど  S に寄与するでしょうか?

 e によって葉は2つの集合に分断されます。その一方の個数を  a 、もう一方の個数を  k-a とすると、異なる葉同士を繋ぐパスで辺  e を通るものは全部で  a(k-a) 本あるため、辺  e の重みは  S a(k-a)w_{e} 寄与します。

このとき  1 \le a \le k-1 であり、 a(k-a) - (k-1) = -(a-1)(a-(k-1)) \ge 0 であることから  a(k-a) \ge (k-1) が成り立ちます。そのため全ての辺について重みの寄与分を足すと、

  •  S \ge (k-1) \sum_{e} w_{e} = (k-1)s

となります。  _{k}C_{2} 本のパスの重み合計が  (k-1)s 以上であるため、重みの最大値  D について

  •  D \ge \frac{(k-1)s}{_{k}C_{2}} = \frac{2s}{k}

が成立します。この右辺の値は冒頭の最適解(仮定)と一致するため、冒頭の構成方法の最適性が証明できました。

ACコード

C. Vasya and Templates

Problem - C - Codeforces

問題概要

以下の問題が  t 個与えられる。

  • a から順に  k 種類のアルファベットからなる文字列  s, a, b が与えられる。 k 種類のアルファベットを置換する方法で、 s を置換した後に辞書順で  a \le s \le b となるようなものを1つ答えよ。またはそのような置換が存在しないことを判定せよ。

制約

  •  1 \le t \le 10^{6}
  •  1 \le k \le 26
  •  1 \le |s| = |a| = |b| \le 10^{6}
  • 全ての入力文字列の合計文字数は  3\times 10^{6} を超えない

解法

DFSで文字列を前から順番に見ていきつつ、置換の割り当てを決めていきましょう。イメージとしては桁DPです。

「既に割り当て済みの置換がこれこれで、  k-1 文字目までが辞書順の条件を満たしているとき、 k 文字目の割り当てを決める」という処理を考えます。このとき、「それより前のインデックスで、 a より真に大きい状態になっているか?  b より真に小さい状態になっているか?」という情報を追加で持ちます。これがちょうど桁DPの「上限値より真に小さいことが確定しているか」という情報と似ています。

DFSの探索において、 s\lbrack k \rbrack が既に割り当て済みのアルファベットだった場合は大小関係だけをチェックします。新しいアルファベットだった場合は、次のように割り当てを行います。「真に大きい/小さい」という条件を確定させたほうが有利なので、なるべくそれが成立するものを優先的に選ぶようにします。

  •  a より真に大きく、 b より真に小さいことが確定している場合、それ以降は任意に割り当てて良い。空いているものを好きに選ぶ。
  •  a より真に大きい場合、 b についての条件だけを考えれば良いので、  b\lbrack k \rbrack 以下のアルファベットで空いているものを選ぶ。特に   b\lbrack k \rbrack より真に小さいものが空いていれば優先的に選ぶ。
  •  b より真に小さい場合、 a についての条件だけを考えれば良いので、  a\lbrack k \rbrack 以上のアルファベットで空いているものを選ぶ。特に   a\lbrack k \rbrack より真に大きいものが空いていれば優先的に選ぶ。
  • どちらでもない場合、 a\lbrack k \rbrack 以上かつ  b\lbrack k \rbrack 以下のアルファベットで空いているものを選ぶ。特にその間にあるアルファベットが空いていれば優先的に選ぶ。

このようなDFSを行う時、そのステップ数はどうなるでしょうか。1度「 a より真に大きく、 b より真に小さい」という状態にたどり着ければ、その後はストレートで解にたどり着くため探索が終了します。これらの条件が確定しないままのDFSは、 a または  b に「沿った」探索しかないため、全体の分岐の中でも高々2本だけです。そのため分岐の本数は高々3本しかなく、ステップ数は文字列の長さを  n として  O(n) となります。

各ステップの計算量で入力に依存しそうなのは空いているアルファベットの探索であり、全探索しても全体  O(kn) です。これでオーダーとしては間に合いますが…とにかく入出力の数が多いので、高速な言語および入出力(C++なら scanf/printf )を使わないとひたすらTLEします。つらい。

ACコード

D. Rock-Paper-Scissors Champion

Problem - D - Codeforces

問題概要

 n 人のプレイヤーが一列に並び、じゃんけんをする。各プレイヤーが出す手は決まっている。このとき以下のルールでじゃんけんを進める。

  1. 隣り合う2人を選び、じゃんけんをさせる。あいこの場合はどちらを勝たせても良い。
  2. 負けた方を列から取り除く。
  3. これを最後の1人が残るまで繰り返す。

「じゃんけんをさせる組の選び方やあいこの勝敗も含めて好きなように操作をするとき、優勝する可能性があるのは何人か?」を求めたい。

ただしクエリが  q 個与えられ、各クエリは「  p_{j} 番目の人の手を  c_{i} に変更する」というものである(クエリの効果は累積する)。初期状態および各クエリを処理した後の全ての状態について、優勝する可能性のある人数を求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  1 \le q \le 2\times 10^{5}

解法

とりあえずクエリは無視して、各参加者の手が固定されているときにそれぞれの人が優勝できる条件を考えます。

例としてグーの手の人が優勝できるかを考えます。もちろん、グーだけでなく全ての手の人の優勝可能性について同じ方法が使えます。

パーと当たらなければ良いので、グーの人は「全てのパーを、自分が当たる前にチョキ(または他のパー)に倒してもらえる」場合に優勝できます。この条件は、

  • 自分より左にパーがいないか、自分より左にチョキがいる
  • 自分より右にパーがいないか、自分より右にチョキがいる

ことの両方を満たすこと、と言い換えられます。片側にいる全てのパーを同じ側のチョキと必ず戦わせることができるのかは考えなければいけませんが、その間にいる人同士を残り1人になるまで適当に戦わせることにすれば、最後に残った1人はパーとチョキの少なくとも片方で倒せるので、戦わせることは必ず可能です。

ということで、グーの人がどの範囲にいれば優勝できるかを考えると、次のようになります。

  • パーがいない場合、全てのグーが優勝できる。
  • パーがいてチョキがいない場合、全てのグーが優勝できない。
  • 両方いる場合、以下の範囲以外のグーが優勝できる。
    • 最左のパーより右で、最左のチョキより左。
    • 最右のパーより左で、最右のチョキより右。

f:id:betrue12:20181226001525p:plain

かなりシンプルな形になりました。あとはこれをどう効率的に処理するかをクエリ込みで考えていきましょう。

ある範囲内にいるグーの人数は累積和、クエリによる変動を考慮するとBITで処理できます。最左/最右にいるチョキ/パーの位置はsetに入れて最小値/最大値を見ればよいです。このように処理すればクエリ処理と答えを求める処理をともに  O(\log n ) で実現でき、初期状態の構築込みで全体計算量  O((n+q)\log n ) となり間に合います。

ACコード

私の印象としてはCよりこちらのほうが簡単だったり…?考察寄りの問題が多いAtCoderに慣れていると、こちらのほうが解きやすく感じるかもしれません。AGCで出てきそう。