Codeforces 145 Div1 A, B, C, D - takapt0226's diary

本番の結果

xoo--- 249位
1808 -> 1758
Aにハマったまま終了(´・ω・`)

A Cinema

解法

各映画のfavorite actorsの上限と下限を求めて、後は題意通りに実装

ソースコード

int main()
{
#ifdef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, k;
    cin >> m >> k;
    bool is_fav[128] = {};
    for (int i = 0; i < k; ++i)
    {
        int a;
        cin >> a;
        is_fav[a] = true;
    }

    int fav_lower[128] = {}, fav_upper[128] = {};
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        string s;
        int t;
        cin >> s >> t;

        int fav = 0, no = 0, free = 0;
        for (int j = 0; j < t; ++j)
        {
            int id;
            cin >> id;
            if (id == 0)
                ++free;
            else if (is_fav[id])
                ++fav;
            else
                ++no;
        }

        int rem_fav = k - fav;
        int rem_not = (m - k) - no;


        fav_lower[i] = fav + max(0, free - rem_not);
        fav_upper[i] = fav + min(free, rem_fav);
    }


    int lower = *max_element(fav_lower, fav_lower + n);
    for (int i = 0; i < n; ++i)
    {
        if (fav_upper[i] < lower)
            cout << 1 << endl;
        else
        {
            int res = 0;
            for (int j = 0; j < n; ++j)
                if (i != j && fav_lower[i] < fav_upper[j])
                    res = 2;
            cout << res << endl;
        }
    }
}

B Fence

解法

よくありそうなdp
状態空間を(どこまで塗ったか見たか, 使った赤, 使った緑, 最後に塗った色)として、その状態の最小コストを値として持てばいい
使った赤 * 使った緑 > 10^8となるが、片方の色をいくつ使ったかわかればもう片方もわかるので、使った赤の状態だけ持つ

dp[i + 1][red][iで使った色] = 最小コスト

ソースコード

int main()
{
    ifstream is("input.txt");
    ofstream os("output.txt");

    const int MAXH = 4 * 10000 + 100;
    int n, a, b, h[222];
    is >> n >> a >> b;
    for (int i = 0; i < n; ++i)
        is >> h[i];

    const int INF = 1 << 30;
    static int dp[210][2 * MAXH][2];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= a; ++j)
            for (int k = 0; k < 2; ++k)
                dp[i][j][k] = INF;

    dp[0][0][0] = dp[0][0][1] = 0;
    int sum = 0;
    int unattra;
    for (int i = 0; i < n; ++i)
    {
        for (int red = 0; red <= min(sum, a); ++red)
        {
            int green = sum - red;
            if (green <= b)
            {
                int last_red = dp[i][red][0];
                int last_green = dp[i][red][1];
                min_swap(dp[i + 1][red + h[i]][0], min(last_red, last_green + unattra));
                min_swap(dp[i + 1][red][1], min(last_red + unattra, last_green));
            }
        }

        sum += h[i];
        unattra = min(h[i], h[i + 1]);
    }

    int res = INF;
    for (int red = 0; red <= a; ++red)
    {
        int green = sum - red;
        if (0 <= green && green <= b)
            min_swap(res, min(dp[n][red][0], dp[n][red][1]));
    }
    if (res == INF)
        res = -1;
    os << res << endl;
}

C Practice

解法

1回目の練習で、選手を2つのチームAとBに分けると、それ以降の練習ではAにいた選手はBにいた選手がどのチームにいるか考慮する必要がない。Bにいた選手も逆に同様
2回目の練習は1回目の練習で分けたAとBそれぞれについて始めと同様に処理する

再帰で実装すると楽。再帰の深さが何度目の練習かに対応しており、各ノードで適当にどちらかのチームを出力用選手にする
全体での練習回数は再帰ツリー全体の高さと一致する
チームの分け方は人数が半々になるようにする。そうしないと、人数を多くとったチーム側の再帰の深さがより深くなってしまい、結果として再帰ツリー全体の高さが大きくなってしまう。

ソースコード

int m;
vector<int> left_group[1111];
void f(const vector<int>& a, int depth)
{
    if (a.size() <= 1)
    {
        max_swap(m, depth);
        return;
    }


    int mid = a.size() / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());

    for (int i = 0; i < left.size(); ++i)
        left_group[depth].push_back(left[i]);

    f(left, depth + 1);
    f(right, depth + 1);
}
int main()
{
    ifstream is("input.txt");
    ofstream os("output.txt");

    int n;
    is >> n;

    vector<int> a;
    for (int i = 1; i <= n; ++i)
        a.push_back(i);

    m = 0;
    f(a, 0);

    os << m << endl;
    for (int i = 0; i < m; ++i)
    {
        os << left_group[i].size();
        for (int j = 0; j < left_group[i].size(); ++j)
            os << " " << left_group[i][j];
        os << endl;
    }
}

D Merging Two Decks

解法

first stageの命令回数はn + mで固定なので、second stageの命令回数をどうやって少なくするか考える
second stageでは、first stageでmergeした山の上から順に同じ向きのカードの塊を作っていけばよさそう
例えば、mergeした山が001101011だとすると
11 1101011
0000 01011
11111 1011
000000 011
11111111 11
0000000000
と操作していく
この操作を見ると、同じ向きのカードが連続している区間ごとに命令する必要がある
second stageでの命令回数を減らすには、first stageで同じ向きのカードをできるだけ長く連続するようにmergeする

first stageは上記の方法に従うと、一番山の上にくるカードの向きを決めると後はgreedyに取っていける。なので、一番山の上にくるカードの向き2通りを試して、命令回数が少なくなるほうを答えとして選ぶ

ソースコード

const int MAX = 1e5 + 100;
int n, m, a[MAX], b[MAX];
typedef pair<vector<int>, vector<int> > Res; // (merged deck, operations)
Res simulate(int first)
{
    vector<int> merged;
    vector<pint> range; // (type, end)

    // first stage
    for (int i = 0, j = 0, type = first; i < n || j < m; type ^= 1)
    {
        while (i < n && a[i] == type)
            merged.push_back(i++ + 1);
        while (j < m && b[j] == type)
            merged.push_back(j++ + (n + 1));

        range.push_back(pint(type, merged.size()));
    }

    // second stage
    vector<int> ope;
    for (int i = 0; i < range.size() - 1; ++i)
        ope.push_back(range[i].second);
    if (range[range.size() - 1].first == 1)
        ope.push_back(range[range.size() - 1].second);

    return Res(merged, ope);
}
int main()
{
    fast_io();

#ifdef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n;
    input(a, n);
    cin >> m;
    input(b, m);


    Res zero = simulate(0);
    Res one = simulate(1);

    Res res = zero.second.size() < one.second.size() ? zero : one;

    print(res.first);
    cout << res.second.size() << endl;
    print(res.second);
}