コンテスト中AC: A〜F

C - Slot Strategy

解法は公式解説と同じだったので、実装例だけ書いておきます。

$S_i$ の左から $j_i$ 番目に文字 $x$ があるとして、 $j_i$ を配列に記録しておきます。これを、
$v_x =\{j_1,...,j_N\}$
とします。

これを昇順ソートして、ランレングス圧縮すると、文字 $x$ が何番目に何個出現するかという組が得られるので、あとは公式解説の方法で計算できます。
Submission #31861075 - AtCoder Beginner Contest 252

D - Distinct Trio

"3つがすべて異なる"は、"2つ以上同じものが存在することの補集合"と捉えられます。

そこで、各整数について、ちょうど2個同じ場合とちょうど3個同じ場合の総和を求め、3つを選ぶ総数から引くことにします。
なお、重複なく選ぶことを前提とします。

では、その求め方です。
ここで、 $cnt_i$ を整数 $i$ の出現数とします。

整数 $i$ がちょうど2個同じ
$cnt_i \geq 2$ である必要があります。
$i$ を2個選ぶ組み合わせは $_{cnt_i}C_2$ 通りです。
残り1つは $i$ 以外ならなんでも良いので、 $N-cnt_i$ 通りです。
よって、 $_{cnt_i}C_2 \times (N-cnt_i)$ 通りです。
整数 $i$ をちょうど3つ選ぶ
$cnt_i \geq 3$ である必要があります。
整数 $i$ から3つ選ぶ組み合わせなので、 $_{cnt_i}C_3$ です。
全体から3つを選ぶ総数
$_{N}C_3$ となります。

3から、各整数についての1,2の総和を引けば答えとなります。

時間計算量は、 $O(min(A_{max},N))$ かなと思います。なお、 $A_{max}$ は $A$ に含まれる整数の最大値です。

E - Road Reduction

$d_2,...,d_N$ が、都市1から各都市への最短路であれば、条件を満たすことができます。
辺のコストが非負整数なので、ダイクストラ法で最短経路を求められます。ダイクストラ法で最短路に使用する辺がわかるので、これを残しておけば、そのまま問題の答えになります。

この方法によって、もう一つの答えの条件である辺が $N-1$ 個になる、すなわち木になるかどうかについてですが、コンテスト中は、閉路はできないだろう、と直感的に解いてしまい、考察が不十分だったので、もう少ししっかり考えてみます。

説明1
ダイクストラ法の各段階において。最短路が見つかっている頂点集合を $S$ 、見つかっていない頂点集合を $T$ とします。
ここから、 $T$ のある頂点 $v$ の最短路が決定するとします。

もし、 $S$ に含まれる頂点 $u_1,...,u_m$ が $v$ と辺で繋がっていたとしてもその中から最短路として選ばれるのはただ1つです。よって、 $S$ と $T$ の任意の辺を繋いで閉路ができることはないです。

また、 $S$ に含まれるもの同士で繋がることもあり得ません。

以上より、ダイクストラ法の各段階で、閉路が生成されることはないので、最終的に出来上がるものは木になります。

説明2

以下を証明してみます。
無向グラフ $G=(V,E)$ にダイクストラ法を適用し、始点 $s$ からの最短路を見つける。ダイクストラ法の各段階において、 $s$ からの最短路が見つかっている頂点数が $k$ 個であるとき、この頂点集合を $V'_k$ とおく。また、 $V'_k$ に含まれる任意の頂点への最短路を構成する辺集合を $E'_k$ とする。

$V'_k,E'_k$ からなる、 $G$ の部分グラフ $G'_k=(V'_k,E'_k)$ は常に木であることを示す。なお、木であるとは、以下が成り立つことである。

$G'$ は連結
$|E'| = |V'|-1$

$G'_1$ のとき、 $V'_1$ には $s$ のみが存在し、連結です。 $|V'|=1,\ |E'| =0$ より、 $|E'| = |V'|-1$ を満たします。

$G'_k$ のときに成り立つと仮定します。
ダイクストラ法によって、 $V\backslash V'_k$ に含まれるある頂点 $v$ の最短路が決定されるとします。
この時、最短路決定に使用された辺 $e=(u,v)$ が存在します。なお、頂点 $u$ は $V'_k$ に含まれる頂点の１つです。

$V'_k$ に $v$ 、 $E'_k$ に $e$ がそれぞれ追加されたものが $V'_{k+1},E'_{k+1}$ となります。

まず、仮定より $G'_k$ は連結です。また、新たに追加された $v$ は $u$ と連結なので、 $G'_{k+1}$ は連結です。

次に、 $|V'_k| =| V'_{k+1}| -1$ 、 $|E'_k| = |E'_{k+1}|-1$ です。仮定より、 $|E'_k| = |V'_k|-1$ が成り立っているので、代入することで $|E'_{k+1}| = |V'_{k+1}|-1$ が得られます。

以上で、帰納法によって、 $G'_k=(V'_k,E'_k)$ は常に木であることが示せたと思います。

Submission #31869657 - AtCoder Beginner Contest 252

F - Bread

解法は公式解説と同じでした。

公式解説のように解法の正当性を厳密に証明できませんでしたが、コンテスト中に大雑把に考えていたことを書きます。

操作の逆を考えたとき、長さ $x$ と長さ $y$ のパンから長さ $x+y$ のパンを得ることを合体と呼ぶことにします。

まず、入力例1からどのように操作すると解が悪化するのか考えました。
例えば、
2+2=4
4+1=5
5+1=6
7+1=7
とすると、解は4+5+6+7=22になり、16より悪化します。
これより、大きい数に合体していくと解は悪くなりそうだとわかりました。ということは、逆に小さいものを2つ選んで合体していけばよいだろうと考えました。

次に、小さいものを2つ選んで合体すると、その後の解に影響を与えるか考えてみました。例えば、入力例1で、最初に1と1を合体した場合と1と2を合体した場合を考えます。

この操作によって、2と3のいずれかが生成されるわけですが、2や3はまた更に合体しないといけないので、追加で2または3のコストがかかります。それなら、1と1を合体したほうがよいです。

こんな感じでしたが、一応ACはできました。
Submission #31875956 - AtCoder Beginner Contest 252

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 252 参加記録

C - Slot Strategy

D - Distinct Trio

E - Road Reduction

F - Bread