読者です 読者をやめる 読者になる 読者になる

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個の青色のボールが与えられる.
すべてのボールを,次の条件を満たすパッケージに詰めていく.

  • 1つのパッケージには1,2,3個のボールを入れることができる.
  • それぞれのパッケージに入っているボールはすべて同じ色か,またはすべて異なる色.

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

(方針)

まず,3個が同じ色になるようにパッケージに詰め込む.
そうすると,赤色の数は0〜2,緑色の数は0〜2,青色の数は0〜2となる.
次に,(赤色の数,緑色の数,青色の数)=(2, 0, 0) or (0, 2, 0) or (0, 0, 2)
の場合は同じ色をパッケージに詰める.
それ以外は,異なる色をパッケージに詰めていく.
f:id:tatanaideyo:20140216051209p:plain
イメージとしては,上の図のような横が1で縦がRの赤色の矩形と,
横が1で縦がGの緑色の矩形と,横が1で縦がBの青色の矩形が与えられる.
矢印は水平方向または垂直方向に長さが1から3まである.
最も少ない矢印で矩形を覆う.

[950 VocaloidsAndSongs]

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

(問題文)

3人のボカロイド,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;
}