Mister雑記

競プロやります。

ABC115 解説 (未完)

2週間早いクリスマスコンテスト。

beta.atcoder.jp

A. Christmas Eve Eve Eve (100)

beta.atcoder.jp

概要

今日の日付( 12 D日)が与えられる。

Christmasに続けて、今日からクリスマス( 12 25日)までの日数分だけEveをスペース区切りで出力せよ。

制約

  •  22 \leq D \leq 25

解説

まずはChristmasを出力、その後 D - 25回だけfor文なりでEveを出力すればいい。while文で D 25になるまでインクリメントするのもよい。

Christmasは手で打つとタイプミスしやすい。これでWAを食らうと目も当てられないので、安全をとって問題文からコピペするといいだろう。

実装例

#include <iostream>
using namespace std;

int main() {
    int D;
    cin >> D;

    cout << "Christmas";

    for (int i = 0; i < D - 25; ++i) {
        cout << " Eve";
        // Eveの前にスペースが入っていることに注意
    }

    cout << endl;
    return 0;
}

ちなみにABCのA問題はforやwhileといったループ構文を使わなくても解けるようになっているらしい。今回の場合、各 Dの値に応じて埋め込みをするのも立派な解法である。

B. Christmas Eve Eve (200)

beta.atcoder.jp

概要

高橋くんはデパートで N個の商品を買おうとしている。 i個目の商品の値段は p_i円である。

高橋くんは割引券を1枚持っており、最も値段の高い商品を半額で買うことができる。このとき高橋くんが支払う金額を求めよ。

制約

  •  2 \leq N \leq 10
  •  100 \leq p_i \leq 10,000
  •  p_iは偶数

解説

問題文通りに実装しようとすると、以下のようになる。

  1. 長さ Nの配列 \{p_i\}を用意し、標準入力を受け取る。
  2. ソートする。
  3. 一番値段の高いやつを 2で割る。
  4. 配列の総和を求め、出力する。

あるいは少し工夫をすると、以下のようにもできる。

  1.  p_iの総和と最大値を持つ変数を用意する。
  2. 標準入力から p_iを受け取り、総和に加えながら最大値を更新していく。
  3. 得られた総和から、最大値の半分を引いたものを出力する。

まぁどっちが悪いというものでもないと思う。前者はバグらせにくい一方、後者は計算量が時間、空間ともに少ない。

実装例

今回は私が本番で実装した後者の実装例を上げる。

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;

    int sum = 0, pmax = 0;
    for (int i = 0; i < N; ++i) {
        int p;
        cin >> p;
        sum += p;
        pmax = max(pmax, p);
    }

    cout << sum - pmax / 2 << endl;
    return 0;
}

C. Christmas Eve (300)

beta.atcoder.jp

概要

高羽氏の庭には N本の木が植えられている。 i本目の高さは h_iである。 高羽氏はこれらの木のうち K本を選んでクリスマスツリーにしたい。

ここでクリスマスツリーの「美しさ」は、選んだ木の高さの最大値と最小値の差となる。 クリスマスツリーの「美しさ」の最小値を求めよ。

制約

  •  2 \leq K \lt N \leq 10^5
  •  1 \leq h_i \leq 10^9

解説

数列 \{h_i\}の並び順はどうでもいいので、例によってソート済みとする。

 \{h_i\}からどんなふうに K個選ぶと、「最大値と最小値の差」を小さくできるか?これは直感的にも「連続した K個を選ぶ」のが最適だと分かるだろうか。

証明

これを簡単に証明すると以下の通り。

連続していない K個を選んだとしよう。このとき一番小さい要素が i個目、大きい要素が j個目だったとする。  K個が連続していないことから、 i \lt k \lt j k個目が選ばれていないようなものが存在する。このとき i個目を捨てて代わりに k個目を選んだとする。 すると木の高さの最小値は変わらないか大きくなる一方で、最大値は変わらない。よってこれがより良い選び方となる。  \square

こんな具合に「理想的な状態でなければより良い状態が存在する」というのは、主に貪欲法の証明でよく使われる手法である。

それと本番でここまでの証明を書きつける必要はない。頭の中に大枠が描ければ十分である。


あとは連続する K個の選び方を全パターン試せばいい。具体的には、 i 1から N - K + 1まで回して h_{i + K - 1} - h_iの最小値を更新していけばいい。

実装例

上は1-indexedなのに対し、以下の実装例は0-indexedなので若干ズレがある。

#include <algorithm>
#include <iostream>

using namespace std;

const int INF = 1 << 30;
// INF >= 10^9 - 1

int main() {
    int N, K;
    cin >> N >> K;

    int h[N];
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }
    sort(h, h + N);

    int ans = INF;
    for (int i = 0; i + K - 1 < N; ++i) {
        ans = min(ans, h[i + K - 1] - h[i]);
    }

    cout << ans << endl;
    return 0;
}

ansの初期値に注意。解の最大値は 10^9 - 1なので、これ以上でなくてはならない。かといって余り大きくしすぎるとintではオーバーフローを起こす。無難にlong longを使うのも手。

D. Christmas (400)

beta.atcoder.jp

概要

TBU...

解説

TBU...

実装例

多分解説を書くのに相当時間がかかるので、先に実装例だけ載せておく。

long longにしないとオーバーフローを起こすので要注意(5分ロス)。

#include <iostream>
using namespace std;
using ll = long long;


ll l[51], p[51];
// l[i] = レベルiのハンバーガーの層数
// p[i] = レベルiのハンバーガーに含まれるパティの数


// レベルNのハンバーガーの、下からX層にパティは何枚入っているか?
ll rec(int N, ll X) {
    if (X <= 0) return 0;

    // レベルNのハンバーガーを丸々食べるケース
    // これで計算量が落ちる
    if (X >= l[N]) return p[N];

    ll ret = 0;

    // 下にあるレベルN-1のハンバーガーの分
    ret += rec(N - 1, X - 1);

    // 真ん中のパティの分
    if (X > l[N - 1] + 1) ++ret;

    // 上にあるレベルN-1のハンバーガーの分
    ret += rec(N - 1, X - l[N - 1] - 2);

    return ret;
}


int main() {
    // l, pを埋める
    l[0] = 1, p[0] = 1;
    for (int i = 1; i <= 50; ++i) {
        l[i] = l[i - 1] * 2 + 3;
        p[i] = p[i - 1] * 2 + 1;
    }

    ll N, X;
    cin >> N >> X;

    cout << rec(N, X) << endl;
    return 0;
}

感想

  • DはABC onlyにしては難しめかなという印象。
  • それでもDの実装に時間掛けすぎた(15分強)。
  • ちなみに結果は22:49で49位。