SRM609 Div2

Rating 778 -> 699

反省点

• なんとなくで解いてはダメ
• なんとなくでチャレンジしてはダメ

[250 MagicalStringDiv2]

通した．

(問題文)

文字'>'と'<'からなる偶数長の文字列Sが与えられる．
Sを「magical strings」にするには最小で何文字変更しなければいけないか．
「magical strings」とは，ある整数kが存在して，
k個の連続する文字'>'とそれに続くk個の連続する文字'<'からなる文字列のこと．

(方針)

Sの文字列長をnとする．
文字列Sが「magical strings」ならば先頭からn / 2文字は'>'になっており，
n / 2 + 1文字目からn / 2文字は'<'になっている．
なので，そうなっていない文字数を先頭からカウントすれば，それが求める答え．

[500 PackingBallsDiv2]

撃墜された．
テストケース(1, 1, 2)の時，答えは{(1, 1, 1), (0, 1, 1)}で2だが，
自分のコードでは{(0, 2, 0), (0, 0, 2), (1, 0, 0)}で3としていた．
場合分けを適当にしてしまった．
3x3x3通りの場合分けだったので，すべて書き下してみるべきだった．

(問題文)

R個の赤色のボール，G個の緑色のボール，B個の青色のボールが与えられる．
すべてのボールを，次の条件を満たすパッケージに詰めていく．

• １つのパッケージには１，２，３個のボールを入れることができる．
• それぞれのパッケージに入っているボールはすべて同じ色か，またはすべて異なる色．

求めるのは上の条件を満たしてすべてのボールをパッケージに詰めた時の，
最小のパッケージ数．

(方針)

まず，３個が同じ色になるようにパッケージに詰め込む．
そうすると，赤色の数は0〜2，緑色の数は0〜2，青色の数は0〜2となる．
次に，(赤色の数，緑色の数，青色の数)=(2, 0, 0) or (0, 2, 0) or (0, 0, 2)
の場合は同じ色をパッケージに詰める．
それ以外は，異なる色をパッケージに詰めていく．

イメージとしては，上の図のような横が1で縦がRの赤色の矩形と，
横が1で縦がGの緑色の矩形と，横が1で縦がBの青色の矩形が与えられる．
矢印は水平方向または垂直方向に長さが1から3まである．
最も少ない矢印で矩形を覆う．

[950 VocaloidsAndSongs]

解けなかった．問題文が理解できなかった．

(問題文)

３人のボカロイド，Gumi, Ia, Mayuがいる．
S曲入っているアルバムを制作する．
Gumiはgumi曲，Iaはia曲，Mayuはmayu曲歌う．
それぞれの曲では，最低1人歌う．
なので，ある曲では2人，または3人で歌う場合がある．
アレンジの方法はどれぐらいあるか．

(方針)

メモ化再帰．(50 * 50 * 50 * 50 = 6.25x10^6)
i番目の歌を歌うボカロイドを決めるときの，場合の数は次の7通り．
1. Gumi, Ia, Mayu
2. Gumi, Ia, x
3. Gumi, x, Mayu
4. Gumi, x, x
5. x, Ia, Mayu
6. x, Ia, x
7. x, x, Mayu

res += (memo % MOD)とやるとオーバーフローするからダメ．

ソースコード

[250 MagicalStringDiv2]

#include <iostream>
#include <vector>

using namespace std;

class MagicalStringDiv2 {
public:
    int minimalMoves(string S) {
		int ans = 0;

        for (int i = 0; i < S.size() / 2; ++i)
            if (S[i] == '<')
                ans++;
        for (int i = S.size() / 2; i < S.size(); ++i)
            if (S[i] == '>')
                ans++;

        return ans;
    }
};

[500 PackingBallsDiv2]

#include <iostream>
#include <vector>

using namespace std;

class PackingBallsDiv2 {
public:
    int minPacks(int R, int G, int B) {
        int ans = 0;

        ans += R / 3;
        R = R % 3;
        ans += G / 3;
        G = G % 3;
        ans += B / 3;
        B = B % 3;

        if ((R > 0 && G == 0 && B == 0) ||
            (R == 0 && G > 0 && B == 0) ||
            (R == 0 && G == 0 && B > 0)) {
            R -= 2, G -= 2, B -= 2;
            ans++;
        }

        while (R > 0 || G > 0 || B > 0) {
            R--, G--, B--;
            ans++;
        }

        return ans;
    }
};

[950 VocaloidsAndSongs]

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

class VocaloidsAndSongs {
    const long long MOD = 1000000007;
    long long Rec(int song, int gumi, int ia, int mayu);
    long long memo[55][55][55][55];
public:
    int count(int S, int gumi, int ia, int mayu) {
        memset(memo, -1, sizeof(memo));

        return Rec(S, gumi, ia, mayu);
    }
};

long long VocaloidsAndSongs::Rec(int song, int gumi, int ia, int mayu)
{
    if (song == 0 && gumi == 0 && ia == 0 && mayu == 0)
        return 1;
    if (song < 0 || gumi < 0 || ia < 0 || mayu < 0)
        return 0;

    if (memo[song][gumi][ia][mayu] != -1)
        return memo[song][gumi][ia][mayu];

    long long res = 0;
    res = (res + Rec(song - 1, gumi - 1, ia - 1, mayu - 1)) % MOD;
    res = (res + Rec(song - 1, gumi - 1, ia - 1, mayu)) % MOD;
    res = (res + Rec(song - 1, gumi - 1, ia, mayu - 1)) % MOD;
    res = (res + Rec(song - 1, gumi - 1, ia, mayu)) % MOD;
    res = (res + Rec(song - 1, gumi, ia - 1, mayu - 1)) % MOD;
    res = (res + Rec(song - 1, gumi, ia - 1, mayu)) % MOD;
    res = (res + Rec(song - 1, gumi, ia, mayu - 1)) % MOD;

    return memo[song][gumi][ia][mayu] = res;
}