2017-03-07

ICPC 国内予選 2016 D: ダルマ落とし

AOJ ICPC

昨年のだるま落とし、ちらっと解説読みながらだけど AC できた。ちょっと嬉しい。
— つたじろう (ABC-D 29/43) (@_TTJR_) March 6, 2017

昨年歯が立たなかっただけに解けてうれしい。

問題概要

原文を参照してください → Daruma Otoshi | Aizu Online Judge

解説

take[i][j] := 区間 [i, j] のブロックを全て取ることができるか となる bool 型の配列を用意します。まずはこの take 配列に対して、真偽値を正しく入れていきます。

条件より、区間の長さが $2$ であるときの判定は容易です。問題はその後でしょう。

次の $2$ つの事項を確認することによって、より長い区間についても判定できるようになります。

区間 $\left[ i, j \right]$ のブロックを全て取ることができ、かつ $i-1$ 番目と $j+1$ 番目のブロックの重さの差が $1$ 以下であれば、区間 $\left[ i-1, j+1 \right]$ のブロックを全て取ることができる
区間 $\left[ i, k \right]$ と区間 $\left[ k+1, j \right]$ について、両区間に対して全て取ることができるならば、区間 $\left[ i, j \right]$ のブロックを全て取ることができる

したがって、以下のようにすれば take 配列を正しく構築できます。

区間の長さが短い順に以下を行う
長さが $2$ であれば、重さの差が $1$ 以下であるかを判定して配列を更新する
それ以外の長さであれば、より短い区間の結果を使って配列を更新する

この配列を元に答えを出すのですが、これに答えるには以下の補題を解かなければなりません。

$\left[ 1, N \right]$ の中に、長さが $N$ 以下の区間がたくさんある。その中から、区間どうしが同じ頂点を被覆しないようにいくつかの区間を選ぶときの、被覆できる頂点数の最大値を求めよ。

これは DP で解くことができます。

dp[i][j] := 区間 [i, j] において被覆できる頂点数の最大値 となるような配列 dp を用意します。

この配列の初期化は各区間を見ることによって行います。例えば長さ $M$ の区間 $\left[ a, b \right]$ があったとします。 $\left[ a, b \right]$ において被覆できる頂点数の最大値は当然 $M$ なので、dp[a][b] = M が成り立ちます。これを全区間に対して行うことで初期化します。

あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの $2$ つめと一緒です)、 $O(N^{3})$ パワーを信じましょう。答えになるのは dp[0][N-1] です。

ソースコード

bool take[310][310];
int dp[310][310];

signed main() {
    int n;
    while(cin >> n, n) {
        int w[310];
        rep(i,0,n) cin >> w[i];
        memset(take, false, sizeof(take));
        memset(dp, 0, sizeof(dp));

        rep(i,0,n) {
            rep(j,0,n-i) {
                int len = i+1;
                int s = j, t = j+i;
                rep(k,s,t) {
                    if(take[s][k] && take[k+1][t]) take[s][t] = true;
                }
                if(len == 2) {
                    if(abs(w[s] - w[t]) < 2) {
                        take[s][t] = true;
                    }
                }
                if(take[s][t]) {
                    int x = s-1, y = t+1;
                    while(1) {
                        if(x < 0 || x >= n || y < 0 || y >= n) break;
                        if(abs(w[x] - w[y]) >= 2) break;
                        take[x][y] = true;
                        x--; y++;
                    }
                }
            }
        }

        rep(i,0,n) rep(j,i+1,n) {
            if(take[i][j]) dp[i][j] = j-i+1;
        }

        rep(i,0,n) rep(j,i,n) rep(k,i,j) {
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
        }
        cout << dp[0][n-1] << endl;
    }
    return 0;
}

当時は「DP を $2$ 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を $2$ 回やる気持ちが確かに分かる。

2017-03-06

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;
}

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

2017-02-14

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 昇格を果たしました。初めて青になれたのでうれしかったです。

Div1？わーい！すごーい！ pic.twitter.com/WGN97oGH6M
— つたじろう (ABC-D 24/43) (@_TTJR_) 2017年2月9日

2017/02/09 TopCoder SRM 708 Div.2
1173 -> 1202
初昇格。やらかすと即刻緑落ちするスリリングな世界 #tsutajmemo
— つたじろう (ABC-D 24/43) (@_TTJR_) 2017年2月9日

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

hogecoder

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

ICPC 国内予選 2016 D: ダルマ落とし

問題概要

解説

ソースコード

KUPC2012 D: 権力

問題概要

解説

ソースコード

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

問題概要

解説

ソースコード

余談