AtCoder Beginner Contest 115 - 情報妖精の競プロ日記

AtCoder Beginner Contest 115 (ABC115) の解説です。
AtCoder Beginner Contest 115 旧版
 AtCoder Beginner Contest 115 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 115
rated 1200
12/8(土) 21:10 ～ 22:50 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - Christmas Eve Eve Eve

問題文

問題文
とある世界では、今日は $12$ 月 $D$ 日です。
$D = 25$ なら Christmas, $D = 24$ なら Christmas Eve, $D = 23$ なら Christmas Eve Eve, $D = 22$ なら Christmas Eve Eve Eve と出力するプログラムを作ってください。
制約

$22 \leq D \leq 25$

$D$ は整数である。

まず、この問題を言い換えると、次のような問題になります。

初めにChristmasと表示し、続けて $25-D$ 回だけ Eveと出力するプログラムを作ってください。

これはループで処理すれば簡単に実現できますね。

ソースコード(C++)

#include<iostream>
using namespace std;
int main() {
	int D;
	cin >> D;
	cout << "Christmas";
	while (++D <= 25) cout << " Eve"; // Dが25になるまでDを増やしながら繰り返す
	return 0;
}

B - Christmas Eve Eve

問題文

問題文
とある世界では、今日はクリスマスイブの前日です。
高羽氏は、デパートで $N$ 個の品物を買おうとしています。 $i$ 個目の品物 $(1 \leq i \leq N)$ の定価は $p_i$ 円です。
彼は割引券を持っており、 $N$ 個のうち最も定価が高い品物 $1$ 個を定価の半額で買うことができます。残りの $N-1$ 個の品物に対しては定価を支払います。支払金額は合計でいくらになるでしょうか？
制約

$2 \leq N \leq 10$

$100 \leq p_i \leq 10000$

$p_i$ は偶数である。

さて、この問題では最も高い品物1個以外は定価で買うことになります。
そこで、先に $sum=\sum_{i=1}^{N} p_i$ として、全ての品物を定価で買ったことにしましょう。
すると、問題は $N$ 個のうち最も定価が高い品物 $1$ 個を半額だけ値引きした問題になります。
これは、最も高い品物 $1$ 個の値段を記録し、最後に $sum$ から引けば求まります。

ソースコード(C++)

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int N, p, maxItem = 0, sum = 0;
	cin >> N;
	for (int i = 0;i < N;++ i) {
		cin >> p;
		sum += p;
		maxItem = max(maxItem, p); // これで、maxItemには全てのうち一番高い品物の定価が入るよ
	}
	cout << sum - maxItem / 2; // 最後に半額だけ引き算するよ
	return 0;
}

C - Christmas Eve

問題文

問題文
とある世界では、今日はクリスマスイブです。
高羽氏の庭には $N$ 本の木が植えられています。 $i$ 本目の木 $(1 \leq i \leq N)$ の高さは $h_i$ メートルです。
彼は、これらの木のうち $K$ 本を選んで電飾を施すことにしました。より美しい光景をつくるために、できるだけ近い高さの木を飾り付けたいです。
より具体的には、飾り付ける木のうち最も高いものの高さを $h_{max}$ メートル、最も低いものの高さを $h_{min}$ メートルとすると、 $h_{max} - h_{min}$ が小さいほど好ましいです。 $h_{max} - h_{min}$ は最小でいくつにすることができるでしょうか？
制約

$2 \leq K < N \leq 10^5$

$1 \leq h_i \leq 10^9$

$h_i$ は整数である。

さて、まずは $K$ 本を全部選び、そこから……とやる訳にはいかなさそうです( $N$ 本の中から $K$ 本を選ぶ選び方は $_{N}C_{N-K}=\frac{N!}{K!(N-K)!}$ 通りあり、とてもじゃないが終わらない)
そこで、何か $K$ 本の選び方に規則性を考えてみましょう。
ここで、まず何本目の木かの情報は全く使わないので、先に分かりやすいよう木の高さをソートしてしまいます。
すると、一番低い木を決め打った時、どう考えても一番高い木はその木から $K-1$ 本後の木になるので、一番低い木を決め打つと $h_{max}-h_{min}$ が自動的に決まります。
後は、一番低い木を全て試すと答えが求まります。
この計算量は ${\rm O}(N-K)$ であり、ソートの計算量も合わせると $O(N \log N - K)$ で求まりました。

ソースコード(C++)

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int N, K, h[100000], dist = 2147483647;
	cin >> N >> K;
	for (int i = 0;i < N;++ i) cin >> h[i];
	sort(h, h+N); // 先にソートするよ！
	for (int i = K - 1;i < N;dist = min(dist, h[i] - h[++i - K]));
	cout << dist;
	return 0;
}

D - Christmas

問題文

問題文
とある世界では、今日はクリスマスです。
高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル $L$ バーガー ( $L$ は $0$ 以上の整数) とは次のようなものです。

レベル $0$ バーガーとは、パティ $1$ 枚である。

レベル $L$ バーガー $(L \geq 1)$ とは、バン $1$ 枚、レベル $L-1$ バーガー、パティ $1$ 枚、レベル $L-1$ バーガー、バン $1$ 枚、をこの順に下から積み重ねたものである。

例えば、パティを P、バンを B で表すと、レベル $1$ バーガーは BPPPB (を $90$ 度回転したもの)、レベル $2$ バーガーは BBPPPBPBPPPBB といった見た目になります。
高羽氏が作るのはレベル $N$ バーガーです。ダックスフンドのルンルンは、このバーガーの下から $X$ 層を食べます (パティまたはバン $1$ 枚を $1$ 層とします)。ルンルンはパティを何枚食べるでしょうか？
制約

$1 \leq N \leq 50$

$1 \leq X \leq ($ レベル $N$ バーガーの層の総数 $)$

$N, X$ は整数である。

まず、 $X$ の制約が少々分かり辛い形で書いてあるので、先にこれの最大値を求めてしまいましょう。
$h(N)$ をレベル $N$ のバーガーの層の総数とします。 $h(0)=1$ です。
この時、 $h(N)=2h(N-1)+3$ ですから、計算すると $h(N)=2^{N+2}-3$ と分かります。
なお、こういう式に関しては手作業でやるよりWolfram Alphaなどで自動で計算させると良いです。(計算結果)
ということは、 $1 \leq X \leq 2^{52}-3$ なので、オーバーフローに気を付けて64bitの整数を使うことにしましょう。
そして、 $X$ が大きいので ${\rm O}(X)$ で求めることはできなさそうです。
もうちょっと考えてみましょう。まず、 $X=2^{N+2}-3$ とします。
この時、これはバーガーに含まれるパティの総数に等しいです。
そして、これは $P(N)$ をレベル $N$ のバーガーに含まれるパティの総数とすると、 $P(0)=1, P(N)=2P(N-1)+1$ より $P(N)=2^{N+1}-1$ と分かります。(計算結果)
次に、 $0 < X \leq 2^{N+1}-2$ の時を考えると、これはまだ半分に達してないので、最初の1層目のバンを抜けばレベル $N-1$ のバーガーを考えることに等しいです。
最後に、 $2^{N+1}-2 < X < 2^{N+2}-3$ の時を考えると、これは最初の半分のパティの数がレベル $N-1$ のバーガーに含まれるパティの総数 $P(N-1)$ であり、次の1個がパティで、残りの部分 $X-2^{N+1}+1$ がレベル $N-1$ のバーガーから $X-2^{N+1}+1$ 個の層を食べることに等しくなります。
従って、答えを $f(N, X)$ とすると、この式は
$$
f(N, X) =
\left\{
\begin{array}{}
0 & (X \leq 0) \\
f(N-1, X-1) & (0 < X \leq 2^{N+1}-2) \\
f(N-1, X-2^{N+1}+1)+2^N & (2^{N+1}-2 < X)
\end{array}
\right.
$$
と表せます。
これは、即ち1回関数を回すごとに $N$ が1ずつ減っていくので、 ${\rm O}(N)$ で計算が終わることを意味します。

ソースコード(C++)

#include<iostream>
using namespace std;
int main() {
	long long N, X, patty = 0;
	cin >> N >> X;
	for (long long i = (long long)(1 << N / 2) * (1 << (N + 3) / 2);i > 0;i /= 2, -- X) { // このiは単に2^(N+1)ね、オーバーフロー関連が面倒だったので
      	      	if (X + 1 >= i) { // 半分より多い
			patty |= i / 2; // パティの数を足す(ちなみに、2^Nの形なのでbitwise orでやっても足し算と同じ結果になる)
			X -= i - 2; // 後で--Xされることを考えて1個少なめに引く
		}
	}
	cout << patty;
	return 0;
}

結果

oooo 4完(1000点) 1:57(1WA)-4:41-7:56-49:35 / 54:35
319位

コンテスト統計

パフォーマンスの算出にはac-predictorを用いています。

スコア	0点	100点	200点	300点	400点	500点	600点	700点	1000点
時間		1:58	42:19	3:09	52:08	73:10	4:53	25:31	9:44
順位	1927位	1881位	1880位	1569位	1565位	1564位	685位	680位	1位
パフォーマンス	-945	-336	-331	326	327	327	1077	1081	1600

パフォーマンス	0	200	400	600	800	1000	1200	1400	1600
スコア	300点	300点	600点	600点	600点	600点	1000点	1000点	1000点
時間	34:53	11:23	88:46	41:10	22:14	11:21	89:27	61:35	46:10
順位	1778位	1665位	1498位	1279位	1029位	782位	555位	381位	246位

感想

今回は比較的簡単な問題ばかりだったからか、速解きコンテストの様相を呈していますね。
数学的要素も高かったため、数学が得意な人にとっては楽だったのではないでしょうか。
今回のD問題のような漸化式などが出てきた場合は、即座にWolfram Alphaに投げるなどツールを用いると他の人より優位に立てる場合があります。
せっかくなのでブックマークし、いざという時に使えるようにしておきましょう！