SRM 714

Easy:Range Encoding

問題概要

単調増加の配列がarrが与えられる. 配列の中で連続した部分(arr[i] + 1 = arr[i + 1]) があるとき,その部分を [a, b]として置き換えることができる. 例えば,{3,4,5,6} であれば [3, 6] と置き換えることができる.

arr配列に対してこのような操作をしたときに最小で何個置き換えるとarr配列をすべて置き換えることができるか.

解法

arr[i] + 1 != arr[i + 1]であれば,カウントをしていけば良い ただし,一番最後のカウントし忘れに注意すること.

#include <iostream>
#include <algorithm>
#include <vector>

class RangeEncoding{
    public:
    int minRanges(std::vector<int> arr){
        std::sort(arr.begin(), arr.end());
        int ans = 0;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i] + 1 != arr[i + 1]) {
                ans++;
            }
        }
        return ans + 1;
    }
};

Meddium:Removing Parenthesis

正しい括弧の対応が取れた文字列Sが与えられる. Sの一番左の括弧'(‘と右の括弧(場所はどこでも良い)を削除する. ただし,正しい括弧の対応が取れてない文字列となる場合はその右括弧の削除は無効とする. この操作を繰り返していき空文字列となるまで続ける.

この時,空文字列になるような括弧の削除の仕方は何通りあるか.

解法

文字列の長さが最長で20文字なので全探索をしても間に合うが,動的計画法を用いるとより早く計算を行うことができる.

#include <iostream>
#include <algorithm>
#include <string>
#include <map>

class RemovingParenthesis {
public:
    std::map<std::string, int> m;

    int rec(std::string s) {
        if(s[0] ==')'){
            return 0;
        }
        if (m[s] > 0) {
            return m[s];
        }
        std::cout << s << std::endl;
        int ret = 0;
        if(s[1] == ')') {
            ret = rec(s.substr(2));
        }else{
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')') {
                ret += rec(s.substr(1, i - 1) + s.substr(i + 1));
            }
        }
        }
        m[s] = ret;
        return ret;
    }

    int countWays(std::string s) {
        m[""] = 1;
        m["()"] = 1;
        m["(())"] = 2;
        m["((()))"] = 6;
        m["(((())))"] = 24;
        m["((((()))))"] = 120;
        m["(((((())))))"] = 720;
        m["((((((()))))))"] = 5040;
        m["(((((((())))))))"] = 40320;
        m["((((((((()))))))))"] = 362880;
        m["(((((((((())))))))))"] = 3628800;
        
        return rec(s);
    }
};