文系ギャルが0から始める競技プログラミング#16

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#15

・参考書籍

最近はiPad買ったので蟻本を読んでいます。
初心者向きではなかったね…。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

まだまだ何言ってるの？状態なところもありますが、コレを読んで優勝していきたいと思います。
わたしレベルにちょうどいいアルゴリズムの本があったらぜひ教えてください！
どっちかっていうと考え方を鍛えたい時期。

・ABC124C - まだ文字列を扱う回

4/25 23:16加筆:
この問題は嘘解法で通していました！！！！！！！
#17で訂正します 。

問題文
左右一列にN枚のタイルが並んでおり、
各タイルの初めの色は長さNの文字列Sで表されます。
左からi番目のタイルは、Sのi番目の文字が0のとき黒色で、1のとき白色で塗られています。
あなたは、いくつかのタイルを黒色または白色に塗り替えることで、
どの隣り合う2枚のタイルも異なる色で塗られているようにしたいです。
最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

制約
1≤|S|≤10^5
Siは0または1である。

入力
入力は以下の形式で標準入力から与えられる。
S

出力
条件を満たすために塗り替えるタイルの枚数の最小値を出力せよ。

どうやるのがスマートなんだろう？とりあえず行けそうだったので文字列で乗り切ります。
どの隣り合う二枚のタイルも異なる色で塗られている状態ということなので、
1.01がいっぱい並んだものをまず作り、
2.始まりによって照合スタートの位置を決めて
3.違うものをカウントする
という戦法でいきます。

1はstringで足し算していくと文字列に追加されていくようなので、とりあえず文字数分作っておきます。倍あるけど。

   size_t size = S.size();
   
   //01をいっぱい作る
   string trueans = "01";
   for(int i=0;i<size;i++){
       trueans = trueans+"01";

2と3はざっくり分岐させて中でループします。

   int ans = 0;
   if(S[0]=='0'){
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i]){
               ans++;
           }
       }
   }else{
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i+1]){
               ans++;
           }
       }
   }

手元にあるtrueansは01010101...なので、
1から始まるパターンの場合はi+1番目がS[i]とあっているかどうかでカウントしました！！！！！

実行時間610msだったので危なっかしい？ですが、C++は早いからいけるって最近覚えたぞ〜〜〜

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   string S;
   cin >> S;
   
   size_t size = S.size();
   
   //01をいっぱい作る
   string trueans = "01";
   for(int i=0;i<size;i++){
       trueans = trueans+"01";
   }
   int ans = 0;
   if(S[0]=='0'){
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i]){
               ans++;
           }
       }
   }else{
       for(int i=0;i<size;i++){
           if(S[i]!=trueans[i+1]){
               ans++;
           }
       }
   }
   cout << ans << endl;
   return 0;
}

天才ムーブが板についてきました。
優勝！！！！！！！！！！！！！！！！！！！！！

・ABC049C - How to 正規表現

詰まっていたAtCoder Beginners Selectionの問題に再チャレンジします！

問題文
英小文字からなる文字列Sが与えられます。
Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことでS=Tとすることができるか判定してください。
Tの末尾に'dream' 'dreamer' 'erase' 'eraser'のいずれかを追加する。

制約
1≦|S|≦10^5
Sは英小文字からなる。

ぐぐりまくっていたら、正規表現というのがあるみたいです。

今回はこれを活用していきます。
regexというのを使うと正規表現を指定できそう。

regex re("[dream|dreamer|erase|eraser]*");

これで、指定の文字列のどれかが0個以上あるかどうか…なので、

   if(regex_match(S,re)){
       cout << "YES" << endl;
   }else{
       cout << "NO" << endl;
       
   }

それが与えられた文字列SにマッチするかどうかでYESかNOかを出力します。
あれ？優勝じゃね？？？？？

#include <iostream>
#include <algorithm>
#include <string>
#include <regex>
using namespace std;
int main()
{
   string S;
   cin >> S;
   
   regex re("[dream|dreamer|erase|eraser]*");
   
   if(regex_match(S,re)){
       cout << "YES" << endl;
   }else{
       cout << "NO" << endl;
       
   }
   return 0;
}

詰まっていたんですが先に進めました！！！！！！！！！！
優勝！！！！！！！！！！！！敗北を知りたい！！！！！！！

また一つ賢くなってしまいました。
優勝祝いにタピオカとラーメンをいただいてしまい太る一方…♡
今日はちゅんすいたんの普通のミルクティー！

もっとスマートな方法があるよ、ここ解釈違うよ、はぜひTwitterやコメントで教えてください！
（リスト随時更新しています！！！いつもありがとう〜〜！）

Outro

#17に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。