乐胖代购免代理版

$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 \rbrack$ が hard の $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}$ となります。

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

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

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