サボってた期間のABCのA,B問題埋め

投稿者: | 2020年5月15日

色々あってサボってた期間のABCのA問題とB問題埋めをやっていました。

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()を使う必要があります。

C++日本語リファレンス fmod

3.substr()

意外と何度も使った関数。string型から文字列を切り分けれます。ただ、引数がちょっと曲者で、

第1引数が開始位置、第2引数が要素数です。第2引数、終了位置じゃねえのかよ!!

ぶっちゃけこれ使わずに実装するほうがわかりやすいまである。

C++日本語リファレンス substr

4.reverse

要素の並びを逆にする関数。もっぱらstring型につかってたので、stringをincludeすれば使えるものだと思ってました。algorithmをincludeする必要があります。

C++日本語リファレンス reverse

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問題埋めです。ここから緑になれるかどうかが変わってくるので、一つ一つ着実に解いていきたいと思います。

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください