SRM 557 Div2

Easy GreatFairyWar

やるだけ

int GreatFairyWar::minHP(vector <int> dps, vector <int> hp)
{
    int dame = 0;
    for (int i = 0, t = 0; i < dps.size(); ++i)
    {
        t += hp[i];
        dame += dps[i] * t;
    }
    return dame;
}

Medium IncubatorEasy

n <= 10なので2^n全探索

int IncubatorEasy::maxMagicalGirls(vector <string> love)
{
    const int n = love.size();

    bool reach[11][11] = {};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            reach[i][j] = love[i][j] == 'Y';
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                reach[i][j] |= reach[i][k] && reach[k][j];


    int max_sayaka = 0;
    for (int s = 0; s < 1 << n; ++s)
    {
        bool saya[11] = {};
        bool pro[11] = {};
        for (int i = 0; i < n; ++i)
        {
            if (s >> i & 1)
            {
                saya[i] = true;
                for (int j = 0; j < n; ++j)
                    if (reach[i][j])
                        pro[j] = true;
            }
        }

        int sayasaya = 0;
        for (int i = 0; i < n; ++i)
            if (saya[i] && !pro[i])
                ++sayasaya;
        max_swap(max_sayaka, sayasaya);
    }

    return max_sayaka;
}

Hard FoxAndMountain

Div1 Easyをやったときにカウントする問題ありそうだと思っていたらDiv2 Hardの問題だった

解けるまで

• (移動回数, 高さ, historyの位置)のdpだろうことは問題読んですぐ思いついた
• 書く → サンプル通らない
• historyの位置の遷移の考察不足
• historyが一致しなかったときに、全く一致していない状態にしていた

解法

• dp[i][j][k] = (i回移動した, 高さjにいる, historyのkまで一致している)な経路数
  • 求めたい答え: dp[n][0][m] (m = history.size())

• kの遷移を考える
  • 一致している場合はk + 1に遷移するが失敗した場合は？
    • 最も長く一致している状態に遷移

• 例えば、history = "UUDUUU"でUUDUUまで一致している(k = 5)場合
  • up: UUDUUUでk = 6に遷移
  • down: UUDUUDとなると、後ろ3つの移動はhistoryの先頭3つと一致するので、k = 3に遷移すればよい

ソースコード

const int mod = (int)1e9 + 9;
void add(int& a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
int FoxAndMountain::count(int n, string history)
{
    const int m = history.size();

    int next[55][2]; // (pos in history, U or D), automaton
    for (int i = 0; i < m; ++i)
    {
        string cur = history.substr(0, i);

        string up = cur + 'U';
        string down = cur + 'D';

        for (int j = 0; j <= i + 1; ++j)
        {
            if (history.compare(0, j, up, (i + 1) - j, j) == 0)
                next[i][0] = j;
            if (history.compare(0, j, down, (i + 1) - j, j) == 0)
                next[i][1] = j;
        }
    }
    next[m][0] = next[m][1] = m;


    int dp[55][55][55];    // (step, height, pos in history)
    CL(dp, 0);

    dp[0][0][0] = 1;
    for (int step = 0; step < n; ++step)
    {
        for (int h = 0; h <= step; ++h)
        {
            for (int i = 0; i <= m; ++i)
            {
                // up
                add(dp[step + 1][h + 1][next[i][0]], dp[step][h][i]);

                // down
                if (h > 0)
                    add(dp[step + 1][h - 1][next[i][1]], dp[step][h][i]);
            }
        }
    }

    return dp[n][0][m];
}