hogecoder

tsutaj 競技プログラミングの記録

KUPC2012 D: 権力

AtCoder

何でこれが詰まっちゃうかな・・・。

問題概要

原文 → D: 権力 - 京都大学プログラミングコンテスト2012 | AtCoder

M 個の区間がある。 \left[1, N \right] を被覆するには、区間はいくつ必要であるか、その最小値を答えよ。

解説

まず、地点 1 を被覆する区間があるかを調べます。もし存在するならば、その中で一番右まで被覆できるものを選びます。存在しなければ Impossible です。

次に、先ほど選んだ区間の右端 + 1 の地点を被覆する区間があるかを調べ、存在するならば一番右まで被覆できるものを選びます。

これを繰り返す貪欲法によって正答が得られ、計算量は O(NM) です。

ソースコード

signed main() {
    int n, m; cin >> n >> m;
    int a[110], b[110];
    rep(i,0,m) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    bool covered[110] = {};
    int ans = 0;
    rep(i,0,n) {
        if(covered[i]) continue;
        int r = -1;
        rep(j,0,m) {
            if(a[j] <= i && i <= b[j]) {
                r = max(r, b[j]);
            }
        }
        if(r == -1) {
            cout << "Impossible" << endl;
            return 0;
        }
        repq(j,i,r) covered[j] = true;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

どうも区間の問題が苦手らしい。

AtCoder Beginner Contest 018 D: バレンタインデー

AtCoder

バレンタインデー、みなさんいかがお過ごしでしょうか。私はいつもと変わらず競プロをやっています。というわけで今回は ABC018 D 問題です。

問題概要

原文 → D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder

女子が N 人、男子が M 人いる中から、女子 P 人、男子 Q 人からなるグループを作る。

チョコレートは R 個あり、番号が x_i である女子は番号が y_i である男子に幸福度 z_i である i 番目のチョコレートを渡すが、これは番号が x_i である女子と番号が y_i である男子が両方ともグループに含まれている時に限り渡すことができる。

渡されたチョコレートの幸福度の合計値の最大値を出力せよ。

解説

女子の組み合わせ、ならびに男子の組み合わせを総当りで考えてしまうと、組み合わせが {}_N C_P \times {}_M C_Q 通りあるため間に合わず、この問題の制約では部分点止まりになります。

満点解法では、「グループに入れる女子を固定すれば、チョコレートを貰う男子とその男子が得る幸福度がわかる」ことに着目します。グループにどの男子を入れるかについては、幸福度が大きい男子から貪欲に選択するのが最適です。いわゆる半分全列挙というやつです。したがって、次の流れで実装すればよいです。

  • グループに女子を P 人入れる各組み合わせについて以下を行う
  • チョコをもらう可能性のある男子について、幸福度を計算する
  • 幸福度が大きい順に男子を Q 人選び、その男子の幸福度の合計を計算し、その max を答えとする

この方針で解くと男子の組み合わせを列挙する必要がなくなるため、間に合います。

ソースコード

signed main() {
    int n, m, p, q, r; cin >> n >> m >> p >> q >> r;
    vector<pii> v[20];
    rep(i,0,r) {
        int x, y, z; cin >> x >> y >> z;
        x--; y--;
        v[x].pb(pii(y,z));
    }
    int ans = 0;
    rep(i,0,(1 << n)) {
        int bcnt = __builtin_popcount(i);
        if(bcnt != p) continue;
        int value[20] = {};
        rep(j,0,n) {
            if(i >> j & 1) {
                rep(k,0,v[j].size()) {
                    int to = v[j][k].fr;
                    int cost = v[j][k].sc;
                    value[to] += cost;
                }
            }
        }
        sort(value, value + m, greater<int>());
        int temp = 0;
        rep(j,0,q) temp += value[j];
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

余談

2/9 の SRM 708 で、念願の Div1 昇格を果たしました。初めて青になれたのでうれしかったです。

青底辺から上がれるようにこれからも頑張ります。

AtCoder Regular Contest 043 B: 難易度

AtCoder 動的計画法 数え上げ

ARC043 B問題、データ構造で殴ってしまったけど、明らかに想定解法より楽な方法だと思うのでいちおう紹介。

問題概要

問題原文 → B: 難易度 - AtCoder Regular Contest 043 | AtCoder

長さ N の数列が与えられる。この数列から、( i - 1 番目に取った数 ) \times 2 \leqq ( i 番目に取った数 ) となるように数字を 4 つとる。この取り方の総数を 1000000007 で割った余りを出力せよ。なお、同じ値でも違うインデックスにある数同士は区別される。

解説

まず数列をソートして、dp でできないかを考えてみます。

dp[i][j] := i 番目の数を j 番目に使う場合の数 という配列を考えると、 a_i の前に選んだ可能性のある数は 1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor を満たす全ての数であるため、遷移は以下のようになります。

dp_{i,j} = dp_{i,j} + \sum_{1 \leqq a_k \leqq \lfloor \frac{a_i}{2} \rfloor} dp_{k, j-1}

これをそのまま実装してしまうと O(N^2) のコードになってしまい TLE しますが、 \Sigma をとっている部分は a のインデックスが 0 からある数字までの区間の和ですので、この部分を BIT などのデータ構造で高速で計算すれば時間内に解くことができます。計算量は O(N \log N) です。実装では BIT を使いやすくするために配列を再利用するとよいでしょう。

ソースコード

BIT を使いやすくするために配列の再利用をしています。

// BIT 略
signed main() {
    int n; cin >> n;
    int a[100010]; rep(i,0,n) cin >> a[i];
    sort(a, a+n);
    zeroIndexedBIT<int> dp(n);
    rep(i,0,n) dp.add(i, 1);

    rep(j,0,3) {
        repr(i,n-1,0) {
            dp.add(i, -dp.sum(i,i));
            int k = upper_bound(a, a+n, a[i] / 2) - a;
            k--;
            if(k < 0) continue;
            int temp = dp.sum(0, k);
            dp.add(i, temp);
        }
    }

    int ans = dp.sum(0, n-1);
    cout << ans << endl;
    return 0;
}