色々あってサボってた期間のABCのA問題とB問題埋めをやっていました。
ABC、サボってた期間のA問題とB問題埋め終わり!A,B問題でもずっとやってると頭痛くなってくるな。 pic.twitter.com/jwpYZPmfDB
— やーご (@ateruimashin) May 14, 2020
A問題、B問題でもぶっ通しで解くと疲れます。この後、「もう何もしたくねー」っていう状態でした。
さて、解いた中で、色々と忘れていたことなどがあるのでメモしていきます。
目次
1.Template Matching
ABCのB問題でおそらく最も難しい問題です。やることはわかるけど、どう実装すれば良いのかという難しさです。
多重ループさせて網羅的に解くというのはまあまあありますが、大体2重ループが書ければ実装できます。しかし、この問題は解説のコードだと4重ループです。
3年前にWA出して以来「やりたくねー」ってなってたのですが、埋めるならこれも終わらせなきゃねと自力で書きました。私は解説のコードとは違い、stringの配列を取って、 sbstr()でtemplateと同じ大きさに切り分けてみたいなのを繰り返していました。3重ループで実現できますが、 sbstr()の扱いで迷うので微妙な気がします。
2.double型の剰余
int型ならばa%bで"aをbで割った時の余り"が出せますが、double型の場合は使うことができません。正確には、浮動小数点数の場合は%を使うことができません。そのため、fmod()を使う必要があります。
3.substr()
意外と何度も使った関数。string型から文字列を切り分けれます。ただ、引数がちょっと曲者で、
第1引数が開始位置、第2引数が要素数です。第2引数、終了位置じゃねえのかよ!!
ぶっちゃけこれ使わずに実装するほうがわかりやすいまである。
4.reverse
要素の並びを逆にする関数。もっぱらstring型につかってたので、stringをincludeすれば使えるものだと思ってました。algorithmをincludeする必要があります。
5.回文判定
一時期ABCで回文の問題がやたら出題された時期があります。なんかめんどくさくなったので、文字列を投げたら回文かどうか判定する関数を書きました。
c++
bool kaibun(string s) {
int flag = false;
string s_left, s_right;
if (s.size() % 2 != 0) {
int half_length = s.size() / 2;
int center_right = s.size() / 2 + 1;
s_left = s.substr(0, half_length);
s_right = s.substr(center_right, half_length);
} else {
int half_length = s.size() / 2;
int center = s.size() / 2 - 1;
s_left = s.substr(0, half_length);
s_right = s.substr(center + 1, half_length);
}
reverse(s_right.begin(), s_right.end());
if (s_left == s_right)
flag = true;
return flag;
}
文字数で場合分けして、それぞれ処理しています。それぞれの場合でcenterが変わってしまうのでこうやっていますが、もっとシンプルに実装できそう。愚直に実装するとこうなった感じです。早さの欠片もない。
6.【戒め】デバッグ
WAが出ると、各変数が果たして想定通りになっているのか見たくなります。そういうときに変数を表示させるコードを付け足すのですが、これを消し忘れてWA出したことが何度もありました。
コンテスト中にやったことがないミスをやったので驚きました。ちゃんと確認してから提出しよう!
7.おわりに
貯めるのは良くない。ぶっ通しでやるのもよくない。程々にしましょう。
A,B問題埋めが終わったのでC問題埋めです。ここから緑になれるかどうかが変わってくるので、一つ一つ着実に解いていきたいと思います。