Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov!

A. Nastya and Rice

問題概要

一つ重さの粒が個あり、その和がである場合、粒の重さを決めてsumの範囲におさめられるか。

実装

void solve(){
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    int l = c - d;
    int r = c + d;
    if(n*(a+b) < l || r < n*(a-b))cout << "No" << endl;
    else cout << "Yes" << endl;
}

B. Nastya and Door

問題概要

長さの区間の中で、となるiを峰と呼ぶ。峰の数が最大になる最小の左端と、そのときの峰の数の最大値を求めよ。

解説

尺取り？っぽくやるだけだが、本番はdequeを使ってバグらせていた・・・

実装

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N);
    rep(i,N)cin>>a[i];
    a.push_back(a[N-1]);
    //初期化
    ll cnt = 0;
    //0 ~ K-1まで
    for(int i = 1; i <= K-2; i++){
        if(a[i-1] < a[i] && a[i] > a[i+1]){
            cnt++;
        }
    }
    ll ans = cnt;
    ll l = 0;
    for(ll i = K; i < N; i++){
        //i - K が抜ける
        if(a[i-K] < a[i-K+1] && a[i-K+1] > a[i-K+2]){
            cnt--;
        }
        //iが入る
        if(a[i-2] < a[i-1] && a[i-1] > a[i]){
            cnt++;
        }
        if(ans < cnt){
            ans = cnt;
            l = i - K + 1;
        }
    }
    cout << ans + 1 <<" " <<  l + 1 << endl;
}

C. Nastya and Strange Generator

問題概要

難読。説明もするのもキツイが、実験すると、最初に選んだ に依存して、そこから右に順に埋まっていくことがわかる。 よって、全てのについて、

• 

• 

となることがわかる。 こうなっていなかったらNo。

実装

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N){
        cin>>a[i];
    }
    rep(i,N-1){
        if(a[i]+1 < a[i+1]){
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

D. Nastya and Scoreboard

問題概要

電光掲示板の初期状態が与えられるので、そこからちょうど個点灯させて、実現できる最大の数を求めよ。

解説

DPをします。ただ、数の最大を取るようなDPをするとかかるので、まずboolのDPをして、dp[N][K]がtrueかどうかで実現できるかどうかを確認し、実現できるなら、(N, K)から逆に伝播させて遷移の辺を貼り、(0, 0)から貪欲に大きい数字を選んでいけばよい。

実装

//dp[i][j] := i個目までみて、K個使って作れるか
bool dp[2020][2020];
bool back[2020][2020];

int diff(string &x, string &y) {
    int res = 0;
    rep(i, x.size()) {
        if (x[i] == '1' && y[i] == '0')return -1;
        if (x[i] == '0' && y[i] == '1')res++;
    }
    return res;
}

void solve() {
    int N, K;
    cin >> N >> K;
    vector<string> a(N);
    rep(i, N)cin >> a[i];
    string v[] = {
            "1110111", "0010010", "1011101",
            "1011011", "0111010", "1101011",
            "1101111", "1010010", "1111111",
            "1111011"
    };
    rep(i,N+1)rep(j,N+1){
        dp[i][j] = false;
        back[i][j] = false;
    }
    dp[0][0] = true;
    rep(i, N) {
        rep(j, K + 1) {
            if (!dp[i][j])continue;
            for (auto & k : v) {
                int cnt = diff(a[i], k);
                if (cnt == -1)continue;
                if (j + cnt > K)continue;
                dp[i + 1][j + cnt] = true;
            }
        }
    }
    if (!dp[N][K]) {
        cout << -1 << endl;
        return;
    }
    // 逆伝播
    back[N][K] = true;
    for (int i = N; i >= 1; i--) {
        // (i-1, j-cnt) <- (i, j)
        for (int j = 0; j <= K; ++j) {
            if (!back[i][j])continue;
            for (auto &k : v) {
                int cnt = diff(a[i - 1], k);
                if (cnt == -1)continue;
                if (j - cnt < 0)continue;
                if (!dp[i - 1][j - cnt])continue;
                back[i - 1][j - cnt] = true;
            }
        }
    }
    string ans;
    int pre = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 9; k >= 0; k--) {
            int cnt = diff(a[i], v[k]);
            if (cnt == -1)continue;
            if (pre + cnt > K)continue;
            if (back[i + 1][pre + cnt]) {
                ans.push_back(char(k + '0'));
                pre = pre + cnt;
                break;
            }
        }
    }
    cout << ans << endl;
}