こちらへ引き続き、AtCoderのABCへ参加したので、その記録です。
勉強したり聞いたことがあったりするような問題が典型的に出ていたので、はじめてD問題まで解くことができました。
といっても、D問題まで解けている人は多いようでしたので、今後も、多数が解けているものは解けるという状態を維持していきたいです。
さて、では、各問題の回答です。
A - 22222
問題が単純すぎて、一瞬どういうこと？と硬直しましたが、愚直に言われていることをやるだけです。
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
for(int i = 0; i < S.size(); i++) {
if(S[i] != '2') continue;
cout << S[i];
}
}
「2以外の文字を削除する」という言い回しでちょっと混乱した事実がコードに現れています。
つまり、愚直に言われた通りに、「2以外の文字だったら出力を飛ばす」実装をしています。
2分26秒でACです。
B - cat
文字列の長さでソートする方法がわからなかったので、「SiとSjの長さは異なる」「長さは1以上50以下」ということから、長さ1から全探索しました。
与えられた文字列の長さの中に、長さ1はあるかな？→長さ2はあるかな？→長さ3はあるかな？→……という感じです。
たかだが最大50個の文字列なので、この方法でじゅうぶんであると思いました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<string> S(N, "");
for(int i = 0; i < N; i++) {
cin >> S[i];
}
for(int i = 1; i < 51; i++) {
for(int j = 0; j < N; j++) {
if(S[j].size() == i) {
cout << S[j];
}
}
}
cout << endl;
}
解説で読んで、JavaScriptでやるようなsortの自己定義関数できるんだーって知りました。
5分18秒時点でACです。
そういえば、採点システムやコードテストのシステムの動作がなんかもっさりしていたので、途中でpaiza.ioへ移動したのはここら辺でのことだったと思います。
C - Debug
さて、初心者にとってはこの辺からが登山です。
以下にACを得られるまでの、3つのWAとTLEコードを記載していきます。
WAのコード
// WAのコードです
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
while(true) {
auto it = S.find("WA");
if(it == string::npos) break;
S.replace(it, it+2, "AC");
}
cout << S << endl;
}
まだ使い方を理解できていないfindやreplaceを使って、それっぽく実装したところ、WAとなりました。
このコードへ、WAWAWAを与えると、ACACと出力されます。
これは、find()とreplace()の理解が間違っているからです。
まだC++がわかってなくて理解がごっちゃごちゃになっているんですが、stringのfind()はイテレーターではなく、文字列の最初を0とする、位置の整数を返すらしいですね。
ですので、stringのreplace()で、このfind()の結果を使うのであれば、第二引数には置換したい文字列の長さ（整数）を与えるのが正解らしいです。
つまり、S.replace(it, 2, "AC")です。
さて、コンテスト中はこれに気づいていませんが、なんとなく試行錯誤をして、次に以下を提出します。
TLEのコード
// これはTLEのコードです
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
while(true) {
auto it = S.find("WA");
if(it == string::npos) break;
S.replace(S.begin()+it, S.begin()+it+2, "AC");
}
cout << S << endl;
}
理解はしていませんが、イテレーターで範囲を指定するreplace()へ切り替えています。
これで、WAWAWAにはACACACを返します。
ですが、この回答はTLEです。（この時点で13分40秒経過）
でしょうねという気はしていました。
毎回頭から文字列を探索しているため、時間がかかりますから。
ですが、WAとACは一部文字がかぶっているため、置換した結果、今の置換した位置より前に置換するべき文字列が発生する可能性があります。
これを考えて、以下の小細工コードを作成しましたがWAでした。
焦ったせいで、よくわからんコードを書いています。
WAのコード
// これはWAのコードです
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
for(int i = 0; i < S.size(); i++) {
if(S[i] == 'W' && S[i+1] == 'A') {
S[i] = 'A';
S[i+1] = 'C';
i--;
}
}
cout << S << endl;
}
どうしよう……と悩んで、さらにもう一度TLEコードを出したところで、確かこの手の置換問題は後ろから確定していくのが定石だったようなぁという淡い記憶がよみがえります。
そこで、以下のようにしました。
ACのコード
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
// 文字列をひっくり返す
reverse(S.begin(), S.end());
int pos = 0; // findし始める位置を指定する
while(true) {
auto idx = S.find("AW", pos);
if(idx == string::npos) break;
S.replace(S.begin()+idx, S.begin()+idx+2, "CA");
pos = idx; // 今置換した部分は確定したので、findし始める位置を進める
}
// 最後に文字列を元に戻す
reverse(S.begin(), S.end());
cout << S << endl;
}
これで、26分43秒でACです。
各ケースが数ミリ秒で終わっている結果を確認すると、勉強するのって大事だなあと思いました。
D - Colorful Bracket Sequence
これぞ、まさに進研ゼミで勉強したところだ！でした。
この手の問題は確かキューだかスタックだかを使うはずと思い出しますが、ひとまず愚直に書いてみるかあと次の回答を提出。
TLEのコード
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
int flag = 0;
while(true) {
auto idx = S.find("()");
if(idx != string::npos) {
S.replace(S.begin()+idx, S.begin()+idx+2, "");
flag = 0;
}
else {
flag++;
}
idx = S.find("[]");
if(idx != string::npos) {
S.replace(S.begin()+idx, S.begin()+idx+2, "");
flag = 0;
}
else {
flag++;
}
idx = S.find("<>");
if(idx != string::npos) {
S.replace(S.begin()+idx, S.begin()+idx+2, "");
flag = 0;
}
else {
flag++;
}
if(flag == 3) break;
}
if(S.size() == 0) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
findとreplaceを繰り返す遅いコードです。
もちろんTLEになりました。
じゃあ、スタック使おうねえと以下を書いて提出。
WAのコード
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
stack<char> st;
for(auto c: S) {
if(c == '(' || c == '[' || c == '<') {
st.push(c);
}
else {
if(c == '>') {
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
char tmp = st.top();
st.pop();
if(tmp != '<') {
cout << "No" << endl;
return 0;
}
}
if(c == ']') {
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
char tmp = st.top();
st.pop();
if(tmp != '[') {
cout << "No" << endl;
return 0;
}
}
if(c == ')') {
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
char tmp = st.top();
st.pop();
if(tmp != '(') {
cout << "No" << endl;
return 0;
}
}
}
}
cout << "Yes" << endl;
return 0;
}
ACが37件、WAが3件となり、何かもうちょっとだなという手応えがありました。
そこで、丁寧にコードを振り返り、以下のとおり修正します。
修正箇所は最後のほうです。
ACのコード
#include <bits/stdc++.h>
using namespace std;
int main() {
string S;
cin >> S;
stack<char> st;
for(auto c: S) {
// 開き括弧はスタックへプッシュ
if(c == '(' || c == '[' || c == '<') {
st.push(c);
}
else {
if(c == '>') {
// 閉じ括弧が来たのに、スタックが既に空になっていたら、その時点でNoで終了
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
// スタックから取りだして、対応する括弧でなければ、その時点でNoで終了
char tmp = st.top();
st.pop();
if(tmp != '<') {
cout << "No" << endl;
return 0;
}
}
// 以下同様
if(c == ']') {
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
char tmp = st.top();
st.pop();
if(tmp != '[') {
cout << "No" << endl;
return 0;
}
}
if(c == ')') {
if(st.size() == 0) {
cout << "No" << endl;
return 0;
}
char tmp = st.top();
st.pop();
if(tmp != '(') {
cout << "No" << endl;
return 0;
}
}
}
}
// 前回のコードからの修正地点
// スタックが空になっていなければ、括弧の対応がおかしいのでNo！
if(st.size() != 0) {
cout << "No" << endl;
}
else {
cout << "Yes" << endl;
}
return 0;
}
これで、44分37秒でACでした。
以降の問題の印象
これを解く知識は現時点では私にはないと判断し、後は適当にグラフについて勉強しながら時間をつぶしました。
総評
A問題: AC1件
B問題: AC1件
C問題: WA2件、TLE2件、AC1件
D問題: WA1件、TLE1件、AC1件
順位は6400位くらい。
C、D問題でペナルティが多くて順位が落ちたっぽいです。
ペナルティを減らすことも課題かと思いますが、まずは確実にA～C問題が解ける状態を維持することが引き続きの喫緊の課題だと考えています。
優先度的には、二番目の課題がペナルティを減らすことです。
なんにしろ、今回は勉強済みなところが典型的な形で出題されたため、ラッキーだったと思います。
次回は、たぶんまたC問題で四苦八苦しているかと思うので、精進してゆきます。
ここまで読んでいただきありがとうございました。