ARMERIA

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

ABC115 参加記録＆解説

AtCoder プログラミング競技プログラミング

19分台全完で25位。20分切れたのは良いですね。

f:id:betrue12:20181208225414p:plain

A - Christmas Eve Eve Eve

A - Christmas Eve Eve Eve

解法

入力が4通りしかないので全部ifで分岐してもよいのですが、まず Christmas を出力して、 $25-D$ 回だけ [半角スペース]Eve を出力するとスマートです。

ACコード

B - Christmas Eve Eve

B - Christmas Eve Eve

解法

一番高い商品を半額にするのが最適です。そのため、

ソートして、最も高い商品を半額にして、合計する
最も高い商品の値段を調べて、元々の全商品の合計からその半額を引く

などの方法で解くことができます。

ACコード

C - Christmas Eve

C - Christmas Eve

解法

$N$ 本の中から $K$ 本を選ぶ時、できるだけ高さの近い木を選びたいです。そのため木を高さ順に並べて、連続する $K$ 本

$1, 2, ..., K$ 本目
$2, 3, ..., K+1$ 本目
...
$(N-K+1), (N-K+2), ..., N$ 本目

を全て試せば、そのうちのどれかが答えになっているはずです。これをすべて試して一番良いものを求めればOKです。

ACコード

D - Christmas

解法

ハンバーガーが再帰的に作られています。なので、計算も再帰的にしていくことを考えましょう。

一般に、レベル $k$ バーガーの下から $x$ 層目までを考えてみます。レベル $k$ バーガーを分解してみましょう。

f:id:betrue12:20181209205728p:plain

レベル $k$ バーガーの構成要素の中でどこに境界があるかによって、場合分けをすることができます。この場合分けの条件を知るためにはレベル $k-1$ バーガーの長さが必要です。

どこに境界があったとしても、レベル $k$ バーガーの下から $x$ 層は

単体のバン、パティ
レベル $k-1$ バーガーの全体
レベル $k-1$ バーガーの途中まで

のうちのいくつかから構成されています。この中にパティがいくつ含まれているかを考えます。

単体のパティはもちろんパティ1個。レベル $k-1$ バーガーの全体に含まれるパティの数は、あらかじめ計算しておくことができます。残るはレベル $k-1$ バーガーの途中までの部分ですが…これを次のようにさらに分解していきましょう。

f:id:betrue12:20181209205742p:plain

このように途中までのバーガーをどんどん「拡大」していって、バーガーのレベルを1つずつ下げていくことで、最悪の場合でもレベル0バーガーまで下げれば具体的な値を求めることができます。

境界がどこにある場合でも、レベル $k-1$ バーガーの途中までが含まれているのは高々1個です。そのため再帰関数も各レベルについて高々1回しか呼ばれないため、呼び出し回数の合計は $O(N)$ で済みます。

あとはこれを場合分け＆再帰関数で実装します。各計算に必要なのは、

レベル $k-1$ バーガー全部のパティ数
レベル $k-1$ バーガー全部の長さ

で、これはバーガーの作り方に従ってレベル0バーガーから漸化式を立て、前計算しておくことができます。

解法をまとめると、

レベル $0, ..., N$ バーガーのパティ数と長さを漸化式で前計算しておく。
再帰関数を実装する。再帰関数ではどこに境界があるかによって場合分けをし、前計算の結果を使って上の図のようにそれぞれ計算する。
レベル $N$ バーガーの下から $X$ 層目を再帰関数で計算する。

のようになります。

ACコード

C++のほうがコメント多め。上記コードの再帰関数は直接的な場合分けではなく、下から見ていって使ったぶんだけ $x$ を減らすようにしています。