問題概要

ある文字列SとKが与えられる。文字列SをK-completeな単語にするには最小で何文字変えれば良いか？なお、K-completeな単語とは以下のような単語を意味する。

回文である
i文字目とi+K文字目が等しい

なお、t個のテストケースに対して回答する必要がある。

入出力

入力

4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

出力

解答

Union-Find木を使う。まず、等しくなければならない文字群を列挙し、この文字群のなかで最も出現率の高いものに揃える。このときがコスト最小となる。

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using vi = vector<int>;
template<class T>using vv = vector<vector<T>>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)

struct UnionFind {
  vector<int> parent;
  UnionFind(int n) {
    parent.resize(n, -1);
  }
  int root(int x) {
    if (parent[x] == -1)
      return x;
    return parent[x] = root(parent[x]);
  }
  void unite(int x, int y) {
    if (root(x) == root(y))
      return;
    x = root(x); y = root(y);
    parent[x] = y;
    return;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

int main() {
  int in(t);

  rep(i, t) {
    int in(N); int in(K);
    vector<char> S(N);
    UnionFind T(N);
    rep(j, N) cin >> S[j];
    // 等しくなければならない箇所をunite
    rep(j, N-K) T.unite(j, j+K);
    rep(j, N) T.unite(j, N-1-j);

    // それぞれの文字群で文字の出現回数をカウント
    vv<int> count(N, vi(26, 0));
    rep(j, N)
      ++count[T.root(j)][S[j]-'a'];

    set<int> s;
    int ans = 0;
    rep(j, N) {
      if (s.find(T.root(j)) != s.end())
        continue;
      s.insert(T.root(j));
      int max_count = 0, sum = 0;
      rep(k, 26) {
        max_count = max(max_count, count[T.root(j)][k]);
        sum += count[T.root(j)][k];
      }
      ans += sum - max_count;
    }
    cout << ans << endl;
  }

  return 0;
}

2020-04-03

Perfect Keyboard

codeforces.com

問題

アルファベット26文字が1列に並ぶキーボードを考える。いま、パスワードがN個与えられる。キーボードの配列をうまく組み替えることで、隣接したキー間の移動のみでパスワードを入力することができるか？

入出力例

入力

はじめにパスワードの数Nが与えられる。以下N行にパスワードが与えられる

5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

たとえば1つ目のパスワードはabが隣接していれば入力することができる。しかし、3つ目はdとaを隣接して配置できないため、入力できない。

出力

YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

解説

この問題は「閉路を含まず、枝分かれのない木が1つだけ存在するグラフか？」と言い換えることができる。左右にしか移動できないという条件からこれが言える。

まず、枝分かれがないことを確認する。もし、次数が3以上の頂点があればその時点でNO。

次に、端が存在することを確認(次数が1の頂点が端)。もし端がなければ閉路となっているのでNO。

連結成分が2つ以上あるケースというのはそもそも存在しないので、以上で存在するかの判定は終了する。

あとはこの点からはじめて順にたどれば単純パスが完成する。その単純パスを先頭に並べて、残ったアルファベットを列挙すればAC。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

int main() {
  int in(N);

  rep(i, N) {
    string in(s);
    if (s.size() == 1) {
      // 1つだけならa-zで対応できる
      cout << "YES\nabcdefghijklmnopqrstuvwxyz\n";
      continue;
    }
    vector<int> edge(26, 0);
    rep(j, s.size()-1) {
      edge[s[j]-'a'] |= (1 << (int)(s[j+1]-'a'));
      edge[s[j+1]-'a'] |= (1 << (int)(s[j]-'a'));
    }

    // 単純パスを見つける
    int start = -1;
    bool ok = true;
    rep(j, s.size()) {
      if (__builtin_popcount(edge[s[j]-'a']) == 1)
        start = s[j]-'a';
      if (__builtin_popcount(edge[s[j]-'a']) > 2)
        ok = false;
    }

    // 閉路しかない
    if (start == -1)
      ok = false;
    if (!ok) {
      cout << "NO\n";
      continue;
    }

    vector<bool> visited(26, false);
    queue<int> q; q.push(start);
    vector<char> ans;
    while (!q.empty()) {
      int p = q.front(); q.pop();
      if (visited[p])
        continue;
      visited[p] = true;
      ans.push_back((char)(p+'a'));
      rep(j, 26)
        if (edge[p] & (1 << j))
          q.push(j);
    }

    cout << "YES\n";
    for (const auto& e : ans)
      cout << e;
    rep(j, 26) {
      if (visited[j])
        continue;
      cout << (char)(j+'a');
    }
    cout << endl;
  }

  return 0;
}

2020-04-03

Cow and Message

codeforces.com

問題

ある文字列Sが与えられる。Sに含まれる部分文字列のうち出現頻度が最も高いものの長さを求めよ

例

入力: ababab
出力: 6

これにはabが6個入っているので出力は6となっている。

解説

参考: 题解 Codeforces Round #621 (Div. 1 + Div. 2) (CF1307) - kylin_xy - 博客园

こちらの中国の方が書かれた解説を読んで通した。DPに苦手意識がまだある…

上の記事ではなぜ通るのかがあまり解説されていなかったので、なぜ通るか以下に書き下しておく。

DPで解く

この問題はxyあるいはxが最も出現頻度が高くなる(x、yはそれぞれ任意の文字でx != y)。たとえばabcacbacならacが最も出現頻度が高い。

まず、同じ文字が2回以上現れない理由は簡単であろう。なぜならxxyにはxyが2回含まれているため、xxyよりxyのほうが出現頻度が高くなる。

そして、xyzを考えなくて良いかも同様にわかる。xyzにはxyが含まれるのだから、仮にxyzが最も出現頻度が高いとしたら、xyも同じ頻度で現れている。今回の問題は出現頻度さえわかれば良いので、xyだけ着目すればよい。

以上がわかればあとはDPを書くだけとなる。

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using vi = vector<ll>;
template<class T>using vv = vector<vector<T>>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)

int main() {
  string in(S);
  int N = S.size();

  vv<ll> dp(26, vi(26, 0)); // dp[a][b] = abの出現頻度
  vi count(26, 0);
  rep(i, N) {
    rep(j, 26)
      dp[j][S[i]-'a'] += count[j]; // ここまでにjが出た回数ぶん更にふえる
    ++count[S[i]-'a'];
  }
  ll ans = 0;
  rep(i, 26) rep(j, 26)
    ans =max(ans, max(dp[i][j], count[i]));

  cout << ans << endl;

  return 0;
}

2020-04-02

Skyscrapers (hard ver)

codeforces.com

問題概要

簡単に言えば

ある配列が与えられる
ある要素1つを選ぶ
その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす
操作後の配列のうち総和が最大となるときの配列を出力せよ。

C1と同様の問題で、制約のみが異なる。

codeforces.com

解法

C1と同様に、ある要素を選んで実際に配列を構築するやりかたは計算量がO(n²)かかる。今回は制約がn <= 5e5なので通らない。

ある位置を選んだ後、実際に配列を構築するのはO(n)で可能。つまり、今回ネックとなっているのは「どの位置を選ぶべきか？」の判定部分である。

第一感としては累積和でいけそうである。そして実際にそれでいける。

まず、基本的には累積和をとる。ただし、左側に存在する「今見ている要素より大きい要素」は今見ている要素に置き換えて和を求める。この作業はO(n)かかりそうだが(実際最悪かかる)、うまくやると償却計算量がO(1)となる。やり方としてはmapで各要素のカウントを取り、priority queueで出てきた要素の種類を保持すると計算量を落とせる。*1

同様の方法を右側からも行う。こうしてO(n)で左から、右からの累積和を求めることができた。

あとは簡単に答えを求めることが出来る。

左からの累積和、右からの累積和の2つを取る(O(n))
それらを足すことで、ある位置を選んだときの配列の総和を求める(O(1))
総和が最大となる位置を調べる(O(n))

全体としてO(n)となる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;
using ll = long long;

#define in(v) v; cin >> v;
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for(int i=(n);i>=0;--i)

template<class T>bool chmax(T &a,const T &b){if(b>a){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

int main() {
  int in(N);
  vector<int> A(N);
  rep(i, N) cin >> A[i];


  priority_queue<int> q;
  map<int, int> m, m2;
  ll sum = 0;
  vector<ll> sum_l(N+1), sum_r(N+1);
  rep(i, N) {
    // 左から累積和をとっていく
    // ただし、左に存在する要素はすべて今見ている要素以下になるよう調整されているものとする
    sum += A[i];
    ++m[A[i]];
    q.push(A[i]);
    while (!q.empty() && q.top() > A[i]) {
      // このループは最悪計算量はO(n)だが、償却計算量がO(1)
      int p = q.top(); q.pop();
      sum += (ll)m[p] * (A[i] - p);
      m[A[i]] += m[p];
      m[p] = 0;
    }
    sum_l[i+1] = sum;
  }
  sum = 0;
  rrep(i, N-1) {
    // 以下は上のコードのコピペ。右からの累積和を取っているだけ
    sum += A[i];
    ++m2[A[i]];
    q.push(A[i]);
    while (!q.empty() && q.top() > A[i]) {
      int p = q.top(); q.pop();
      sum += (ll)m2[p] * (A[i] - p);
      m2[A[i]] += m2[p];
      m2[p] = 0;
    }
    sum_r[i] = sum;
  }
  int max_i = 0;
  rep(i, N)
    if (chmax(sum, sum_l[i] + sum_r[i])) max_i = i;


  rrep(i, max_i-1) chmin(A[i], A[i+1]);
  rep(i, max_i, N-1) chmin(A[i+1], A[i]);
  rep(i, N) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl;

  return 0;
}

*1:うまく説明できないのだが、このやり方なら最悪計算量はO(n)となる。まあ5, 4, 3, 2, 1のような降順の配列に対する操作を考えていただければ、直感としてはわかっていただけるのではないだろうか。

2020-04-02

Skyscrapers

codeforces.com

問題概要

簡単に言えば

ある配列が与えられる
ある要素1つを選ぶ
その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす
操作後の配列のうち総和が最大となるときの配列を出力せよ。

解法

ある要素を実際に選んでみて操作後の配列を構築して総和を出すやりかたで通した。計算量はO(n²)で、制約がn <= 1000なので通る。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define in(v) v; cin >> v;
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for(int i=(n);i>=0;--i)

template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

int main() {
  int in(N);
  vector<int> A(N);
  rep(i, N) cin >> A[i];

  long long ans = 0;
  int max_i = 0;
  rep(i, N) {
    // A[i]を頂上としたときについて見ていく
    long long sum = A[i];
    int max_A = A[i];
    rep(j, i+1, N) {
      // 右側が単調減少となるようにする
      chmin(max_A, A[j]);
      sum += max_A;
    }
    max_A = A[i];
    rrep(j, i-1) {
      // 左側も右側と同様
      chmin(max_A, A[j]);
      sum += max_A;
    }
    if (ans <= sum) {
      ans = sum;
      max_i = i;
    }
  }

  rrep(i, max_i-1) chmin(A[i], A[i+1]);
  rep(i, max_i, N-1) chmin(A[i+1], A[i]);
  rep(i, N) {
    if (i) cout << " ";
    cout << A[i];
  }
  cout << endl;

  return 0;
}

panda noir 競プロのブログ

1332 C. K-Complete Word

問題概要

入出力

入力

出力

解答

Perfect Keyboard

問題

入出力例

入力

出力

解説

Cow and Message

問題

例

解説

DPで解く

Skyscrapers (hard ver)

問題概要

解法

Skyscrapers

問題概要

解法