接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

Codeforces Round #632 (Div. 2)

codeforces.com

A. Little Artem

問題文

n \times mのボードがあり、各マスは白か黒の色で塗られている
隣接する白マスが一つでもある黒マスの個数をB
反対に、隣接する黒マスが一つでもある白マスの個数をWとする
この時、 B = W + 1を満たすボードの色の塗り方を1つ出力せよ

解法

Aに置かれているので当然ギャグなんですが時間使いすぎた
1行目と1列目を全部黒に塗ってそれ以外は白に塗る
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n, m;
        cin >> n >> m;
        vector<string> fi(n, string(m, '.'));
        REP(i,n) fi[i][0] = 'B';
        REP(j,m) fi[0][j] = 'B';
        REP(i,n) REP(j,m) if(fi[i][j] == '.') fi[i][j] = 'W';
        REP(i,n) cout << fi[i] << endl;
    }
}

B. Kind Anton

問題文

n個の要素からなる数列a, bが与えられる
以下の操作を任意の回数行い、aをbに一致させられるかどうかを判定せよ
1. 1 \leq i \lt j \leq n を満たすペア  ( i, j )を選ぶ
1.  a_ja_i + a_jに変更する

解法

後ろから貪欲していくといい
今見ている数より前に1と-1がいくつあるかの情報を持っておき
a_ib_iに出来ないものがあればその時点でNOになる

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        int posi = 0, nega = 0;
        REP(i,n){
            cin >> a[i];
            if(i < n-1){
                if(a[i] > 0) posi++;
                else if(a[i] < 0) nega++;
            }
        }
        REP(i,n) cin >> b[i];
        bool ok = true;
        if(a[0] != b[0]) ok = false;
        for(int i=n-1;i>0;i--){
            if(i < n-1){
                if(a[i] < 0) nega--;
                if(a[i] > 0) posi--;
            }
            if(a[i] == b[i]) continue;
            if(b[i] > a[i] && posi > 0) continue;
            if(b[i] < a[i] &&  nega > 0) continue;
            ok = false;
            break;
        }
        if(ok) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

C. Eugene and an array

問題文

長さnの数列aが与えられる
aの連続する部分列のうち、部分列の連続する部分和に0となるものが存在しない時
その部分列を良い配列と呼ぶ
数列aの部分列のうち、良い配列の個数を求めよ

解法

Zero-Sum Rangesっぽくやる
ある区間の部分和が0になるには、累積和が0もしくは、すでに出現した値になる必要がある
そのため、左端を固定しながら区間の右端を伸ばしていき、累積和がすでに出てきた値なら左端を更新し、数え上げていく
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    map<ll, ll> mp;
    mp[0] = 0;
    ll left = -1;
    ll sum = 0;
    ll ans = 0;
    REP(i,n){
        ll a;
        cin >> a;
        sum += a;
        if(mp.count(sum)) chmax(left, mp[sum]);
        ans += i - left;
        mp[sum] = i + 1;
    }
    cout << ans << endl;
}

D. Challenges in school №41

問題文

n人の子どもたちが1列に並んでおり、右(R)もしくは左(L)を向いている
1秒ごとに子供たちが向かい合っているペアを任意の数だけお互いの向きを反対にすることが出来る
ただし、1秒間に最低1つのペアを反転させる必要がある
この時、丁度k秒で向かい合っているペアを0に出来るかどうかを判定し、可能ならばその操作を出力せよ

解法

1秒の間に可能なペアをすべて反転させることを考える
その時、操作を行う必要のある回数kを超えていたら不可能
また、操作を行えるペアの個数がk未満だったら不可能
それ以外は操作を行うことが可能である
この時、kに合わせるために、その差分だけ1秒間に1つのペアを出力して合わせてあげればいい
終わった後TLで見かけたけど、'L'と'R'を数値とみなすと隣接swapの操作の最大は転倒数になる(天才か?)
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    string S;
    cin >> n >> k >> S;
    vector<vector<int>> ans;
    int cnt = 0;
    REP(i,n + 10){
        vector<int> tmp;
        for(int j=0;j<n;j++){
            if(S[j] == 'R' && S[j+1] == 'L'){
                tmp.push_back(j);
                swap(S[j], S[j+1]);
                j++;
            }
        }
        if(tmp.size() == 0) break;
        cnt += tmp.size();
        ans.emplace_back(tmp);
    }
    // cout << S << endl;
    // cout << cnt << " " << ans.size() << endl;
    if(cnt < k || (int)ans.size() > k){
        cout << -1 << endl;
        return 0;
    }
    k -= (int)ans.size();
    REP(i, ans.size()){
        while(k > 0 && (int)ans[i].size() > 1){
            cout << 1 << " " << ans[i].back() + 1 << '\n';
            ans[i].pop_back();
            k--;
        }
        cout << ans[i].size() << " ";
        for(auto x : ans[i]) cout << x + 1 << " ";
        cout << '\n';
    }
}

おわりに

Cで頭壊れてしまった
D復習して無限にTLEになる〜ってなってたけどendlが原因だった(それはそう)