Codeforces Round #644 (Div. 3)

codeforces.com

A. Minimal Square

ならをそうでないならを正方形の辺として使う
提出コード

void solve(){
    int 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. Honest Coach

ソートをし、隣接要素の差の絶対値の最小を出力すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> s(n);
    REP(i,n) cin >> s[i];
    sort(s.begin(), s.end());
    int ans = INF;
    REP(i,n-1){
        chmin(ans, abs(s[i+1] - s[i]));
    }
    cout << ans << endl;
}

C. Similar Pairs

偶数のものと奇数のものの数を数える
このとき偶数の数と奇数の数が両方2で割り切れるものなら"YES"
そうでないときは、偶数のものと奇数のものを1つずつ使ってペアを作ることができれば"YES"になる
したがって、そのようなときは差が1であるペアを見つければいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int even = 0, odd = 0;
    REP(i,n){
        cin >> a[i];
        if(a[i] & 1) odd++;
        else even++;
    }

    if(even % 2 == 0 && odd % 2 == 0){
        cout << "YES" << endl;
        return;
    }
    sort(a.begin(), a.end());
    REP(i,n-1){
        if(a[i+1] - a[i] == 1){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

D. Buying Shovels

nの約数を調べる
nの約数を調べていき、k以下で最大のものを見つければいい
提出コード

void solve(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    for(ll i=1; i*i <= n; i++){
        if(n % i == 0){
            if(i <= k) chmax(ans, i);
            if(i != n / i && n / i <= k) chmax(ans, n/i);
        }
    }
    cout << n / ans << endl;
}

E. Polygon

操作を考えると、n行目とn列目以外で'1'がある場合
行方向もしくは列方向の1つ後ろに'1'がなければいけない
そのため、これを満たすかどうかを全部調べればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<string> fi(n);
    REP(i,n) cin >> fi[i];
    bool ok = true;
    REP(i,n) REP(j,n){
        if(fi[i][j] == '1'){
            if(i == n-1 || j == n-1) continue;
            if(fi[i+1][j] == '1' || fi[i][j+1] == '1') continue;
            ok = false;
        }
    }
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}

F. Spy-string

i文字目を考えたときにいくつの文字列が異なるものになるかを考える
i文字目に出現する文字の種類をとすると
個の文字列がsとi文字目が異なる文字列となる
sと1文字異なるものが許されるのはn個までなのでのときは作れない
そうでないときは、dfsで作ることの出来る文字列を全列挙し、条件に合うものを出力する
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    REP(i,n) cin >> a[i];
    vector<int> cnt(m);
    vector<vector<char>> c(m);
    int diff = 0;
    int ma = 0;
    REP(i,m){
        REP(j,n){
            c[i].push_back(a[j][i]);
        }
        sort(c[i].begin(), c[i].end());
        c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
        cnt[i] = (int)c[i].size();
        if(cnt[i] > 1) diff++;
        chmax(ma, cnt[i]);
    }

    if(diff == 0 || diff == 1){
        cout << a[0] << endl;
        return;
    }

    int sumDiff= 0;
    REP(i,m) sumDiff += cnt[i] - 1;
    if(sumDiff > n){
        cout << -1 << endl;
        return;
    }
    string ans = "";
    auto dfs = [&](auto && self, string cur, int len) -> void{
        if(len == m){
            bool ok = true;
            REP(i,n){
                int cntDiff = 0;
                REP(j,m) if(a[i][j] != cur[j]) cntDiff++;
                if(cntDiff > 1){
                    ok = false;
                    break;
                }
            }
            if(ok){
                ans = cur;
                return;
            }
            return;
        }
        if(cnt[len] == 1){
            cur += a[0][len];
            self(self, cur, len+1);
        }
        else{
            for(auto c1 : c[len]){
                cur += c1;
                self(self, cur, len+1);
                cur.pop_back();
            }
        }
    };

    string cur = "";
    dfs(dfs, cur, 0);
    if(ans == "") cout << -1 << endl;
    else cout << ans << endl;
}

G. A/B Matrix

のときのみ構築することが出来る
このようなとき各行にa個ずつ各列に連続して並べ、次の行は前の行の最後においた列の次からまた連続でa個置いていくように作ればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<ll> a(N), b(N);
    ll sum = 0, mi = LINF;
    REP(i,N){
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) chmin(mi, b[i]);
        sum += a[i];
    }
    if(a == b) cout << 0 << endl;
    else cout << sum - mi << endl;
}