草体にぼ日記

だらだらと

2020年3月25日　日記

毎日

2020年3月25日

　まえがき

ウーン, APG4bまたやり始めようかな。

今日はなんかQiitaがやらかしたみたいな話が話題に上がっていますね。
それと関連してちょっと、自分のサイト持ちたいな〜って思っています。
wordpressとかgithub pagesっていう言葉は聞くのですが、よく分かりません。
HTMLやCSSでサイトを作ったとして、とりあえずそこに置くことができれば自分のサイトを持てたということが出来るんですかね？

まぁ、なんとなくどんなサイトにするかは頭の中にあるので、あとで図にします。

今日解いた問題

Indeedなう(予選B) B- 高橋くんと文字列操作
[文字列,文字列の比較]
起きたのが23:40だったのでAtCoderProblemsのRecommendationのeasyを解きましたが、中々に手応えがありました。
今回の問題では文字列sのサイズが1000以下だったので、1000回問題文のように操作をしても間に合うだろうな〜ってことで1000回pop_backしてACしました。
が、ちょっと計算量調べないとやべえな。って思ったので計算量だけ少し整理します。
そもそもの僕の提出コードは以下です。

int main()
{
    string s, t;
    cin >> s >> t;
    if(s == t){
        cout << 0 << endl;
        return 0;
    }
    int count = 1;
    while(count < s.size() + 100){ // 余裕持って100回多くループ回しといた
        string ns ="";
        ns += s[s.size() - 1]; // nsの末尾にs[s.size()-1]を足すのはO(1)(多分）;
        s.pop_back(); // 末尾を消すのは確かO(|S|)
        ns += s; // O(|S|)かなあ？
        if(ns == t){ // 比較は O(|S|);
            cout << count << endl;
            return 0;
        }
        count ++;
        s = ns;
    }
    cout << -1 << endl;
}

コンな感じですかね？3秒ぐらいcpp referenceを見に行ったけど、計算量知りたいときってどこ見たら分かるんだろ。まじで文字列の計算量頭に入ってないからそろそろ入れ直さないとな。 でまぁ、上のコードは|S|回ループを回すのと、その中で3|S|回くらいだからO(|S|^2)で|S|=1000でも間に合う。
でもまぁ、ちょっとゴリゴリすぎるよねってことで書いてあった解説の解き方 もみておこう。
sを2つつなげた文字列をs'とすると、0回操作したときの文字列はs'.substr(|s|-0,|s|); i回操作したときの文字列はs'.substr(|s|-0,|s|)
これを使えば計算量が明らかに落ちるね！！

　あとがき

ウーン、特に無い。今日は結構ダラダラしてたよ。

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)