Codeforces Round #644 (Div. 3) 参加記

コンテストへのリンク

Gがわかりません・・・。

A

問題へのリンク

として一辺は。

void solve() {
    ll a, b;
    cin >> a >> b;
    if(a >= b)swap(a,b);
    if(2*a >= b){
        cout << 2 * a * 2 * a << endl;
    }
    else{
        cout << b*b << endl;
    }
}

B

問題へのリンク

差の最小値。

void solve(){
    int N;
    cin >> N;
    vec<ll> a(N);
    rep(i,N)cin >> a[i];
    sort(all(a));
    ll ans = INFLL;
    rep(i,N-1){
        chmin(ans, a[i+1] - a[i]);
    }
    cout << ans << '\n' ;

}

C

問題へのリンク

parityで分類して両方偶数ならOK、奇数ならそれらの組みの中で差が1のものがあればよい。

void solve() {
    int N;
    cin >> N;
    vec<int> a, b;
    rep(i, N) {
        int x;
        cin >> x;
        if (x & 1)a.push_back(x);
        else b.push_back(x);
    }
    if (a.size() % 2 == 0) {
        cout << "YES" << endl;
    } else {
        rep(i, a.size()) {
            rep(j, b.size()) {
                if (abs(a[i] - b[j]) == 1) {
                    cout << "YES" << endl;
                    return;
                }
            }
        }
        cout << "NO" << endl;
    }
}

D

問題へのリンク

の約数で以下の最小値。

void solve(){
    ll N, K;
    cin >> N >> K;
    if(N <= K){
        cout << 1 << endl;
        return;
    }
    ll ans = N;
    for(ll x = 1; x*x <= N; x++){
        if(N%x == 0){
            ll tmp = N / x;
            if(tmp <= K){
                chmin(ans, x);
            }
            if(x <= K){
                chmin(ans, tmp);
            }
        }
    }
    cout << ans << endl;
}

E

問題へのリンク

行と列方向で後ろの両方が0である1は無理、どちらかにあればできる。

void solve(){
    int N;
    cin >> N;
    vec<string> S(N);
    rep(i,N)cin >> S[i];
    vvec<bool> ok(N,vec<bool>(N,true));
    vvec<bool> ok2(N,vec<bool>(N,true));
    //行方向
    for(int i = N-2;i >= 0; i--){
        rep(j,N){
            if(S[i][j] == '1' && S[i+1][j] == '0'){
                ok[i][j] = false;
            }
        }
    }

    for(int j = N-2;j >= 0; j--){
        rep(i,N){
            if(S[i][j] == '1' && S[i][j+1] == '0'){
                ok2[i][j] = false;
            }
        }
    }
    bool ans = true;
    rep(i,N)rep(j,N){
        if(!ok[i][j] && !ok2[i][j])ans = false;
    }
    cout << (ans ? "YES": "NO") << endl;
}

F

問題へのリンク

1つ目の文字列を一個変えた文字列が条件を満たすか確認するだけでいい。

void solve() {
    int N, M;
    cin >> N >> M;
    vec<string> a(N);
    rep(i, N)cin >> a[i];
    auto diff = [&](string &x, string &y) {
        int res = 0;
        rep(i, M) {
            if (x[i] != y[i])res++;
        }
        return res;
    };
    auto check = [&](string &s)->bool{
        vec<int> cnt(N,0);
        rep(i,N){
            cnt[i] = diff(s, a[i]);
        }
        int mx = *max_element(all(cnt));
        return mx <= 1;
    };
    for (int k = 0; k < 26; k++) {
        rep(i, M) {
            //a[0]のi文字目をkに変えて、満たされるか確認
            string tmp = a[0];
            tmp[i] = char('a' + k);
            if(check(tmp)){
                cout << tmp << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
    return;
}

G

問題へのリンク

横にa文字ずつ入れながら、行ごとにaずつずらすと満たすらしい

int ans[100][100];
void solve() {
    ll n, m, a, b;
    cin >> n >> m >> a >> b;
    if(n * a != m * b){
        cout << "NO" << endl;
        return;
    }
    rep(i,n)rep(j,m)ans[i][j] = 0;
    cout << "YES" << endl;
    int idx = 0;
    rep(i,n){
        rep(j,a){
            ans[i][(idx+j)%m] = 1;
        }
        idx += a;
    }
    rep(i,n){
        rep(j,m){
            cout << ans[i][j];
        }
        cout << endl;
    }
}

H

問題へのリンク

二分探索して、下に半分ぴったりになる境界を探す。判定が微妙すぎる。

void solve(){
    int N, M;
    cin >>  N >> M;
    vec<ll> a(N);
    rep(i,N) {
        string tmp;
        cin >> tmp;
        a[i] = stoll(tmp, nullptr, 2);
    }
    sort(all(a));
    //print(a);
    auto check = [&](ll X) -> bool {
        //X未満の個数を数える
        ll idx = lower_bound(all(a), X) - a.begin();
        ll cnt = X  - idx;
        return bit(M) - N > cnt*2;
    };
    ll ok = -1;
    ll ng = INFLL;
    while(ng - ok > 1){
        ll mid = (ok + ng) / 2;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    string ans;
    for(int i = M-1; i>=0;i--){
        ans.push_back('0'+(1&(ok>>i)));
    }
    cout << ans << endl;
}