SRM 687 div2 Easy Med

Easy

問題概要

N個の数字の中からK個選んだとき、それらの数字の和を最小化せよ。

制約

ちいさい

解法

そーとしてK番目まで加算する。

コード

class Quorum {
  public:
    int count(vector <int> arr, int k)
    {
        sort(arr.begin(), arr.end());
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }
        return sum;
    }
};

Med

問題概要

部屋にアヒルが何羽かいる。アヒルの鳴き声は、"quack"である。
"quackquack"や"quackquackquack"なども1羽の鳴き声としてあり得る。
しかし、複数羽が部屋にいる可能性があるため、鳴き声が混ざる可能性がある。
例えば、"qquuaacckk"など。

文字列sが与えられる。この中に、最小で何羽のアヒルがいるでしょうか。
ただし、何羽アヒルがいても表現できない場合は-1。

制約

sの長さは最大2000くらい

解法

貪欲法(と言っていいのかな)。
まず、1重目のループで何匹目かを指定する。
2重目のループで、
文字列の前から、未使用かつ初めて出現する'q'を見つけ、次に初めて出現する'u'を見つけ、...、最後に初めて出現する'k'を見つける。
次に'k'の後に存在する初めて出現する'q'を見つけ、... という操作を繰り返す。

例) Sample
quqaquuacakcqckkuaquckqauckack の場合
1匹目で、quqaquuacakcqckkuaquckqauckack
2匹目で、quqaquuacakcqckkuaquckqauckack
3匹目で、quqaquuacakcqckkuaquckqauckack
となり、合計3匹となる。

アンダースコアのものがそのアヒルが鳴いたもの。ボールド体のものが既に他のアヒルが鳴いたもの。

もし、2重目のループでcで終わったり、何匹やっても使わない文字が出現した場合に-1となる。

コード

#define MAX 3000

class Quacking {
  public:    
    int quack(string s)
    {
        int N = s.size();        
        const int q[] = {'q', 'u', 'a', 'c', 'k'};
        bool used[MAX] = {0};
        for (int i = 0; i < MAX; i++) {
            int idx = 0;
            for (int j = 0; j < N; j++) {
                if (!used[j] && s[j] == q[idx]) {
                    used[j] = 1;
                    idx++;
                }
                idx %= 5;
            }
            if (idx != 0) {
                return -1;
            }
            bool finished = 1;
            for (int j = 0; j < N; j++) {
                if (!used[j]) {
                    finished = 0;
                    break;
                }
            }
            if (finished) {
                return i+1;
            }
        }
        return -1;
    }
};