No.345 最小チワワ問題｜yukicoder - C++競プロ学習日記(仮)

yukicoderのNo.345 最小チワワ問題が初心者的に大変学習的だった。
もしかしたら3重loopの問題を初めて解いたかも知れないという事で全然解けなかった。
まず3重もあったらloopから抜けられないという事に直面した。
そこで「C++ for loop 抜けられない終了条件」みたいな末期な検索ワードでggると
色々な方法がある事を知り、flagに真偽を持たせてbreakで抜けていくという
画期的な方法を知り得た。(めぐるちゃんのスニペットで一度見ていた事を思い出した)
loopを抜けるだけの練習を個別に多重forで練習した。
サクサク抜けれて楽しかった！！
これで解けるかなーーー！！？ ⇒ 解けない

[リセット]

処理を分割して書く事を教えて貰いました。
特別難しい処理は無い筈なのに、一気に処理を搭載すると書けない...
みたいな私には解りやすかったし、書きやすかったです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int count{0};
    cin >> s;
    int len=s.size();
    for(int i=0; i<len; i++){
        for(int j=i+1; j<len; j++){
            for(int k=j+1; k<len; k++){
                if(s[i]=='c'&&s[j]=='w'&&s[k]=='w'){
                    count++;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

↑まず、問題文からは離れて、c,w,wとなる文字列が何個あるかをカウントするプログラムを書きました。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int temp{0};
    cin >> s;
    int len=s.size();
    for(int i=0; i<len; i++){
        for(int j=i+1; j<len; j++){
            for(int k=j+1; k<len; k++){
                if(s[i]=='c'&&s[j]=='w'&&s[k]=='w'){
                    temp=k-i+1;//神point
                }
            }
        }
    }
    cout << temp << endl;
    return 0;
}

↑次にc,w,wを含む文字列の長さを出力するプログラムを書いた。
文字列の長さと聞けばs.size()で求める方法しか思い浮かばず...
若しくはfindで対象文字の位置を受け取るか...みたいな事を考えていたのですが、
もっと単純な事で良かったみたいです...。
cは左端で、wの2個目は右端...。つまりk-i+1で長さを出す....
chiwawaという文字列があった場合、cはs[ i ]にwはs[ j ]とs[ k ]に入っていて、
iの位置(c)からkの位置(w)で文字列の長さを出したいので、
k-iとなってi自体も含むので+1をして6文字！chiwawa
この問題、これが解らなかったら多分永遠に解けてなかったので神pointと名付けました。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int temp{0},temp2=numeric_limits<int>::max();
    cin >> s;
    int len=s.size();
    bool flag=false;
    for(int i=0; i<len; i++){
        for(int j=i+1; j<len; j++){
            for(int k=j+1; k<len; k++){
                if(s[i]=='c'&&s[j]=='w'&&s[k]=='w'){
                    temp=k-i+1;//神point
                    if(temp2>temp){
                        temp2=temp;
                        flag=true;
                    }
                }
            }
        }
    }
    cout << (flag?temp2:-1) << endl;
    return 0;
}

そして最後に、取得した文字列の長さの最小値を出す処理を追加しました。
min()で返していたのですが返り値がなんか変だったので、
普通にtempに保存して最小値を更新していく形にしました...。
flagに真を持たせて最後場合分けで出力して完成です。

最小値を出すのにtemp2に大きい数を入れておかなくてはいけなくて、
初め適当な数値を入れていたのですが、以前long long intの最大値を入れておくのを
教わった事を思い出したので、intの最大値をnumeric_limits::max();で入れた(成長

この問題、3重loopにifのネストと大変ツラかった...。
実は初めSTLで解いていたのですが、そっちでWAだったので方向転換した。
問題が解けない時は解けないで、色々右往左往しながら脱線して新しい事も覚えるので、
ツラかったけど勉強になりました！！

尚、この記事は単なる私の葛藤の内容だけなので、
正しい解法は作問者のゆらふなさんのページへ。

/*--------------追記--------------*/

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = std::numeric_limits<int>::max();
int main(){
    string s;
    cin >> s;
    const int len=s.size();
    int res = INF;
    for(int i=0; i<len; i++){
        for(int j=i+1; j<len; j++){
            for(int k=j+1; k<len; k++){
                if(s[i]=='c'&&s[j]=='w'&&s[k]=='w'){
                    res= min(res,k-i+1);
                }
            }
        }
    }
    // 初期値である INFのままであることと発見できなかったことは同値
    cout << (res==INF?-1:res) << endl;
    return 0;
}

なんと...！コードを添削、私の書いたコードを活かして(？)
よりスマートにして頂きました。(なので大変理解し易かった...)
私の書いたコードはflagに真を持たせてloopを抜けていたのですが、
その必要がないという...。
min()関数で失敗していた部分もクリアになりました。
あと、constexpr,constなど今まで使った事がなかったのですが、
使った方がコードが読みやすいと教えて頂きました。
(しかしconstexprはちょっと難しかったので今後の課題ですね...)
無駄がない完結なコードを書けるようになりたいなあという感想を持つ今日この頃でした。
ありがとうございました。