見出し画像

こんなミスをしていてはいつまでも水色になれないよ!


文章書きたい欲を満足させたいと思って書きます。初投稿なので力まず、目標はnoteのエディタに慣れる。
AtCoder - Schoella ( https://atcoder.jp/users/Schoella ) (自己紹介)

右端に注意

ミスを言語化・類型化する趣旨の記事ですが、いきなり言語化につまづきました。

「o」と「-」からなる文字列Sが与えられます。Sの中で最長のお団子の長さを求める問題です。

連続する「o」の個数で最大のものを数えれば良いです。ランレングス圧縮のきもちです。
今見ている団子の長さをcurとして、これを伸ばしていきます。串が来たらcurの更新をやめ、cur = 0にリセットします。

int main(){
    int n; string s; cin >> n >> s;

    // oのみ、-のみ の場合は除いておく
    bool alldango = true, allkushi = true;
    rep(i,n){
        if(s.at(i)=='-') alldango = false;
        else allkushi = false;
    }
    if(alldango || allkushi){
        cout << -1 << endl;
        return 0;
    }

    int ans = -1;
    int cur = 0;
    rep(i,n){
        if(s.at(i)=='o') cur++;
        else{
            chmax(ans,cur);
            cur = 0;
        }
    }

    cout << ans << endl;
 }

(公開したらハイライトが入るみたいですが、編集中だと文字が全てモノクロでめちゃくちゃ見づらい。)

これはダメです。

else{
      chmax(ans,cur);
      cur = 0;
}

この部分。「串が来たら、ans を更新する」という挙動をしますが、正しく動きません。
文字列の末尾が団子だった場合、ansの更新が行われません。S = "-ooo" などで落ちます。

if(s.at(i)!='o'||i==n-1){
      chmax(ans,cur);
      cur = 0;
}

これでACです。

本番は尺取法で書いて、同じようなミスをしました。

(追記 : 
風呂に入ると頭が良くなるものですね。もう少しいいコードを思いつきました。

rep(i,n){
      if(s.at(i)=='o'){
            cur++;
            chmax(ans,cur);
      }
      else cur = 0;
}

団子を串に刺すたびにansを更新します。こうすれば文字列の末尾を例外処理せずに済みます。

この問題は最大長を求めるだけなのでこれで良いですが、ランレングス圧縮をした結果を全て記録するような問題なら、やはり配列の右端の扱いには注意を要しそうです。
追記おわり)


インタラクティブ問題の出力形式に注意

「!」を入れ忘れてWAです。
手元でテストケースをガチャガチャやってるうちにやっちゃいがちなミスです。


まとめ

ABC299の振り返りになってました。
E問題は解けませんでしたが、「どうやったらその解法を思いつくのか」を言語化できたので実りのある復習になりました。

https://twitter.com/akrov5_kyopro/status/1649775725854216192?s=61&t=CxzcDPGk0CHscIIrc4PgpA



Qiitaにこの薄さの記事を出すと怒られそうなので、これからもnoteに投稿するのかな。技術記事なんて到底言えない日記しか書けない。


エディタの機能を使う練習

出典を書くところ


この記事が気に入ったらサポートをしてみませんか?