SRM 611 Div2

競プロ

反省点

Rating 699 -> 731

  • 250の問題文を理解するのに時間がかかった．

[250 InterestingNumber]

通った．問題文を理解するのと実装に手間取った．

(問題文)

それぞれの文字が'0'-'9'である文字列xが与えられる．
各文字の出現回数が0回または2回であり，
かつ，すべての2つの文字Dの間にDとは異なる文字がD文字あれば文字列xは"Interesting"である．
それ以外の文字列は"Not interesting"である．

(方針)

はじめに，各文字の出現回数を調べる．
各文字の出現回数が0回または2回でないならば"Not interesting"を返して終了．
次に，2つの文字Dの間にDとは異なる文字がD文字あるかをフラグを使ってチェック．
すべての条件を満たしていれば"Interesting"を返す．

[500 LCMSetEasy]

システムテストで落ちた．

(問題文)

整数の集合Sと整数xが与えられる．
集合Sのいくつかの要素で最小公倍数がxとなる部分集合が存在するかを判定する．

(方針)

Wikiの最小公倍数でxを素因数分解して・・・のところを意味を履き違えて間違えた．
最小公倍数 - Wikipedia
wikiの定義を逆からたどっていく．
実直にやると一番下のソースコードになる．
ごちゃごちゃやると次のスースコードのような実装になる．

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class LCMSetEasy {
public:
    string include(vector <int> S, int x) {
        int l = 1, n = S.size();

        for (int i = 0; i < n; ++i)
            if (x % S[i] == 0)
                l = l / __gcd(l, S[i]) * S[i];

        return (x == l) ? "Possible" : "Impossible";
    }
};

[1000 ElephantDrinkingEasy]

通せなかった．
実装は間に合っていたけど，添字のミスをしていた．

(問題文)

省略．

(方針)

nが5以下なので2^4*nの全探索をしても間に合う．
すべての正方形の周辺から辺に垂直に水溜りを探索して，
最初に見つかった水溜りを，その位置のゾウが飲むか飲まないかで場合分け．
f:id:tatanaideyo:20140305000910p:plain

ソースコード

[250 InterestingNumber]

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

class InterestingNumber {
public:
    string isInteresting(string x) {
        int time[10] = {0};

        const int n = x.size();
        for (int i = 0; i < n; ++i)
            ++time[(int)(x[i] - '0')];

        for (int i = 0; i < 10; ++i)
            if (time[i] != 0 && time[i] != 2)
                return "Not interesting";

        bool flag[n];
        for (int i = 0; i < n; ++i) {
            if (flag[i])
                continue;

            flag[i] = true;
            int d = (int)(x[i] - '0');
            for (int j = 1; i + j < n && j <= d; ++j)
                if (x[i + j] == x[i])
                    return "Not interesting";
            if (i + d + 1 < n && x[i] == x[i + d + 1])
                flag[i + d + 1] = true;
            else
                return "Not interesting";
        }

        for (int i = 0; i < n; ++i)
            if (flag[i] == false)
                return "Not interesting";

        return "Interesting";
    }
};

[500 LCMSetEasy]

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

class LCMSetEasy {
    map<int, int> PrimeFactor(int n);
public:
    string include(vector <int> S, int x) {
        map<int, int> xp = PrimeFactor(x), res;

        const int n = S.size();
        for (int i = 0; i < n; ++i) {
            if (x % S[i] != 0)
                continue;

            map<int, int> tmp = PrimeFactor(S[i]);

            auto it = tmp.begin();
            while (it != tmp.end()) {
                if (xp[(*it).first] < (*it).second)
                    return "Impossible";

                if (res.find((*it).first) == res.end())
                    res[(*it).first] = (*it).second;
                else
                    res[(*it).first] = max(res[(*it).first], (*it).second);

                ++it;
            }
        }

        auto it = res.begin();
        int ans = 1;
        while (it != res.end()) {
            ans *= pow((*it).first, (*it).second);
            ++it;
        }


        if (ans == x)
            return "Possible";
        else
            return "Impossible";
    }
};

// nの素因数分解
map<int, int> LCMSetEasy::PrimeFactor(int n)
{
    map<int, int> res;

    for (int i = 2; i * i <= n; ++i)
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }

    if (n != 1)
        res[n] = 1;

    return res;
}

[1000 ElephantDrinkingEasy]

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

class ElephantDrinkingEasy {
    int n, ans;
    void Rec(int idx, vector<string> &map, int cnt);
public:
    int maxElephants(vector <string> map) {
        n = map.size();
        ans = 0;
        Rec(0, map, 0);

        return ans;
    }
};

void ElephantDrinkingEasy::Rec(int idx, vector<string> &map, int cnt)
{
    if (idx == 4 * n) {
        ans = max(ans, cnt);
        return ;
    }

    Rec(idx + 1, map, cnt);

    if (idx < n) {
        for (int i = 0; i < n; ++i) {
            if (map[i][idx] == 'S')
                return ;
            else if (map[i][idx] == 'Y') {
                for (int j = 0; j <= i; ++j)
                    map[j][idx] = 'S';
                Rec(idx + 1, map, cnt + 1);
                for (int j = 0; j < i; ++j)
                    map[j][idx] = 'N';
                map[i][idx] = 'Y';
                return ;
            }
        }
    }
    else if (idx < 2 * n) {
        int x = idx - n;
        for (int i = n - 1; i >= 0; --i) {
            if (map[x][i] == 'S')
                return ;
            else if (map[x][i] == 'Y') {
                for (int j = n - 1; j >= i; --j)
                    map[x][j] = 'S';
                Rec(idx + 1, map, cnt + 1);
                for (int j = n - 1; j > i; --j)
                    map[x][j] = 'N';
                map[x][i] = 'Y';
                return ;
            }
        }
    }
    else if (idx < 3 * n) {
        int x = idx - 2 * n;
        for (int i = n - 1; i >= 0; --i) {
            if (map[i][x] == 'S')
                return ;
            else if (map[i][x] == 'Y') {
                for (int j = n - 1; j >= i; --j)
                    map[j][x] = 'S';
                Rec(idx + 1, map, cnt + 1);
                for (int j = n - 1; j > i; --j)
                    map[j][x] = 'N';
                map[i][x] = 'Y';
                return ;
            }
        }

    }
    else {
        int x = idx - 3 * n;
        for (int i = 0; i < n; ++i) {
            if (map[x][i] == 'S')
                return ;
            else if (map[x][i] == 'Y') {
                for (int j = 0; j <= i; ++j)
                    map[x][i] = 'S';
                Rec(idx + 1, map, cnt + 1);
                for (int j = 0; j < i; ++j)
                    map[x][i] = 'N';
                map[x][i] = 'Y';
                return ;
            }
        }
    }
}