Mister雑記

競プロやります。

ABC116 解説

atcoder.jp

地味に実装が辛かった回。

A. Right Triangle (100)

atcoder.jp

概要

 \angle ABC = 90^{\circ}である直角三角形 ABCの3辺の長さ |AB|, |BC|, |CA|が与えられる。この直角三角形の面積を求めよ。

制約

  •  1 \leq |AB|, |BC|, |CA| \leq 100
  • 入力は全て整数。
  • 面積は整数であることが保障されている。

解説

 \angle ABC = 90^{\circ}であることから、直角三角形の面積は \dfrac{1}{2} |AB| |BC|で求まる。これを出力すればよい。

ちなみに私は本番中 \angle ABC = 90^{\circ}を読み飛ばし、わざわざソートして小さい2辺を求めていた。問題文はちゃんと読もう。

実装例

#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a * b / 2 << endl;
    return 0;
}

上では |CA|の入力を受け取っていないが、要らない入力は別にわざわざ受け取らなくてもよい。まぁ入力を無視して得することもそこまでないのでお好みで。

B. Collatz Problem (200)

atcoder.jp

概要

関数 g(x)を、

  •  xが奇数なら g(x) = 3x + 1
  •  xが偶数なら g(x) = \dfrac{x}{2}

と定める。

この gと整数 sによって、数列 \{a_i\}

  •  a_1 = s
  •  a_{i + 1} = g(a_i)

として構築する。このとき a_m = a_n  (m \gt n)なる nが存在するような最小の mを求めよ。

制約

  •  1 \leq s \leq 100
  •  \{ a_i \}の各要素、および解は 10^6以下となることが保障される。

解説

そのまま解くならば「set a_iを入れていって、過去に同じものが出ていたらその添字を出力」となるだろう。

一方で \{ a_i \}がCollatz数列であることから、入力程度の範囲では 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \cdots以外のループが現れないことが知られている。つまり「 1, 2, 4のいずれかが出てきたら、添字に 3 (1ループ分)を加えて出力」としてもACとなる。

実装

ここでは後者の実装を載せることにする。

#include <iostream>

using namespace std;

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

    int index = 1;
    while (s > 4 || s == 3) {  // !(s == 1 || s == 2 || s == 4) と同値
        s = (s % 2 == 0 ? s / 2 : s * 3 + 1);
        ++index;
    }

    cout << index + 3 << endl;
    return 0;
}

C. Grand Garden (300)

atcoder.jp

概要

花壇に N本の花が植えられており、最初全ての花の高さは 0である。

あなたはこの花壇に対し、以下の操作「水やり」を行うことができる。

  • 整数 l, r ( 1 \leq l \leq r \leq N)を指定する。
  •  l \leq x \leq rなる全ての xに対し、花 xの高さを 1増やす。

あなたは各 1 \leq i \leq Nについて、花 iの高さが h_iになるようにしたい。これに必要な水やりの最小回数を求めよ。

制約

  •  1 \leq N \leq 100
  •  0 \leq h_i \leq 100

解説

解説の便宜上、「花の高さを h_iから 0に減らす」として考えることにする。

できるだけ効率的に花の高さを減らすためには、やはり区間 [l, r]は毎回できるだけ広くとっておきたい。 h_x = 0なる xが含まれるような区間を取ることはできないため、貪欲に「 0によって分割された区間に対して水やりを行う」とすれば上手くいきそうである。実際これが最適な戦略である。

実装例

ただ、本問は考察よりも実装が難しい。以下では「左端の花から順に 0にしていく」という方針で実装したものである。多分キレイにまとまっている方だと思う。

#include <iostream>

using namespace std;

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

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

    int ans = 0;
    // l : h[i] > 0なる最小のi
    for (int l = 0; l < N; ++l) {
        while (h[l] > 0) {
            int r;
            for (r = l + 1; r < N; ++r) {
                if (h[r] == 0) break;
            }
            // 区間[l, r)は全て正
            // この区間に対して水やりをする
            for (int x = l; x < r; ++x) --h[x];
            ++ans;
        }
    }

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

ちなみに本番では「区間を分割して再帰的に水やりをする」という方針をとっていたが、まぁ盛大にバグった。上の方で実装しておけば良かったと今更ながら思う。

D. Various Sushi (400)

atcoder.jp

概要

 N個の寿司がある。 i個目の種類は t_iで、美味しさは d_iである。

あなたはこの寿司から K個を選んで食べる。このとき、全体の美味しさは以下の2つの値の和で表される。

  • 選んだ寿司の d_iの総和。
  •  x種類の寿司を選んだとき、 x^2

全体の美味しさの最大値を求めよ。

制約

  •  1 \leq K \leq N \leq 10^5
  •  1 \leq t_i \leq N
  •  1 \leq d_i \leq 10^9

解説

最初「先頭 i個までを見てDPかな〜」とか思ったが、それだと選んだ寿司の集合を保持する必要があるので即却下。

次に浮かんだのが「寿司の種類数 xを固定する」という方針。以降はこの方針で進むことになる。

まず種類数 xを実現するにはどうすればいいかというと、当然「 x種類の寿司を少なくとも1個ずつ食べる」ことが必須となる。そしてこれが満たされていれば、残りをどう選ぼうと種類数は xを下回ることはない。よって残りは貪欲に選んでいい。

では種類 tを食べることにしたとしよう。このとき種類 tで「少なくとも1個食べる」寿司はどれがいいか?これは種類 tで最も美味しい寿司である。なぜなら美味しくない寿司を選んでもメリットが何一つないからだ。

ここから、 x種類の選び方は「『一番美味しい寿司』が美味しい方から貪欲に選ぶ」のが最適となる。

以上から、 x種類選ぶときの最善策は以下のような貪欲法となる。

  • 寿司を「その種類で一番美味しいもの」と「その他」に分ける。
  • 前者から、美味しい順に x個食べる。 ( x種類の確保)
  • 後者から、美味しい順に K - x個食べる。

ここで「この方法だと x種類を超えるケースがあるのでは?」という疑問が浮かぶが、これは問題ない。というのも、その場合は「 x種類が最適解でない」というだけで、より多い種類を選んだ場合に上書きされるからだ。

ちなみに毎回頭から x個を足しているとおそらくTLEになる。よってそれぞれの累積和を予め計算しておく必要がある。

実装例

見ての通り、実装は結構重い部類に入る。priority_queueはソートが面倒だから使っているだけで、別にvectorをソートしても何ら問題はない。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
using ll = long long;

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

    priority_queue<ll> kind[N];
    for (int i = 0; i < N; ++i) {
        int t;
        ll d;
        cin >> t >> d;
        kind[t - 1].push(d);
    }

    priority_queue<ll> best, remain;
    // best: 各種類で一番美味しいやつを集めたもの
    // remain : bestの余り
    for (int i = 0; i < N; ++i) {
        if (!kind[i].empty()) {
            best.push(kind[i].top());
            kind[i].pop();

            while (!kind[i].empty()) {
                remain.push(kind[i].top());
                kind[i].pop();
            }
        }
    }

    vector<ll> bsum = {0};
    // bestの累積和 (bsum[i] = bestの先頭からi個の総和)
    while (!best.empty()) {
        bsum.push_back(bsum.back() + best.top());
        best.pop();
    }

    vector<ll> rsum = {0};
    // remainの累積和
    while (!remain.empty()) {
        rsum.push_back(rsum.back() + remain.top());
        remain.pop();
    }

    ll ans = 0;
    for (ll x = 1; x <= K; ++x) {
        // 種類が多すぎるケース
        if (x >= bsum.size()) break;

        // 種類が少なすぎて、余り物が足りないケース
        if (K - x >= rsum.size()) continue;

        // bestからx個、remainからK-x個貪欲に選ぶ
        ans = max(ans, bsum[x] + rsum[K - x] + x * x);
    }

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

感想

  • ABC onlyにしては全体的にハイレベルだったと思われる。
  • ちなみに41分全完で31位だった。
    • ここからも難易度の高さが伺われる。

f:id:misteer:20190121000614p:plain