AtCoder ABC381 振り返り
AtCoder Beginner Contest 381 の振り返りです。
今回は珍しく金曜日開催のBeginnerコンテストでした。
配点も150-150-300-425といつもと少し違った回で、問題も文字列操作が続くテーマ性が強い回でした。
C問題で４ペナくらうという痛恨のミスで成績はふるわず。。。
A 11/22 String: Solved
与えられた文字列が「11/22文字列」の条件を満たしているかを判定する問題。
「11/22文字列」は/で区切られた左右対称に前半が'1'で後半が'2'が配置されたような文字列のことで、その条件が問題文中にも与えられている。
問題文中にあった条件を愚直に実装するだけでACできたが、もう少し簡単な解放はあるよなとも思った。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
if (n%2 == 0){
cout << "No" << endl;
return 0;
}
for(int i = 0; i < (n+1)/2-1; i++){
if(s[i] != '1'){
cout << "No" << endl;
return 0;
}
}
if (s[(n+1)/2-1] != '/'){
cout << "No" << endl;
return 0;
}
for(int i = (n+1)/2; i < n; i++){
if(s[i] != '2'){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}B 1122 String: Solved
A問題と同じく、文字列が与えられて「1122文字列」という条件を満たすかを判定する問題。
「1122文字列」は、同じ文字が２個ずつ連続で並んでおり、その文字の種類が重複しないような文字列のことを指す。
２文字ずつ同じ文字が並んんでいることの確認は問題文にもある通り、素直に2i番目と2i+1番目の文字が同じかどうかを確認するだけでよい。
一方で、文字の種類が重複しないことの確認は、文字列をソートして2i+1番目と2i+2が隣り合う文字が異なるかどうかを確認することで実装できた。
文字の種類をasciiコードに置き換えて、文字の種類を数え上げるよりも実装が楽だったけど、計算量はソートによってちょっとかかっていると思う。
提出したコードではソート後にも2i番目と2i+1番目の文字が同じかどうかを確認しているが、これはソート後には確認しなくてもよいということに提出してから気がついた。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
if(s.size()%2 == 1){
cout << "No" << endl;
return 0;
}
for(int i = 0; i < s.size()/2; i++){
if(s[2*i+1] != s[2*i]){
cout << "No" << endl;
return 0;
}
}
sort(s.begin(), s.end());
// ここは不要...
for(int i = 0; i < s.size()/2; i++){
if(s[2*i] != s[2*i+1]){
cout << "No" << endl;
return 0;
}
}
for(int i = 0; i < s.size()/2-1; i++){
if(s[2*i+1] == s[2*i+2]){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}C 11/22 Substring: Solved(4ペナ)
A問題で与えられた「11/22文字列」の条件を満たす最長部分文字列の文字列長を求める問題。
前から/を走査していき、/が現れたらその前後の文字がそれぞれ1と2になっているかを判定していくことで、「11/22文字列」としての部分文字列の長さを数えていき、その最大値を求めた。
ただし、/の１文字のケースを考慮していなかったことと、/の前後の文字を文字長を超えてアクセスしてしまわないかの境界条件を間違えていたことからWAとREを連発してしまい、結果4ペナとなってしまった。
問題が解けた段階では3000位前半だった順位があれよあれよと下がっていき、最終的には3900位台になってしまった。
/の１文字ケースについては考慮漏れと言ったらそこまでだけれど、境界条件のミスについては割と簡単なケース（文字列全体が11/22文字列であるケース）を試していさえすれば、流石に４ペナまではなかったと思うので、焦らずにテストすべしという教訓を得た。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int mx = 0;
if(n == 1){
cout << 1 << endl;
return 0;
}
for(int i=1; i<n-1; i++){
if(s[i] == '/'){
int c = 0;
for(int j=1; j < min(n-i,i+1); j++){
if(s[i-j] == '1' && s[i+j] == '2'){
c++;
} else {
break;
}
mx = max(mx,c);
}
}
}
cout << mx * 2 + 1 << endl;
}所感
今回はいつもよりテーマ性が強い問題が出題されて全体的に文字列判定が中心の問題だった。 これ系の問題は特に苦手意識があるわけではなかったけれど、思い出してみれば競プロを初めて初期の頃、配列の添字を間違えてペナルティを受けることが多かった記憶が蘇ってきた。 競プロはじめてからかれこれ半年ほどになるが、まだまだそのような初歩的なコーディングミスを起こしてしまうのは練習不足なのだろうか。
安定的にC問題が解けるだけでレーティングが上昇しているうちに、D問題が解けるようにならなければと思う今日この頃。