ARMERIA

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

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

 998244353 猛プッシュ回。その真意はG問題にありましたが、私は解けませんでした…

f:id:betrue12:20181229143906p:plain

※2019/01/16 E問題を追記。

A. Find Divisible

Problem - A - Codeforces

問題概要

以下の問題  T 個に答えよ。

  • 整数  l, r が与えられる。 l \le x, y \le r かつ  x \ne y かつ  x y の約数であるような整数  x, y を1組求めよ。

制約

  •  1 \le T \le 1000
  •  1 \le l \le r \le 998244353
  • 解の存在が保証されている

解法

 x y もある区間内に収めないといけないので、なるべく近くしたいです。そうすると  y = 2x となるような値を取りたくなります。

そのうえで  x区間の左端ギリギリに取ると  x = l, y = 2l であり、これが最も「区間に含まれやすい」ペアになります。これが区間  \lbrack l, r \rbrack に含まれない場合は解が存在しないので、入力としては与えられません。

ACコード

Submission #47625206 - Codeforces

B. Substring Removal

Problem - B - Codeforces

問題概要

長さ  n の文字列  s が与えられる。この  s の空でない連続部分列のとり方のうち、「その連続部分列を取り除くと、残った文字が1種類または0種類になる」という条件を満たすものの個数を求め、998244353で割った余りを出力せよ。

制約

  •  2 \le n \le 2\times 10^{5}
  •  s は英小文字からなる
  •  s には少なくとも2種類の文字が含まれている

解法

いくつかの場合に分けて考えます。

  • 全部の文字を取り除く
    • 問題文よりこれはカウント対象になるので、必ず1通りが加算されます。
  • 文字列の右側を取り除く
    • 左端の文字が残るので、「左端から連続して1種類だけの文字を残す方法は何通りあるか?」ということになります。これは左端から連続して同じ文字がいくつ続いているかの値と一致します。
  • 文字列の右側を取り除く
    • さっきと逆です。
  • 文字列の真ん中を取り除く
    • この場合、まず左端の文字と右端の文字が一致していることが必要です。一致している場合、左端から何文字残すか、右端から何文字残すかをそれぞれ掛け算すればよいです。

まとめると、左端から同じ文字が連続している個数を  l 、右端から同じ文字が連続している個数を  r とすると、

  • 左端と右端の文字が一致している場合:  1 + l + r + lr
  • そうでない場合:  1 + l + r

が求める数となります。オーバーフローと余りを取る操作については注意しましょう…

ACコード

Submission #47630409 - Codeforces

C. Polygon for the Angle

Problem - C - Codeforces

問題概要

以下の問題  T 個に答えよ。

  • 度数法の角度を示す整数  ang が与えられる。「正  n 角形においてある3頂点を取った時、なす角が  ang になる」という条件を満たす最小の  n を求めよ。またはそのような  n が存在しないことを判定せよ。

制約

  •  1 \le T \le 180
  •  1 \le ang \lt 180
  • 答えが存在する場合は  n \le 998244353 であることが保証される

解法

※説明中に点a, b, cという表記を使います。問題文中の図に合わせているのでそちらを参照してください。

正多角形は円に内接するので、円として考えます。円周角の定理を使うと、円周上の3点を取った時のなす角を計算することができて、これは

  •  180^\circ \times \frac{(弧acの長さ)}{(円周の長さ)}

となります。ただし弧acは点bと反対側の弧とします。

今回の場合は正多角形なので、弧acが正  n 角形の辺  k 本に対応している場合

  •  ang = 180 \times \frac{k}{N}

となります。この  k が整数で、かつ  k \lt N-1 である必要があります。 k = N-1 だと、弧acの反対側に1つも頂点がなく、点bを取ることができないからです。(サンプルにあるように90角形で2度を作れないのはこの条件によるものです)

あとは  n を総当たりしていけばよいです。実際にやってみると  3 \le n \le 360 で制約内の全ての  ang について答えが出るので、この範囲で総当たりすれば十分間に合います。

ACコード

Submission #47634550 - Codeforces

D. Easy Problem

Problem - D - Codeforces

問題概要

[tex n] 文字の文字列  s が与えられる。この文字列から0個以上の文字を取り除き、部分列(連続とは限らない)に hard という文字列を含まないようにしたい。

 i 文字目を取り除くコストは  a_{i} である。条件を満たすための最小コストを求めよ。

制約

  •  1 \le n \le 10^{5}
  •  s は英小文字からなる
  •  a \le a_{i} \le 998244353

解法

左からDPをします。「  i 文字目まで見て、 hard のうちちょうど  j 文字目までが部分列に含まれているようにするための最小コスト」を  dp\lbrack i \rbrack \lbrack j \rbrack とします。

例えば  j = 1 のとき、既に部分列は h を含んでいることになります。この状態で a を消さずに受け入れてしまうと、 j = 2 に遷移をしてしまいます。 j = 4 になるとアウトです。

より一般的に  dp\lbrack i \rbrack \lbrack j \rbrack からの遷移を考えます。次の文字  s\lbrack i+1 \rbrackhard j+1 文字目と一致していない場合はノーコストで  dp\lbrack i+1 \rbrack \lbrack j \rbrack に遷移できます。一致している場合は、

  • 取り除くためのコストを加算し、 dp\lbrack i+1 \rbrack \lbrack j \rbrack に遷移する。
  • その文字を受け入れて、コストを加算せずに  dp\lbrack i+1 \rbrack \lbrack j+1 \rbrack に遷移する。

の2通りがあります。

これを文字列の最後まで行い、 dp\lbrack N \rbrack \lbrack 0 \rbrack dp\lbrack N \rbrack \lbrack 3 \rbrack のうち最も小さいものが答えです。

ACコード

Submission #47636462 - Codeforces

E. The Top Scorer

Problem - E - Codeforces

問題概要

 p 人の人がゲームを行った。全員の得点は非負整数で表され、その合計は  s 点だった。一番点数が高い人が優勝者であり、複数人いる場合は等確率で誰か1人が優勝者に選ばれる。

あるプレイヤー(ハサン)の得点は  r 点以上だったことが分かっている。プレイヤー同士は区別され、全員の得点分布としてあり得るもの全てが等確率で起こるとしたとき、ハサンが優勝する確率を求めよ。

答えは有理数となるため、答えを既約分数  \frac{P}{Q} としたときの  PQ^{-1} \mod 998244353 を出力せよ。

制約

  •  1 \le p \le 100
  •  0 \le r \le s \le 5000

解法

「一番点数が高い人が複数いる場合は等確率で誰か1人が優勝者となる」の部分がとても厄介に見えます。幸い人数  p は小さいので、「同着一位が何人いるか」を全て場合分けすることを考えます。

さらに優勝者の点数も全探索すると、「ハサンが  a 点取って一位となり、ハサンも含めた同着一位が  b 人いるような場合の数」というものを考えることができます。それぞれの動く範囲は  r \le a \le s 1 \le b \le p で、さらに  ab \le s が満たされている必要があります。

この場合、まずハサン以外に  a 点を取った人は誰かという選び方が  _{p-1}C_{b-1} 通り。そして残った  s-ab 点を  p-a 人で分ける分け方で、残り全員の点が  a 点未満であるような場合の数を掛け算すると、パラメータ  (a, b) に対応する場合の数が求められます。

というわけで必要なものは、「 x 点を  y 人で分ける分け方で、全員の点が  z 点未満であるような場合の数」です。これは包除原理を用いると、

  •  x 点を  y 人で分ける分け方で、ある  i 人を選んだ時にその  i 人が  z 点以上を取っているような場合の数」 \times (-1)^{i}

を、全ての  i=0, 1, ..., y および全ての  i 人の選び方について足したものとして求められます。

これを求めます。 y 人の中で  i 人選ぶのが  _{y}C_{i} 通り。そしてその人達に予め  z 点ずつを割り振っているので残りの点数は  x - iz 点となり、この点は  i 人の中に選んだかどうかに関わらず自由に  y 人に割り振って良いので、重複組合せを用いて  _{x-iz+y-1}C_{y-1} 通りとなります。この2つを掛け算すると求めたい場合の数が求められます。

最後に、求めたいものは確率なので、場合の数から確率にするために全ての場合の数が必要です。これも重複組合せを用いて求めることができて、 r 点をハサンに割り振った残りの  s-r 点を自由に割り振ると考えると  _{s-r+p-1}C_{p-1} となります。

これで全ての材料が揃いました。解法の手順としては、

  1. 必要な分の階乗と階乗逆元を前計算しておく。
  2. 「ハサンが  a 点取って一位となり、ハサンも含めた同着一位が  b 人いるような場合の数」を、組み合わせや包除原理を用いて求める。これを同着人数  b で割ったものを取り得る全ての  (a, b) について計算し合計しておく。
  3. 上記の合計を、全ての場合の数で割る。これが求めたい確率である。

となります。 a, b そして包除原理における  i を全探索するので、 r が小さい時(計算量がより悪い時)を考えると全体計算量は  O(sp^{2}) となります。

ACコード

Submission #48426919 - Codeforces

F. Inversion Expectation

Problem - F - Codeforces

問題概要

長さ  n の数列  p_{1}, ..., p_{n} が与えられる。これは  1, ..., n を並び替え、いくつかを  -1 に置き換えたものである。

 1, ..., n のうち数列に登場しない整数を1つずつ  -1 の場所に当てはめる。どのような当てはめ方も同じ確率であるとする。このとき、数列の転倒数の期待値を求めよ。

答えは有理数となるため、答えを既約分数  \frac{P}{Q} としたときの  PQ^{-1} \mod 998244353 を出力せよ。

制約

  •  1 \le n \le 2\times 10^{5}
  •  p_{i} 1, ..., n または  -1 であり、 -1 でない要素は相異なる

解法

与えられた数列において  -1 でない要素を確定済み、  -1 である要素を未確定の要素と呼ぶことにします。

転倒数を、「確定済み・確定済みのペア」「未確定・未確定のペア」「確定済み・未確定のペア」の3種類に分けて計算していきます。

確定済み・確定済みのペア

これは普通に転倒数を求めればよいです。BITを使うことができます。

入力に  -1 が存在しない場合は、ここで計算をやめて出力すればよいです。

未確定・未確定のペア

入力に含まれる  -1 の個数を  k 個とします。このとき、未確定同士のペアは全部で  \frac{k(k-1)}{2} 個あります。

これらそれぞれのペアについて、「転倒している」つまり大きい値が小さい値よりも左に置かれる確率は  \frac{1}{2} です。

つまり未確定同士のペアによる転倒数の期待値は  \frac{k(k-1)}{4} となります。4で割り切れない可能性があるので割り算には逆元を使いましょう。

確定済み・未確定のペア

これが一番面倒でしょうか。

f:id:betrue12:20181229142508p:plain

この図に、「確定済み要素 > 未確定要素」である転倒ペアの数え方をまとめています。確定済み要素それぞれについて、「右側にいくつ未確定要素があるか」を重みとしてBITに加算します。

次に未確定の整数それぞれについて、BITで自分より数値が大きい範囲の区間和を求めます。そうするとこれは、「その未確定の整数を  -1 のどこかに置いたときに転倒ペアがいくつできるか」を、全ての  -1 の位置について合計したものになります。

ある未確定の整数がある  -1 の位置に入る確率は  \frac{1}{k} なので、期待値はさきほどの値を  \frac{1}{k} 倍したものになります。

「確定済み要素 < 未確定要素」である転倒ペアの個数も同じようにして求めることができます。

また、この計算では確定済みの要素について全部BITに加えてから区間和を取るので、BITではなく通常の累積和でも可能です。どのみち確定済み・確定済みのペアの計算でBITを使うので、BITを使ってしまったほうがバグりにくくて楽だとは思います。

これらのパターン全てを合計すると答えが求められます。

ACコード

Submission #47644155 - Codeforces