ARC097の振り返り

久しぶりにプログラミングコンテストに参加。

今回は、AtCoder Regular Contest 097 - AtCoder Regular Contest 097 | AtCoder に。

AtCoderのコンテストは初めての参加ですが、結果は、C,D解けて、E,F解けず。1回しか参加してないのでまだ灰色ですが、5回コンテストに参加するとちゃんとレーティングが算出され見合ったカラーになるようです。

C - K-th Substring

Sの部分文字列から辞書順でK番目に小さい値を探す。

部分文字列を総当りしていくと日が暮れるので制約の小さいKに着目。K文字以上は探索しなくて良いので後はささっと実装する。

int main(int argc, char *argv[]) {
  string s;
  int k;
  cin>>s>>k;
  int now=0;
  set<string> ststr;
  for (int i=0;i<30;i++){
    char c = 'a' + i;
    for (int j=0;j<s.size();j++){
      if (s[j] == c){
        for(int j2=1;j2<=5;j2++){
          if (j+j2>s.size())break;
          ststr.insert(s.substr(j, j2));
        }
      }
    }
    if (ststr.size() > k)break;
  }
  string ans=*std::next(ststr.begin(), k-1);
  cout<<ans<<endl;
  return 0;
}

本番では律儀にaから順番に探索していた。

D - Equals

交換可能なindex、値をUnionFindでつないでいく。 操作回数は無制限なので、値と目的のindexが同じツリーにいるものをカウントしていく。 indexはそのままいれると値とバッティングするので200000とか足しておく。

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool connect(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool isSame(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

UnionFind uf = UnionFind(400030);

int main(int argc, char *argv[]) {
  int n,m;cin>>n>>m;
  for(int i=0;i<n;i++){
    int t;
    cin>>t;
    uf.connect(t, i + 200000);
  }
  for(int i=0;i<m;i++){
    int t1,t2;
    cin>>t1>>t2;
    uf.connect(200000 + t1 -1, 200000 + t2 -1);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(uf.isSame(i+1, 200000+i))ans++;
  }
  cout<<ans<<endl;

  return 0;
}

最初、UnionFindの確保サイズ小さすぎてRuntime Errorが起きてしまった。+5分のペナルティ。

E - Sorted and Sorted

なんか蟻本に似たようなのあったな〜と思いつつ解けずに死亡。

F - Monochrome Cat

そっ閉じした。

感想

問題自体がかなりシンプルでわかりやすく、それでいて奥が深いので練習にも最適な感じがしました。 使える言語多いし、日本語の問題だし、日本語の解説もあるし、AtCoder最高じゃないかと思った。