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最高じゃないかと思った。