Codeforces Manthan, Codefest 18 参加記録

何か不規則な解き方してますが、Fが通ったおかげでレートも結構上がりました。Dは誤読で落ちました（にゃーん）

f:id:betrue12:20180903203023p:plain

後から解いたものも含めてA～Fを振り返ります。

A. Packets

問題概要

1円玉 $n$ 枚をいくつかの袋に入れて、「袋をいくつか適切に選ぶことで、合計金額 $0, 1, 2, ..., n$ 円*1の全通りが作れる」状態にしたい。最小の袋の数を求めよ。

解法

2進数で作るとよさそうです。 $2^{m} -1 \le n$ である最大の整数を $m$ として、 $m$ 個の袋に $1, 2, 4, ..., 2^{m-1}$ 円を入れると、 $0, 1, 2, ..., (2^{m}-1)$ 円の全パターンが作れます。端数が出た場合は、余った分をもう1つの袋に入れれば、 $n$ まで全部のパターンを作れます。つまり袋の数は、 $2^{M} - 1 \ge n$ であるような最小の整数 $M$ となります。構成方法を示したので、これは十分条件です。

次に必要性、つまりこれより小さい解がないことを確かめます。 $M$ 個の袋を使って得られるパターン数は、いくら値が被らないように努力したとしても、全ての袋について「選ぶ」「選ばない」で分岐した高々 $2^{M}$ 通りです。作る必要があるパターン数は $n+1$ 通りなので、 $2^{M} \ge n+1$ が必要条件となります。これは上の式に一致するので、ちょうど必要十分です。

ACコード

（C++）Submission #42367865 - Codeforces

B. Reach Median

Problem - B - Codeforces

問題概要

要素数が $n$ （奇数）の数列 $a_{1}, ..., a_{n}$ と整数 $s$ が与えられる。操作「数列の要素 $a_{i}$ を1つ選び、+1または-1を足す」を繰り返して数列の中央値を $s$ にしたい。操作の最小回数を求めよ。

解法

要素数が奇数の数列の中央値が $s$ になる条件は、要素を左から右に昇順ソートしたときに真ん中の要素が $s$ であることです。もう少し全体的に見ると、

真ん中の要素が $s$ である
真ん中より左の要素が $s$ 以下である
真ん中より右の要素が $s$ 以上である

このようになっていればよいです。

元の数列を昇順ソートして、上記の条件を満たすように加減してやればよいです。わざわざ大小の順番を入れ替えるような操作は、得になることはありません。

ACコード

（C++）Submission #42370350 - Codeforces

C. Equalize

Problem - C - Codeforces

問題概要

長さ $n$ で各文字が0か1の文字列 $a, b$ が与えられる。 $a$ に以下の操作を好きな順序で好きな回数繰り返して、 $b$ と一致させたい。最小のコストを求めよ。

$a$ の文字を1つ選んで書き換える。コスト1。
$a$ の文字を2つ選んで入れ換える。コストは入れ換える2文字の距離。

解法

まず、「入れ換える」ことで得になるケースはかなり限られています。入れ換える操作は、最大2文字を書き換える操作をすれば同じことができて、そのコストは最大でも2です。つまりコストが2以上かかるような入れ換え操作はする必要がなくて、

隣り合った2文字を両方書き換える（コスト2）代わりに、その2文字を入れ換える（コスト1）

以外の入れ換え操作では得をしないことがわかります。そのため、

$a$ 側が「10」で $b$ 側が「01」、あるいはその逆である箇所のみ、入れ換え操作を行う。
それ以外の場所は単純に書き換え操作を行う。

これで最適となります。

ACコード

（C++）Submission #42373970 - Codeforces

D. Valid BFS?

Problem - D - Codeforces

問題概要

$n$ 頂点の木と、 $1, ..., n$ を並び替えた数列 $a_{1}, ..., a_{n}$ が与えられる。数列が「木を頂点1からBFSしたときの探索順序」になっているか判定せよ。

解法

問題文にも書いてありますが、BFSを実装する際は

始点をキューに入れる。
キューから頂点番号を取り出す。
その頂点に隣接する頂点のうち未訪問のものをキューに入れる（普通のBFSでは、このときのpush順序は実装者が勝手に選ぶ）。
2に戻る。

を、キューが空になるまで続けます。

今回は始点と探索順序が指定されているので、

まず数列の始点 $a_{1}$ をキューに入れる。ただし、これが1でない場合は No で終了。
キューから頂点番号を取り出す。
数列で指定された順に、その頂点に隣接する頂点のうち未訪問のものをキューに入れる。このとき、指定された次の番号が隣接する頂点として取れない場合、順番が守れないので No で終了。
2に戻る。