ARMERIA

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

Codeforces Round #529 参加記録&解説

Dashboard - Codeforces Round #529 (Div. 3) - Codeforces

だいたい1時間で全完。平和なDiv3でした。

f:id:betrue12:20181228151449p:plain

A. Repeating Cipher

Problem - A - Codeforces

問題概要

ある文字列  s に対して、各文字を「1文字目を1個、2文字目を2個…」と並べた文字列  t が与えられる。 t から  s を復元せよ。

制約

  •  1 \le |s| \le 10
  •  1 \le |t| \le 55
  • 解の存在が保証されている

解法

解の存在が保証されているので、 s のそれぞれの文字が  t の何文字目に存在するかを計算して集めてくればよいです。

ACコード

Submission #47556204 - Codeforces

B. Array Stabilization

Problem - B - Codeforces

問題概要

長さ  n の数列  a_{1}, ..., a_{n} が与えられる。この数列から1つ要素を取り除いて「要素の最大値 - 要素の最小値」を最小にするとき、その値を求めよ。

制約

  •  2 \le n \le 10^{5}
  •  1 \le a_{i} \le 10^{9}

解法

最も大きい値を取り除くか、最も小さい値を取り除くかのどちらかが最適となるので、両方試します。要素をソートして「1番目に大きい要素 - 2番目に小さい要素」と「2番目に大きい要素 - 1番目に小さい要素」を両方計算して小さい方が答えです。

ACコード

Submission #47558356 - Codeforces

C. Powers Of Two

Problem - C - Codeforces

問題概要

整数  n, k が与えられる。 n をちょうど  k 個の2冪数の和で表現する方法を1つ出力せよ。またはそれが不可能であることを判定せよ。

制約

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

解法

まず、 n を最も少ない個数の2冪数の和に分解します。これは2進数展開をすればよいです。この時点で  k 個を超えてしまった場合は分割不可能です。

その後、「1でない2冪の数を1つ選んで半分ずつに分割する」という操作を  k 個になるまで繰り返せばよいです。個数が足りないのに分割できない場合(具体的には  n \lt k のとき)は不可能です。

実装は「 2^{m} の数が今いくつあるか」を  m ごとに個数で管理して、大きい方から見ていくと良いと思います。

ACコード

Submission #47563042 - Codeforces

D. Circular Dance

Problem - D - Codeforces

問題概要

 1, ..., n までの番号を持つ人が円形に並び、全員が時計回りの方向を向いている。各人について1つ先の人と2つ先の人の番号の情報が与えられるが、どちらがどちらかは与えられない。人の並び方としてあり得るものを1つ出力せよ。

制約

  •  3 \le n \le 2\times 10^{5}
  • 解の存在が保証されている

解法

まず  n = 3 の場合を除外しておきます。このときは各人について自分以外の2人の番号が与えられる場合しかないので、どのように並べても条件を満たします。適当に 1 2 3 などを出力しておけばよいです。

 n \gt 3 の場合、まず基準として1人目を番号1の人とします(誰でも良いです)。この1人目の次の2人、つまり2人目と3人目が  a_{1, 1} a_{1, 2} のどちらかです。

このとき、2人目の「次の2人」には3人目が含まれていて、3人目の「次の2人」には( n \gt 3 であれば)2人目は含まれていません。そのため  a_{1, 1} a_{1, 2} のうち、「次の2人」にもう片方を含んでいるほうが2人目になります。

これを最後の1人まで順番に繰り返していくと全ての順番が決まります。

ACコード

Submission #47565769 - Codeforces

E. Almost Regular Bracket Sequence

Problem - E - Codeforces

問題概要

長さ  n の括弧列  s が与えられる。 s の文字のうち、「その1文字を反転させることで  s が正しい括弧列になる」という条件を満たす文字の個数を求めよ。

制約

  •  1 \le n \le 10^{6}

解法

( を+1、) を-1として、 s の累積和を求めます。正しい括弧列の条件は

  • 任意の区切り位置で、累積和が0以上である。
  • 全ての文字の合計がちょうど0になる。

の2つを満たすことです。

まず合計だけを考えます。1文字の変更後に合計が0になることが必要条件なので、

  • 合計が2の場合、() に変えることで正しい括弧列になる可能性がある。
  • 合計が-2の場合、)( に変えることで正しい括弧列になる可能性がある。
  • そうでない場合、1文字変更後に正しい括弧列になることはない。

と場合分けできます。ここでもし合計が2の場合は  s 全体を鏡写しに(実装においては、文字列全体を反転させ、() を反転)することで合計が-2の場合と同一視できるので、こちらだけを考えます。

全体の合計が-2のときに、)( に変えることで正しい括弧列になる条件を考えます。

f:id:betrue12:20181228022040p:plain

上の図のように、文字を変更することで変更箇所より右側の累積和が+2されます。この状態で全ての位置の累積和が0以上になればよいので、

  • 変更位置より左側の累積が0以上である
  • 変更位置より右側の累積が-2以上である

ような ) が条件を満たします。あとはこれを順番に探していけばよいです。

ACコード

Codeforces

F. Make It Connected

Problem - F - Codeforces

問題概要

 n 個の頂点からなる無向グラフがあり、初期状態においては辺が存在しない。各頂点には整数  a_{i} が書かれている。

このグラフには以下の方法で辺を追加できる。

  • 通常の方法:頂点  i と 頂点  j を、コスト  a_{i} + a_{j} で結ぶ。
  • 特別な方法:「頂点  x と頂点  y をコスト  w で結んでよい」という条件が  m 個与えられるため、それを使う。

辺を追加し全ての頂点を連結にするまでの最小コストを求めよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  0 \le m \le 2\times 10^{5}
  •  1 \le a_{i} \le 10^{12}
  •  1 \le w \le 10^{12}

解法

最小全域木を作るように辺を追加していけばよいです。

あり得る辺を全て考えようとすると、  O(n^{2}+m) 本の辺を扱わないといけないので間に合いません。ただしこの問題の場合は、コストの最も小さい頂点を1つ固定すると、その頂点以外の2頂点を「通常の方法」で連結する辺は不要であることが分かります。

その理由をクラスカル法のアルゴリズムを元にして考えてみます。クラスカル法ではコストの小さい辺から順に、「その辺の両端が既に連結済みでなければ辺を追加する」ということを繰り返します。また、同じコストの辺はどちらを先に使っても正しい解が得られます。

例えば頂点1のコストが最も小さく、  a_{1} \le a_{2} かつ  a_{1} \le a_{3} であるとします。頂点  i, j を通常の方法で結ぶコストを  e_{ij} と表記すると、  e_{12} \le e_{23} かつ  e_{13} \le e_{23} が成立します。

つまりクラスカル法のアルゴリズムに基づいて辺を追加するならば、辺2-3よりも先に辺1-2と辺1-3の追加が行われて、その時点で頂点1, 2, 3が連結になります。そうなると、辺2-3を追加する意味はなくなります。

これをより一般的に考えると、「通常の方法」で追加する辺については、コストの最も小さい頂点を1つ固定し、そこから他頂点に伸びる  n-1 本の辺だけを考えれば十分であることが言えます。

あとはこれを「特別な方法」で追加できる  m 本の辺と混ぜてソートし、クラスカル法を回すことで答えが得られます。辺の数  E = n-1+m に対して計算量  O(E \log E ) なので間に合います。

ACコード

Submission #47575989 - Codeforces