Codeforces Round #630 (Div. 2) - 接着剤の精進日記

A. Exercising Walk

問題文

0以上の整数a, b, c, dが与えられ、以下の操作を行うことを考える
ただし操作は任意の順番で行える
1. a回左に移動: from (𝑢,𝑣) to (𝑢−1,𝑣)
2. b回右に移動: from (𝑢,𝑣) to (𝑢+1,𝑣)
3. c回下に移動: from (𝑢,𝑣) to (𝑢,𝑣−1)
4. d回上に移動: from (𝑢,𝑣) to (𝑢,𝑣+1)
この時、初期位置(x, y)が与えられ、 $x1 \leq u \leq x2$ かつ $y1 \leq v \leq y2$ を満たすようにすべての操作を行えるかを判定せよ

解法

$x1 == x2$ もしくは $y1 == y2$ がコーナーケースになるので注意
それ以外は上下と左右で独立して考え、それぞれの差の絶対値分はその方向に移動しなければいけないので、それを判定する

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll x, y, x1, y1, x2, y2;
        cin >> x >> y >> x1 >> y1 >> x2 >> y2;
        if(a > 0 || b > 0){
            if(x1 == x2){
                cout << "NO" << endl;
                continue;
            }
        }
        if(c > 0 || d > 0){
            if(y1 == y2){
                cout << "NO" << endl;
                continue;
            }
        }
        ll u = x + b - a, v = y + d - c;
        if((x1 <= u && u <= x2) && (y1 <= v && v <= y2)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

B. Composite Coloring

問題文

n個の合成数が与えられれ、それぞれに対し色を塗っていくことを考える
次の条件を満たすように色を塗っていく時、条件を満たすmとその塗り方を出力せよ（ $1 \leq m \leq 11$ ）
1. 1からmまでの色は、それぞれ少なくとも1つ以上存在する
2. 1つの要素には丁度1つの色しか塗れない
3. 同じ色で塗られているもので、任意のペア(i, j)に対し $GCD(a_i, a_j) \gt 1$ を満たす

解法

1000以下の合成数が与えられるため $\sqrt{1000}$ 以下を考える
そのような合成数は必ず31以下の素数を含み、31以下の素数は丁度11個あるので必ず構築できる
そのため、11個の素数で適当にグループ分けをしていけばいい

提出コード

int p[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        cin >> n;
        vector<int> a(n);
        vector<bool> used(11);
        int cnt = 1;
        REP(i,n){
            cin >> a[i];
            REP(j,11) if(a[i] % p[j] == 0){
                a[i] = p[j];
                if(used[j]) break;
                used[j] = true;
                break;
            }
        }
        map<int, int> mp;
        REP(i,11) if(used[i]) mp[p[i]] = cnt++;
        cout << cnt - 1 << endl;
        REP(i,n) cout << mp[a[i]] << " ";
        cout << endl;
    }
}

C. K-Complete Word

問題文

長さnの文字列sとnの約数となるような正の整数kが与えられる
一回の操作で文字列sの任意の1文字を好きな文字に変えられる
以下の条件を満たすように操作を行った時、その最小回数を答えよ
$𝑠_𝑖 = 𝑠_{𝑛+1−𝑖} (1 \leq 𝑖 \leq 𝑛)$
$𝑠_i =𝑠_{𝑘+𝑖} (1 \leq 𝑖 \leq 𝑛−𝑘)$

解法

条件を満たすように操作を行うと、あるグループは全部同じ文字になる
そのため、条件を満たすグループごとにどの文字にするのが最適化を全探索する

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n, k;
        string S;
        cin >> n >> k >> S;
        int ans = 0;
        vector<bool> used(n, false);
        for(int i=0;i<k;i++){
            int ma = 0;
            int cnt = 0;
            vector<int> alp(26);
            for(int j=i;j<n;j+=k) if(!used[j]){
                alp[S[j]-'a']++;
                cnt++;
                used[j] = true;
            }
            for(int j=n-1-i;j>=0;j-=k) if(!used[j]){
                alp[S[j]-'a']++;
                cnt++;
                used[j] = true;
            }
            REP(i,26) chmax(ma, alp[i]);
            ans += cnt- ma;
        }
        cout << ans << endl;
    }
}

D. Walk on Matrix

問題文

n × mの行列上を(1, 1)からスタートし、右もしくは下に移動し(n,m)まで行くことを考える
プレイヤーは最初 $a_{1,1}$ のスコアを持っており、マス(i, j)を通ると今のスコアと $a_{i, j}$ との論理積を取ったものがスコアとなる
このような行列を考えた時、実際に得られる最大値とBobが考えたアルゴリズムの出力との差が丁度kとなるようなnとmおよびその行列の要素 $a_{i, j}$ を出力せよ

解法

解説にある通り、次のような出力をすれば良い
f:id:tkm-kyudo:20200401170033p:plain
Bobのアルゴリズムではdp[2][2] = $2^{17}$ となり、dp[2][3] = 0となる
(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) と通ればkとなり、条件を満たすことが出来る
提出コード

int a[3][4];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    a[1][1] = (1LL << 17) + k;
    a[1][2] = (1LL << 17);
    a[2][1] = k;
    a[2][2] = (1LL << 17) + k;
    a[2][3] = k;
    cout << 2 << " " << 3 << endl;
    for(int i=1;i<=2;i++){
        for(int j=1;j<=3;j++) cout << a[i][j] << " ";
        cout << endl;
    }
}

おわりに

mathforcesが苦手