忍者ブログ

競プロ日記

競技プログラミングの問題を解いた感想を書きます。

[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

配列内で特定の条件を満たす連続する要素を数える
例えば、ABC122 B ATCoderを考える。
文字列を文字の配列とみなし、「要素が'A','C','G','T'のどれかである」という条件を満たす、連続した要素の数の最大値が答えである。
これを実現するコードを2つ乗せる。

方法1
int main(void) {
  string s;
  cin >> s;
  int cnt = 0, maxi = 0;
  // allrep(c, s) = for(auto &&c : s)
  allrep (c, s) {
    if (c == 'A' || c == 'C' || c == 'G' || c == 'T') ++cnt;
    else {
      maxi = max(maxi, cnt);
      cnt  = 0;
    }
  }
  maxi = max(maxi, cnt); // 忘れやすい
  cout << maxi << endl;
  return 0;
}


方法2
int main(void) {
  string s;
  cin >> s;
  int maxi = 0;
  rep (i, s.size()) {
    int start = i;
    while (i < s.size() && (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')) ++i;
    maxi = max(maxi, i - start);
  }
  cout << maxi << endl;
  return 0;
}

最初、方法1で書いていたのだが、これはミスしやすい。
最後にmaxを更新するという操作をあまりに忘れる。
仮に配列内の全ての要素が条件に合っていた場合、maxiは0のままである。
この問題では忘れたまま提出し、久々にB問題でWAを出してしまった。
実はこの間違いは、覚えているだけでもこの問題と合わせて少なくとも3回している。
1つは初コンテスト参加のABC139 C Lower、このミスに気づくのに少し時間を取られてしまった。
もう1つは、まさかのこの問題と同日に解いたABC124 D Handstand、実装中のデバッグ段階で気付いたのでこのミスによるWAはなかったが、そういや初参加のコンテストでミスったなぁと思い出した後のBでのミスである。ひどい。

他人のコードを見て、これは良さそう!となったのが方法2。
for文の中で最後のmaxiの更新も済ませられるため、忘れるということがない!
カウント用の変数や、条件に前の要素が絡んでくる場合に前の要素を保存するための変数等、必要な変数のスコープが抑えられるのもGood。
これを機に間違えづらくてスマートな方法2を使っていくように習慣づけたいと思う。

しかしrange-based forの使い所がどんどんなくなっていく。
添字を使わないループなんて、文字列のループの一部か答えの配列の出力くらいしかなかったのだが、数少ない文字列ループの一部がさらに減ってしまった。
好きなんだけどなぁ、range-based for。
PR

コメント

コメントを書く