Codeforces Round #786 (Div. 3)

はじめに

バチャの記録です

記録は $3$ ペナ全完

いやー 前半でペナってしまったのでとても焦りました

本文

A. Number Transformation

概要

整数 $x$, $y$ が与えられる

以下の条件をみたす正整数 $a$, $b$ を一組出力してください

• $x$ を $x \cdot b$ で置き換える操作をちょうど $a$ 回行うと $x$ と $y$ が等しくなる

そのような $a$, $b$ が存在しなければそのことを報告してください

制約

• $1 \le x, y \le 100$

解法

$x$ が $y$ の約数でないと明らかに不可能

逆に, $x$ が $y$ の約数なら $a = 1$, $b = y/x$ とすれば良いです

$a > 1$ だと勘違いして $x = y$ をダメにしたけどサンプルに助けられました

#include <bits/stdc++.h>
using namespace std;

int main(){
  int t; cin >> t;
  while(t--){
    int x, y; cin >> x >> y;
    int a = 0, b = 0;
    if(y % x == 0) a = 1, b = y / x;
    cout << a << " " << b << "\n";
  }
}

B. Dictionary

概要

長さ $2$ の相異なる英小文字からなる文字列が与えられる

長さ $2$ の相異なる英小文字全体の集合のうち, 与えられた文字列が辞書順で何番目なのか求めよ

解法

算数

これは $25$ 進法のようなふるまいをすることがわかります (アルファベット $26$ 文字のうちダブっていない $25$ 個が二文字目に使える)

よって, 桁ごとに見て足し合わせればいいです

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int t; cin >> t;
  while(t--){
    string s; cin >> s;
    cout << (s[0] - 'a') * 25 + (s[1] - 'a') + (s[0] > s[1]) << "\n";
  }
}

全探索

集合の大きさは $26 \times 25$ 通り程度しかありません

よって, すべてを列挙していきながら数えればいいです

#include <bits/stdc++.h>
using namespace std;

int main(){
  int t; cin >> t;
  while(t--){
    string s; cin >> s;
    int cnt = 0;

    string bs = "aa";
    for(bs[0] = 'a'; bs[0] <= 'z'; ++bs[0]){
      for(bs[1] = 'a'; bs[1] <= 'z'; ++bs[1]){
        if(bs[0] == bs[1]) continue;
        if(bs <= s) ++cnt;
      }
    }

    cout << cnt << "\n";
  }
}

また, 一度列挙して map などに記録しておくことでも求められます (バチャ中はこの解法で解きました)

#include <bits/stdc++.h>
using namespace std;

int main(){

  map<string, int> mp;
  {
    string s = "aa";
    for(s[0] = 'a'; s[0] <= 'z'; ++s[0]){
      for(s[1] = 'a'; s[1] <= 'z'; ++s[1]){
        if(s[0] == s[1]) continue;
        mp[s] = mp.size() + 1;
      }
    }
  }

  int t; cin >> t;
  while(t--){
    string s; cin >> s;
    cout << mp[s] << "\n";
  }
}

Tips

mp[s] = mp.size() + 1;

という書き方は, 左辺が先に評価された場合 map の要素数が変わってしまうことがあります

C++14 までは部分式の評価順序は未規定だったため, 意図しない結果になってしまう可能性がありましたが, C++17 からは代入演算子, 複合代入演算子が右辺から評価されることが規定されました

Codeforces や AtCoder では問題ありませんが環境によってはバグの要因になるため気を付けましょう

参考: cpprefjp 厳密な式の評価順

C. Infinite Replacement

概要

'a' のみを含む文字列 $s$ が与えられる

$s$ に含まれる 'a' を一つ選んで文字列 $t$ で置換する という操作を $0$ 回以上の好きな回数行えるとき, 最終的に得られる文字列の種類数を求めよ

解法

$t$ に 'a' が含まれている場合, 置換した後の文字列にも必ず 'a' が含まれるため無限に相異なる文字列を作ることができる

ただし, $t =$ "a" の場合は置換しても何も起きないため, 一通り

$t$ に 'a' が含まれていない場合, 置換できる回数は $|s|$ 回. また, 相異なる 'a' を置換した場合相異なる文字列ができる よって $2 ^ {|s|}$ 通り

$2 ^ {|t|}$ と書き間違えて $1$ ペナ

#include <bits/stdc++.h>
using namespace std;

int main(){
  int q; cin >> q;
  while(q--){
    string s, t; cin >> s >> t;
    if(t.find('a') != string::npos) cout << (t.size() == 1 ? 1 : -1) << "\n";
    else cout << (1ll << s.size()) << "\n";
  }
}

C++23 からは s.contains(c) と書けるようになるのでうれしい 早く使わせろ

テストケース数が $t$ じゃなくてびっくりしたけど文字列のほうを $t$ にしたかったんですね

D. A-B-C Sort

概要

長さ $n$ の数列 $a$ と, 空の数列 $b, c$ が与えられる

以下の操作を行う

1. $a$ の要素を後ろから見て, $b$ の真ん中に挿入する
2. $b$ の要素を真ん中から見て, $c$ の末尾に挿入する

どちらの操作も, $b$ が奇数長の場合, どちらに挿入するか/どちらを選ぶかは自由

操作後, $c$ をソートされた状態にできるのか判定しなさい

解法

ちゃんと考察がいるタイプの問題, 困った

後ろの二要素を見てみると

$a _ {n-1}$: $b$ への挿入は一通り $c$ への挿入は二通り ($c _ {n-2}$ or $c _ {n-1}$)

$a _ {n-2}$: $b$ への挿入は二通り $c$ への挿入は二通り

ということで $a _ {n-1}$ と $a _ {n-2}$ を swap することはできるが, それ以上の移動はできないことがわかる

つまり, ほかの要素はこの二要素の移動に干渉できない

結局, 後ろから二要素ずつ見て行って swap するかどうか選択する という操作であるということがわかる

#include <bits/stdc++.h>
using namespace std;

int main(){
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    vector<int> a(n); for(auto&&e : a) cin >> e;
    for(int i = n&1; i < n - 1; i += 2){
        if(a[i] > a[i + 1]) swap(a[i], a[i + 1]);
    }
    auto b = a; sort(begin(b), end(b));
    puts(a == b ? "YES" : "NO");
  }
}

E. Breaking the Wall

概要

長さ $n$ の数列 $a$ が与えられる

整数 $i \in [0, n)$ を選んで $a _ {i-1} -= 1$, $a _ i -= 2$, $a _ {i+1} -= 1$ とする

という操作を繰り返して $a$ の要素を二つ $0$ 以下にするとき, 操作回数の最小値を求めよ

解法

$0$ 以下にする二つの要素 $i, j$ を全探索する

愚直に行うと $O(n^2)$ 通り存在するが, 次の三通りに場合分けする

1. 隣接二項を選ぶ ($j = i+1$)

ここが一番厄介

選び方は $n - 1$ 通り

大きいほうを $x$, 小さいほうを $y$ とする

まず $x - y$ 回 $x$ のほうを $-2$ することで $x = y$ にする

その後, $x, y$ 交互に多く減らすことで合計 $3$ ずつ削っていくのが最適

これには $\lceil\dfrac{2x}{3}\rceil$ 回かかることがわかる

コーナーケースは差が埋まるより前にどちらも $0$ になるとき

1. 一つ飛ばしの二項を選ぶ ($j = i+2$)

真ん中を叩いて片方を $0$ にして残った回数もう片方を叩く

1. 任意の二項を選ぶ

$a$ の小さいほうから二つ選んでそれぞれ叩く

これら合計 $O(n)$ 通りについてそれぞれ $O(1)$ で試すことができる

それらの min が答え

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  vector<int> a(n); for(auto&&e : a) cin >> e;

  int ans = 1e9;
  for(int i = 0; i < n-1; ++i){
    auto[y, x] = minmax(a[i], a[i+1]);
    if(int d = x - y; d >= (x + 1)/2){
      ans = min(ans, (x + 1)/2);
    }else{
      ans = min(ans, d + ((y - d) * 2 + 2)/3);
    }
  }

  for(int i = 1; i < n-1; ++i){
    auto[y, x] = minmax(a[i-1], a[i+1]);
    ans = min(ans, y + (x - y + 1)/2);
  }

  nth_element(begin(a), begin(a) + 1, end(a));
  ans = min(ans, (a[0] + 1)/2 + (a[1] + 1)/2);

  cout << ans << "\n";
}

適当に三分探索したら $2$ ペナくらってしまいました (あきらめてまじめに算数した)

F. Desktop Rearrangement

概要

$n \times m$ のグリッドが与えられる

左からいくつかの列は '*' で埋まっていて次の列も prefix が '*' でありそれ以外すべて '.' (なんて言えばいいんですかこれ) であるようなグリッドを 良い とする

各クエリでは, ある一点の '*' と '.' を反転させた後, 次の問題に答える

任意の二点を swap してグリッドを良い状態にするとき, 操作回数の最小値を求めよ

但し, クエリで反転させた状態はその後のクエリでも反転されたままになる

解法

良い状態のグリッドは一意に定まる

よって, swap する回数の最小値はそこからはみ出した '*' の数と等しい

更新ありの区間和なので Binary Indexed Tree を使えば求まる

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, m, q; cin >> n >> m >> q;
  vector<int> fw(n * m + 1), a(n * m, -1);

  auto add = [&](int i, int x){
    for(++i; i <= n * m; i += (i & -i)) fw[i] += x;
  };

  auto sum = [&](int i){
    int s = 0;
    for(; i > 0; i -= (i & -i)) s += fw[i];
    return s;
  };

  for(int i = 0; i < n; ++i){
    string s; cin >> s;
    for(int j = 0; j < m; ++j){
      if(s[j] == '*') add(j * n + i, 1), a[j * n + i] = 1;
    }
  }

  while(q--){
    int x, y; cin >> x >> y; --x; --y;
    int p = y * n + x;
    a[p] *= -1;
    add(p, a[p]);

    int s = sum(n * m);
    cout << s - sum(s) << "\n";
  }
}

いろいろサボってるところをまじめにやれば高速化できそうではある

G. Remove Directed Edges

概要

$n$ 頂点 $m$ 辺の非巡回有向グラフが与えられる このグラフは単純である

このグラフからいくつかの辺を取り除くことを考える

ただし, 任意の頂点 $v$ について $v$ の入次数/出次数はどちらも減少するように取り除かなければいけない (もともと $0$ の場合は ok)

取り除かれた後のグラフの頂点の部分集合 $S$ を考える

任意の $u, v \in S$ について $u - v$ パス または $v- u$ パスが存在する場合, $S$ は cute である とする

cute な $S$ の要素数の最大値を求めよ

解法

非巡回有向グラフと言われているのでトポロジカルソートしてみる

$dp _ v = v$ を含み $v$ よりトポロジカルソート順で後ろの頂点のみからなる cute な集合の大きさの最大値

という dp を考えると, トポロジカルソート順で後ろから埋めていける

ただし, かならず辺を取り除かなければいけないので次数が $2$ 未満の場合は遷移できない そうでないときは最大をとるような辺以外を取り除いたことにすればよい

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, m; cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> in(n), out(n);

  while(m--){
    int u, v; cin >> u >> v; --u; --v;
    g[u].push_back(v);
    ++in[v];
    ++out[u];
  }

  vector<int> vs;

  {
    queue<int> qu;
    auto tmp = in;
    for(int v = 0; v < n; ++v){
      if(tmp[v] == 0) qu.push(v);
    }
    while(!qu.empty()){
      int v = qu.front(); qu.pop();
      vs.push_back(v);

      for(int e : g[v]){
        if(--tmp[e] == 0) qu.push(e);
      }
    }
  }
  

  reverse(begin(vs), end(vs));
  vector<int> dp(n, -1);
  int ans = 1;

  for(int v : vs){
    if(out[v] >= 2){
      for(int e : g[v]) dp[v] = max(dp[v], dp[e] + 1);
    }

    ans = max(ans, dp[v]);
    if(in[v] >= 2) dp[v] = max(dp[v], 1);
    else dp[v] = -1;
  }

  cout << ans << "\n";
}

おわりに

地味にめんどくさい問題が多くて疲れました

いい感じにガチャガチャするタイプの問題適当になってしまうのやめないとなぁという気持ち