2020-03-16

AtCoder Petrozavodsk Contest 001 A - Two Integers (灰色, 100 点)

AtCoder AtCoder100点数学(整数問題) 場合分け推移性に着目する必要条件を列挙したら十分条件になる灰色diff AGC-like

発想一発

問題へのリンク

問題概要

二つの整数 $X, Y$ が与えられる。 $X$ の倍数であって $Y$ の倍数でないものが存在すれば、それを一つ出力し、存在しなければ -1 を出力せよ。

考えたこと

$X$ の倍数とは、 $X, 2X, 3X, \dots$ であるが、余計なリスクを回避したければ普通に $X$ を選んでおきたい (他を選んでも $Y$ で割り切れる可能性が増すだけ)。

$X$ が $Y$ の倍数になっているようでは、もうダメ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long X, Y; cin >> X >> Y;
    if (X % Y == 0) cout << -1 << endl;
    else cout << X << endl;
}

2020-03-16

AtCoder Petrozavodsk Contest 001 D - Forest (青色, 600 点)

AtCoder AtCoder600点グラフコーナーケース連結成分 Greedy 最小コスト Yes/No判定問題必要条件を列挙したら十分条件になる N個からK個を選ぶ設定の問題 DFS 青色diff AGC-like 連結成分ごとに分解して考える Greedy:条件を満たすまで大きい順に取っていく最適化問題

面白かった

問題へのリンク

問題概要

$N$ 頂点 $M$ 辺の森が与えられる。各頂点 $v$ には、値 $a_{v}$ が付いている。これにいくつかの辺を追加して、連結にしたい。

頂点 $i$ と頂点 $j$ とを結ぶのに必要なコストは $a_{i} + a_{j}$ である
すでに辺がある二頂点間は結べない
一度辺を張るのに使用した頂点は、他の頂点と結ぶことはできない

連結するための最小コストを求めよ。不可能な場合は "Impossible" と出力せよ。

制約

$1 \le N \le 10^{5}$

考えたこと

こういうのはいかにも Wrong Answer を出しそうで怖い。慎重にちゃんと証明しながらやりたい...

まず、可能な条件を考えたい。森の各連結成分のサイズを $c_{1}, \dots, c_{K}$ とする。 $c_{1} + \dots + c_{K} = N$ という制約はあるものの、ある程度自由な値をとれるものである。

極端な話、 $c$ がすべて 0 の場合はダメ。もう少し具体的には、

$c$ の総和 < $2(K-1)$

のときはダメ。なぜなら、辺を $K-1$ 本張る必要があるため。そして逆に、 $c$ の総和が $2(K-1)$ 以上のときは連結にすることが可能である！！！

具体的には、合計 $2(K-1)$ 個の頂点を、どの連結成分からも最低 1 個ずつは選ばれるように選んであげて、それらを適切にペアリングしてあげればよい。

具体的な最小コストは、

各連結成分から、まずは 1 個ずつ「コスト最小の頂点」を選ぶ
その後は残りの頂点からコストが小さい順に、 $K-2$ 個選ぶ

とすれば OK。注意点として、 $K = 1$ の場合は例外で、はじめから 0 を出力しておく。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
using Graph = vector<vector<int>>;
int N, M;
Graph G;
vector<long long> a;

void rec(int v, vector<bool> &seen, vector<int> &comp) {
    seen[v] = true;
    for (auto e : G[v]) {
        if (seen[e]) continue;
        rec(e, seen, comp);
    }
    comp.push_back(v);
}

void solve() {
    vector<vector<int>> comps;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        vector<int> comp;
        rec(v, seen, comp);
        comps.push_back(comp);
    }

    int sum = 0;
    for (auto comp : comps) sum += (int)comp.size() - 1;
    if (sum < (int)comps.size()-2) {
        cout << "Impossible" << endl;
        return;
    }
    if (comps.size() == 1) {
        cout << 0 << endl;
        return;
    }

    long long res = 0;
    vector<long long> rem;
    for (auto comp : comps) {
        long long mi = INF;
        int pmi = -1;
        for (int i = 0; i < comp.size(); ++i) {
            if (chmin(mi, a[comp[i]])) pmi = i;
        }
        res += mi;
        for (int i = 0; i < comp.size(); ++i) {
            if (i == pmi) continue;
            rem.push_back(a[comp[i]]);
        }
    }
    sort(rem.begin(), rem.end());
    int V = comps.size();
    for (int i = 0; i < V-2; ++i) res += rem[i];
    cout << res << endl;
}

int main() {
    cin >> N >> M;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    solve();
}

2020-03-10

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点)

AOJ AOJ-ICPC400点 ICPC国内予選 DP 数列区間区間DP 入れ子構造操作操作を好きな回数だけ行える操作後の結果の最適化問題最大回数・最大個数を求める AOJ-ICPC 最適化問題操作:削除制約条件:隣接する要素について操作:隣接する2個を削除

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！

問題へのリンク

問題概要

長さ $N$ の整数数列 $a_{1}, \dots, a_{N}$ が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。

値の差が 1 以下であるような、隣接する 2 つの要素を選び、2 つまとめて削除する

操作によって削除される要素の個数の最大値を求めよ。

制約

$1 \le N \le 300$

考えたこと

この手の「列の中の隣接する 2 項について処理を順次行う」というタイプの問題に対しては

スタックを用いたシミュレーション
区間 DP

といった手法が有効であることが多い。前者の例として「カッコ列の整合性判定」、後者の例として「最適行列積計算を求める DP」が有名だ。今回は後者のパターンになる。

dp[ i ][ j ] := 数列の区間 [i, j) に対して操作を施せる回数の最大値

としておく。このように区間 [i, j) をキーにもつような DP を区間 DP とよぶ人が多い。

区間 DP

さて、dp の遷移を作る上で、以下の 2 つの場合に分けられる。

ある k が存在して、区間 [i, k) と区間 [k, j) とは独立に操作したものとみなせる場合
区間 [i+1, j-1) の要素が無事すべて消滅し、要素 a[ i ] と a[ j - 1 ] のみが残る場合

前者は簡単だ

chmax(dp[ i ][ j ], dp[ i ][ k ] + dp[ k ][ j ])

とかで OK。後者はまず dp[ i + 1 ][ j - 1 ] = j - i - 2 であることが必要だ。その元で

a[ i ] == a[ j - 1 ] ならば、chmax(dp[ i ][ j ], j - i)
a[ i ] != a[ j - 1 ] ならば、chmax(dp[ i ][ j ], j - i - 2)

という感じだ。計算量は $O(N^{3})$ 。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
vector<int> w;

int solve() {
    vector<vector<int>> dp(N+1, vector<int>(N+1, -N));
    for (int i = 0; i <= N; ++i) {
        dp[i][i] = 0;
        if (i < N) dp[i][i+1] = 0;
    }
    for (int bet = 2; bet <= N; ++bet) {
        for (int i = 0; i + bet <= N; ++i) {
            int j = i + bet;
            if (dp[i+1][j-1] == j-i-2) {
                if (abs(w[i] - w[j-1]) <= 1) chmax(dp[i][j], j-i);
                else chmax(dp[i][j], j-i-2);
            }
            for (int k = i+1; k <= j-1; ++k) {
                chmax(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    return dp[0][N];
}

int main() {
    while (cin >> N, N) {
        w.resize(N);
        for (int i = 0; i < N; ++i) cin >> w[i];
        cout << solve() << endl;
    }
}

2020-03-10

Educational Codeforces Round 83 E. Array Shrinking (R2100)

Codeforces 区間DP DP 操作操作を好きな回数だけ行える入れ子構造操作:2つのものを1つにマージ最大回数・最大個数を求める EducationalCodeforces CodeforcesR2100 最適化問題

区間 DP な問題って、あまり見なくなったなと。貴重なので記録。

問題へのリンク

問題概要

長さ $N$ の数列 $a_{1}, \dots, a_{N}$ が与えられる。以下の操作を好きな順序で好きな回数だけ行える。

隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、代わりに v + 1 に置き換える

一連の操作後の数列の長さの最小値を求めよ。

制約

$1 \le N \le 500$

考えたこと

出た！！！ぷよぷよ的な構造をした問題。ぷよぷよ的な構造とは「列の中の隣接する二項についてどうのこうのする」という雰囲気のこと。有名な「カッコ列の整合性判定」なんかもそう。

そういう問題に対しては

stack を用いてシミュレーション
区間 DP

といった手法が大変有力である。今回は区間 DP がピッタリはまる。区間 DP とはどのようなものかにつては、たとえば以下の問題にある。

atcoder.jp

今回はこんな感じの DP を組んだ

dp[ i ][ j ] := 区間 [i, j) についての、操作後の長さの最小値
val[ i ][ j ] := dp[ i ][ j ] の値が 1 となる場合のみ、そのときの数列の値を記録する

という風にした。計算量は $O(N^{3})$ に。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<29;
int N;
vector<int> a;

long long solve() {
    vector<vector<int>> dp(N+1, vector<int>(N+1, INF));
    vector<vector<int>> val(N+1, vector<int>(N+1, -1));
    for (int i = 0; i < N; ++i) {
        dp[i][i+1] = 1;
        val[i][i+1] = a[i];
    }
    for (int bet = 2; bet <= N; ++bet) {
        for (int i = 0; i + bet <= N; ++i) {
            int j = i + bet;
            for (int k = i+1; k <= j-1; ++k) {
                if (dp[i][k] == 1 && dp[k][j] == 1 && val[i][k] == val[k][j]) {
                    dp[i][j] = 1;
                    val[i][j] = val[i][k] + 1;
                }
                else {
                    chmin(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    return dp[0][N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 

    while (cin >> N) {
        a.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        cout << solve() << endl;
    }
}

2020-03-10

Educational Codeforces Round 83 G. Autocompletion (R2600)

Codeforces EducationalCodeforces DFS 非自明な線形時間 DP 木木DP 木上で配っていくDP trie木最短路問題最小コスト場合分けグラフ各kに対して辞書順 DP高速化 DP高速化:累積和累積和 CodeforcesR2600 最適化問題

頑張って DFS だけで通した！！！

問題へのリンク

問題概要

頂点数 $N+1$ の Trie 木と、そのうちの $K$ 個の頂点集合 $S$ が与えられる。 $S$ の各頂点 $v$ について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。

トライ木の辺を 1 本先に進める (親方向には進めない)：コスト 1
$S$ のうち今いる頂点の子孫 (今いる頂点を含む) のみを取り出した集合を $S'$ として、 $v$ が $S'$ に含まれるならば一気に移動する：コストは、 $S'$ における $v$ の辞書順順位 (1-indexed)

制約

$1 \le N \le 10^{6}$

考えたこと

とりあえず DP することを考える。dp[ v ] を v にいたるまでの最小コストとする。dp[ v ] を求めるにあたり、以下の 2 つの場合に分けられる

1 個上の親 p から 1 歩進んで到達する
いずれかの先祖 w から、一気に到達する

このうちの前者については簡単で、chmin(dp[ v ], dp[ p ] + 1)。
後者についてちゃんと考えることにする。

DFS

ここで、以下の変数を導入しよう。

iter[ v ] := トライ木を辞書順に DFS していったとき、頂点 v に到達した時点で、S に含まれる頂点を何個訪れたか？ (ただし v 自身が S に含まれるときは、この個数に v を含めないこととする)

このとき、w から v へと移動した場合の DP 遷移は次のように表せるのだ。

chmin(dp[ v ], dp[ w ] + (iter[ v ] - iter[ w ] + 1))

ここで、iter[ v ] - iter[ w ] + 1 というのが、移動コストを表す。この遷移式をよく眺めて、集める DP にするとこうなる！

dp[ v ] = iter[ v ] + min(w: v の先祖) (dp[ w ] - iter[ w ] + 1)

こうしてみると、min の部分は累積和をとるような要領で管理すれば、DFS 一発で全頂点に対する DP 値が求められることがわかった！！！

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Edge = pair<int, char>;
using Graph = vector<vector<Edge>>;
const int INF = 1<<29;

void rec(const Graph &G, const vector<int> &isS, vector<int> &dp,
         int v, int &iter, int dp_of_parent, int min_dp_iter) {
    chmin(dp[v], dp_of_parent + 1);
    if (isS[v]) chmin(dp[v], iter + min_dp_iter);
    chmin(min_dp_iter, dp[v] - iter + 1);
    if (isS[v]) ++iter;
    for (auto e : G[v])
        rec(G, isS, dp, e.first, iter, dp[v], min_dp_iter);
}

int main() {
    // input
    int N; scanf("%d", &N);
    Graph G(N+1);
    for (int i = 0; i < N; ++i) {
        int v; char c;
        scanf("%d %c", &v, &c);
        G[v].emplace_back(i+1, c);
    }
    for (int i = 0; i <= N; ++i)
        sort(G[i].begin(), G[i].end(),
             [&](Edge x, Edge y) { return x.second < y.second; });
    int K; scanf("%d", &K);
    vector<int> S(K), isS(N+1, false);
    for (int i = 0; i < K; ++i) scanf("%d", &S[i]), isS[S[i]] = true;

    // solve
    int iter = 1;
    vector<int> dp(N+1, INF);
    rec(G, isS, dp, 0, iter, -1, 0);
    vector<int> res(K, -1);
    for (int i = 0; i < K; ++i) { 
        if (i) printf(" ");
        printf("%d", dp[S[i]]);
    }
    printf("\n");
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder Petrozavodsk Contest 001 A - Two Integers (灰色, 100 点)

問題概要

考えたこと

AtCoder Petrozavodsk Contest 001 D - Forest (青色, 600 点)

問題概要

制約

考えたこと

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点)

問題概要

制約

考えたこと

区間 DP

Educational Codeforces Round 83 E. Array Shrinking (R2100)

問題概要

制約

考えたこと

Educational Codeforces Round 83 G. Autocompletion (R2600)

問題概要

制約

考えたこと

DFS