Educational Codeforces Round 52 参加記録＆解説（A～F）

Dashboard - Educational Codeforces Round 52 (Rated for Div. 2) - Codeforces

結果は4完で194位。DがHackで落ちました…

f:id:betrue12:20181012201409p:plain

A～Fの6問を振り返ります。

A. Vasya and Chocolate

Problem - A - Codeforces

問題概要

以下の問題 $t$ 個に答えよ。

所持金 $s$ ルーブルで、1つ $c$ ルーブルのチョコを買えるだけ買う。また、チョコを $a$ 個買うごとに追加で $b$ 個のチョコがもらえる。入手できるチョコの総数を求めよ。

制約

$1 \le t \le 100$
$1 \le s, a, b, c \le 10^{9}$

解法

買えるチョコは $n_{1} = \lfloor\frac{s}{c}\rfloor$ 個です。これを $a$ 個1組とすると $\lfloor\frac{n_{1}}{a}\rfloor$ 組買っているので、追加でもらえるチョコは $n_{2} = \lfloor\frac{n_{1}}{a}\rfloor \times b$ 個です。 $n_{1} + n_{2}$ が答えです。

ACコード

（C++）Submission #44119682 - Codeforces

B. Vasya and Isolated Vertices

Problem - B - Codeforces

問題概要

$n$ 頂点 $m$ 辺の単純な無向グラフの中で、孤立点が最も少ないグラフと、最も多いグラフを考える。それぞれの孤立点の数を求めよ。

制約

$1 \le n \le 10^{5}$
$0 \le m \le \frac{n(n-1)}{2}$

解法

孤立点を最も少なくするには、孤立点同士を辺で結んでいくのがよいです。1本の辺につき孤立点が2個減るので、孤立点の最小数は $\max(0, n-2m)$ となります。

孤立点を多くするには、なるべく少ない頂点だけで全部の辺を持ちたくなります。そのため、完全グラフを作るように辺を張っていくとよいです。 $k$ 頂点の完全無向グラフの辺数は $\frac{k(k-1)}{2}$ 本なので、 $m \le \frac{k(k-1)}{2}$ であれば $k$ 頂点で $m$ 本の辺を持てます。この不等式を満たす最小の $k$ を求めて、孤立点の最大数は $N-k$ となります。

ACコード

Submission #44123483 - Codeforces

C. Make It Equal

Problem - C - Codeforces

問題概要

ブロックが積まれてできた $n$ 本の塔があり、それぞれの高さはブロック $h_{i}$ 個である。

以下の操作を、全ての塔の高さが等しくなるまで繰り返す。操作回数の最小値を求めよ。

ある高さを決める。このとき、その高さ以上にあるブロックの個数が $k$ 個以下でなければならない。その高さ以上のブロックを全て取り除く。

制約

$1 \le n \le 2\times 10^{5}$
$n \le k \le 10^{9}$
$1 \le h_{i} \le 2 \times 10^{5}$

解法

毎回の操作で、 $k$ 個を超えないギリギリまでブロックを取り除くのがもちろん最適です。そのため、上から数えたブロック数が $k$ 個を超えない最小の高さを求めたくなります。

「今の操作で除去できる残りブロック数」を管理しておいて、今の操作でどこまで除去できるか1段ずつ調べます。このとき「今の時点で一番高さが高い塔の本数」を管理しておくと、1段下げたときいくつのブロックが除去されるかが分かります。

残りブロック数が足りなくなった時点で、次の操作に移ります。これを一番低い塔の高さに到達するまで繰り返します。

$h_{i}$ の上限が少ないので、これで十分間に合います。

ACコード

（C++）Submission #44183329 - Codeforces

本番ではもう少しまとめて計算するようなコードを書いていて、こっちだと $h_{i}$ が大きくても対応できるのですが、そのぶん実装が少しだけ複雑です。

D. Three Pieces

Problem - D - Codeforces

問題概要

$N \times N$ のチェス盤の各マスに、 $1, 2, ..., N^{2}$ の数字が1つずつ記載されている。このチェス盤上で、以下の操作を行う。

1のマスに、ルーク・ビショップ・ナイトのうち好きな種類の駒を置く。
以下の操作を好きな順番で繰り返し、の順にマスを訪れる。途中で他のマスを経由しても良い。
- チェスのルールにおける駒の動き方に則って駒を1手分動かす。
- 駒をルーク・ビショップ・ナイトのいずれかに交換する。

$N^{2}$ が書かれたマスに到達するまでの操作の合計回数を $a$ 、そのうち駒の種類を交換した回数を $b$ として、 $(a, b)$ を辞書順最小にしたい。そのような $a, b$ を求めよ。

制約

$3 \le N \le 10$
マス $(i, j)$ に書かれた数を $A_{ij}$ として、 $1 \le A_{ij} \le N^{2}$ でありこれらは互いに異なる

解法

駒の交換と移動があり、遷移が複雑です。グラフに帰着して、最短路問題などのアルゴリズムを使って上手く処理したいです。

状態として「位置」と「駒の種類」の組み合わせを考え、それぞれが1頂点となるようなグラフを考えます。頂点の数は $V = 3N^{2} \le 300$ です。駒の移動も交換も、この頂点間の遷移として考えることができます。

頂点間の距離は、求める答えと同じように $(操作回数, そのうちの駒交換回数)$ のペアで定義し、辞書順比較します。駒の移動と交換に対応する遷移を辺として追加し、ワーシャルフロイド法を用いると、ある状態からある状態までの最短距離を計算することができます。 $V \le 300$ なので $O(V^{3})$ のワーシャルフロイドが間に合うのがポイントです。

これを用いて答えを求めましょう。 $1, 2, ..., N^{2}$ を順に通る最短路を求めるにあたり、「頂点 $1, ..., i$ までの巡回が完了し、今の駒が $j$ であるときの、最初の状態からの最短距離」を $dp\lbrack i \rbrack \lbrack j \rbrack$ としてDPができます。 $dp\lbrack i+1 \rbrack \lbrack j \rbrack$ を求めるときには、 $dp\lbrack i \rbrack \lbrack 0 \rbrack, dp\lbrack i \rbrack \lbrack 1 \rbrack, dp\lbrack i \rbrack \lbrack 2 \rbrack$ すべてからの遷移を試して最も小さいものを採用します。これを $i=N^{2}$ まで回せば答えが求められます。

ACコード

（C++）Submission #44180256 - Codeforces

E. Side Transmutations

Problem - E - Codeforces

問題概要

$|A|$ 種類の文字があり、その一部または全部で構成される $n$ 文字の文字列を考える。

整数 $b_{1}, ..., b_{m}$ が与えられる。文字列 $S$ と $T$ は、 $S$ に以下の操作を0回以上行って $T$ と一致させることができる時、「等しい」と呼ぶ。

$b_{i}$ を1つ選ぶ。操作対象の文字列の前 $b_{i}$ 文字と後ろ $b_{i}$ 文字を、それぞれ反転して交換する。

「等しい」文字列は区別せず1種類と数えることにしたとき、 $n$ 文字の文字列の種類数を数え上げて、 $998244353$ で割った余りを出力せよ。

制約

$2 \le n \le 10^{9}$
$1 \le m \le \min(\frac{n}{2}, 2\times 10^{5})$
$1 \le |A| \le 10^{9}$

解法

問題文の操作を繰り返すことで、何が起こるでしょうか。例えば、2つの異なる箇所で操作を行うと、以下のように文字列が変化します。

f:id:betrue12:20181012224005p:plain

$b_{i}$ の位置を区切りとして、左右それぞれ対応するペアを考えます。操作を繰り返すことで、任意のペアを入れ替えることができます。つまりこのペアをいくつか入れ替えることで一致するような文字列が、今回の問題でいう「等しい」文字列です。

ペアの入れ替えを独立に考えられるので、場合の数も独立に考えて掛け算することができます。 $b_{1} - b_{0}$ 文字のペア、 $b_{2} - b_{1}$ 文字のペア…というように、それぞれのペアについて独立に「反転で一致するものを同一視したときに文字列が何通りあるか」を数えて、これを掛け算すればよいです。（ $b_{0} = 0$ としておくと便利です）

ただし真ん中の部分の文字列は反転できないので、単純に「文字列が何通りあるか」を数えて掛け算します。それらを全て掛け合わせたものが答えです。

各ペアについての場合の数を考えます。 $d_{i} = b_{i+1} - b_{i}$ と置くと、求めたいものは「長さ $2d_{i}$ の文字列を、反転すると一致するものは同一視して数えたときの場合の数」です。「反転すると一致する」文字列は、文字列が回文でない場合は1対1で相手が存在し、回文である場合は反転しても自分自身になるので相手が存在しません。

そのため反転を同一視しない全ての文字列の数を $n_{all}$ 、回文になっている文字列の数を $n_{pal}$ とすると、回文になっていない文字列が同一視で半減することから、求めたい数は $\frac{n_{all} - n_{pal}}{2} + n_{pal}$ となります。具体的に計算すると $n_{all} = |A|^{2d_{i}}$ 、 $n_{pal} = |A|^{d_{i}}$ であるため、これらを全て計算していけばよいです。

ACコード

（C++）Submission #44153485 - Codeforces

F. Up and Down the Tree

Problem - F - Codeforces

問題概要

根を頂点1とする $n$ 頂点の根付き木と、整数 $k$ が与えられる。頂点1にトークンを置いた状態から、以下の操作を0回以上繰り返す。

いまトークンが置かれている頂点をとして、
- $v$ が葉でない場合、 $v$ 以下の部分木に含まれる葉のうちいずれかにトークンを移す。
- $v$ が葉である場合、 $v$ から最大 $k$ 回親を辿った先の頂点にトークンを移す。

頂点1にトークンを置いた状態からスタートし、なるべく多くの葉を訪れたい。その最大数を求めよ。

※接続されている辺の数が1本である頂点を葉と呼ぶが、今回は根である頂点1は葉ではないとして扱う。

解法

ある頂点から葉に降りたときに、元の頂点に戻って来れる場合と来れない場合があります。イメージとしては、葉が深いところにあり、途中で経由できるような葉もないときは戻ってこれません。

そのため、ある頂点以下の部分木でなるべく多くの葉を訪れようとすると、以下のような戦略になります。

全ての子に対して、まずは降りた後に自分自身に戻って来れる範囲で葉を回収する。
最後に1つだけ子を選んで降り、戻って来れない範囲の葉も回収し、操作を終える。

これは再帰的に処理していくことができます。つまりそれぞれの頂点に対して、

$dp_{1}\lbrack i \rbrack$ = 頂点 $i$ 以下の部分木で、 $i$ から始めて自分自身に戻って来ることが必要な場合、いくつ葉を回収できるか
$dp_{2}\lbrack i \rbrack$ = 頂点 $i$ 以下の部分木で、 $i$ から始めて自分自身に戻って来なくてもよい場合、いくつ葉を回収できるか

を葉のほうから決めていくような木DPができます。 $dp_{2}\lbrack 1 \rbrack$ が答えです。

このDPの遷移を考えます。ある頂点 $i$ に着目し、その子 $j$ を順に見ていきます。

子 $j$ から $i$ に（ $j$ 以下のいずれかの葉を経由して）移動できる場合は、 $i$ から $j$ 側に降りて $dp_{1}\lbrack j \rbrack$ 個の葉を回収し、また $i$ に戻ってくることができます。もし最後に子 $j$ 側に降りるのであれば、追加で $dp_{2}\lbrack j \rbrack - dp_{1}\lbrack j \rbrack$ 個の葉を回収することができます。
子 $j$ から $i$ に移動できない場合は、葉を回収して戻ってくることができません。ただし、最後に子 $j$ 側に降りるのであれば $dp_{2}\lbrack j \rbrack$ 個の葉を回収することができます。

このようにそれぞれの子からの情報を得て、「戻ってこれる範囲で回収できる葉の数」の合計を $dp_{1} \lbrack i \rbrack$ とし、「最後に子 $j$ に降りるのであれば追加で回収できる葉の数」の最大値を $dp_{1} \lbrack i \rbrack$ に足したものを $dp_{2} \lbrack i \rbrack$ とします。