【AtCoder】ABC 351 C - Merge the balls | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 228

問題概要

個目の大きさが である 個のボールと空の列がある。以下の操作を 回繰り返した後の、列に残っているボールの数を出力せよ。

• 回目の操作 :

1. 個目のボールを列の一番右に付け加える。
2. 列にあるボールが1つ以下ならばこの操作を終了する。
3. 列にあるボールのうち右から1番目と2番目の大きさが異なるならば操作を終了する。
4. 列にあるボールのうち右から1番目と2番目の大きさが等しいならば、2つのボールを取り除き、「取り除かれた2つのボールの大きさの和」の大きさのボール1つを列の一番右に付け加える。その後、手順2に戻り以降の手順を繰り返す。

制約

• 入力はすべて整数。
• 
• 

考察

まず、 であることから、ボールの大きさを2を底とする対数で管理し、手順4で付け加えるボールの大きさは元の大きさに1を足したものとすればよい。

また、列の状態を管理するデータ構造として、ここではstack (変数名はst) を用いた。が、データの追加・削除を定数時間 で行えればよいので、素直にvectorを使ってもOK。

あとは手順通りにシュミレーションをしていく。手順2~4については再帰関数を用いて実装したので、以下ではその説明をする。

• 手順1で付け加えるボールの大きさをnextとしてf(st, next)を呼び出す。
• stが空 (手順2に相当) あるいはstの先頭要素がnextと異なる (手順3に相当) ならば、そのままnextをstに追加して終了。
• そうでない場合について。一度stの先頭要素をtempとして取り出しておき、nextをtemp + 1として (ボールをくっつける操作) 、再度f(st, next)を呼び出す。

こうすることで、ボールが連続でくっつけられる場合に対応することができる。最初にA[0]をpushしておくのを忘れないこと。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

void f(stack<int> &st, int next)
{
    if (!st.empty() && st.top() == next)
    {
        int temp = st.top();
        st.pop();
        f(st, temp + 1);
    }
    else
    {
        st.push(next);
    }
}

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    stack<int> st;
    st.push(A[0]);
    rep(i, 1, N)
    {
        f(st, A[i]);
    }

    cout << st.size() << endl;
}

atcoder.jp

実装時間: 20分