two colors card gameを解くためのメモ

atcoderのコンテンツで勉強を進めていて、練習問題を解いていっています。

しばらく問題文を難しく解釈してしまい、一部の解き方が煩雑になり、プログラムをどうやって作ればいいのか分からず、そこでずっと止まってましたが、そこまで考えなくてよかったみたいなことが何度も問題文読んでいると思えてきたので、そこを無視して作ると解けると思ったので一部を無視して作ってみました。

問題の概要

青いカードがN枚、赤いカードがM枚あって、青いカードの1枚から順番に、以降のカードにかかれている文字列を比べて、同じならカウントを増やしていく。赤いカードにもし青いカードと同じ文字列のカードがあったら、カウントを減らしていく。マイナスになってしまったら0とする。

最後に一番カウントが多いカウント数を出力する。

入力例
3
orange
apple
orange
1
grape

出力例
2

問題を解く上での問題点だと思ったこと

for文のループで青いカードの1枚めと以降のカードを比較して同じ文字列のときはカウントを増やす。2枚めのカードと以降のカードを比べて同じ文字列だったらカウントを増やす。3枚めのカードと以降のカードを比べて同じ文字列だったらカウントを増やす。。。と進めていくと、同じカードが複数あるときに、一度カウントしたカードをまたカウントしカウントがダブってしまうという問題。

例えば、上記の入力例のように、orangeは1枚めと3枚めなのでカウントは2となる。2枚めのカードappleは1枚なのでカウントは1、3枚目のカードはorangeなので、1枚めで既にカウント処理したorangeをまたカウントしてしまうというもの。3枚めのorangeのカウント値は1となる。

でもよくよく考えてみたら、同じカードが複数あるときにカウントをダブっても、同じカードのカウント数は段々少なくなる方向。解答は一番カウント数が多いものを出力するので、別にダブっても問題ないということに気づきました。

青いカード　　　カウント数
apple　　　　　　　3
apple　　　　　　　2
apple　　　　　　　1
赤いカード
orange　　　　　　カウント不要
orange　　　　　　カウント不要

また、青いカードに無くて、赤いカードにある文字列があって、赤いカードのカウント数の多い場合、このカウントを数えて、青いカードのカウント数と赤いカードのカウント数を比較して最大値を出力しないといけないと思い込んでいました。しかもこの処理が難しい。でも、問題文をよく読んでみると、赤いカードは青いカードと同じ文字列があったときカウントをマイナスする役割だけでよさそうだと思いましたので、その方針でソースコードを作成していきました。

問題を解くための処理の流れを文章で作成

# プログラムの流れ
カードの枚数と文字列の入力を促す。
入力する
入力したデータを変数に格納
青いカードの処理
赤いカードの処理
結果の出力
----------------------------------------------------------------------------------

# 処理の詳細
入力したデータを変数に格納
青いカードは変数Nに格納。
入力された文字列は青いカード専用の配列に格納
赤いカードは変数Mに格納
入力された文字列は赤いカード専用の配列に格納

青いカードの処理
カウンタ変数countを作成し0で初期化。
カウンタ変数の値を保存する配列を宣言する。
1枚目のカードと次のカードの文字列を比較し、同じ
だったらカウンターの値を+1増やす。
異なる文字列だったら何もせず次の文字列と比較する。
最後の文字列まで比較が完了したら赤いカードと比較する。
もし同じカードだったらカウンタを1減らす。
異なるカードだったら何もせず次のカードと比較する。
最後のカードまで比較し、カウンタの値をカウンタ変数用の
配列に保存する。
もし、カウンタの値がマイナスの値だったら、カウンタ変数に
0を保存する。

結果の出力
青いカードの最後のカードまで上記の処理が完了したら、
カウンタ変数の配列に格納した要素の最大値を出力
する。最大値の出力は要素をソートして、一番最初の
変数が最大値になるのでそれを出力する。
----------------------------------------------------------------------------------

備考

カードのカウント時、基準となるカードの並び順をiとすると、比較対象のカードは次のカードなのでi+1番めとなる。ここで注意しないといけないのが、i+1>Nとなってしまうと、存在しない添字へのアクセス(範囲を超えている)でエラーになってしまうので、i + 1 < Nのときだけ処理するようにする。

カウンタの値を配列に保存すると、値の個数は青いカードの枚数分になる。値をソートすると小さい順に並ぶので、それを逆に並べると大きい順になる。配列の一番最初の要素が最大値になるのでこれを出力する。

#include <bits/stdc++.h>
using namespace std;
int main() {
       //入力を促すメッセージ　
       cout << "入力してください" << endl;
       //入力を受け取る
       int N, M;
       cin >> N;
       vector<string> blue(N);
       for(int i = 0; i < N; i++){
               cin >> blue.at(i);
       }
       cin >> M;
       vector<string> red(M);
       for(int i = 0; i < M; i++){
               cin >> red.at(i);
       }
//青いカードの処理
       int count = 1;
       //カウンタの値を格納する配列を作成
       vector<int> sum(N);
       //文字列を比較
       for(int i = 0; i < N; i++){
               for(int j = i+1; j < N; j++){
                       if(i+1 < N && blue.at(i) == blue.at(j)){
                               count++;
                       } else {
                               continue;
                       }
               
               //青いカードと赤いカードの比較処理
               for(int k = 0; k < M; k++){
                       if(blue.at(i) == red.at(k)){
                               count--;
                       } else {
                               continue;
                       }
               }

               }
               //カウントが0未満だったらカウントに0を代入
               if(count < 0){
                       count = 0;
               }
               //カウント値を配列sumに格納
               sum.at(i) = count;
               count = 1;
       }
       //sumに格納したカウンタの値を小さい順にソートして順番を逆にすることで最大値が先頭にくるように並び替え
       sort(sum.begin(), sum.end());
       reverse(sum.begin(), sum.end());
       
       cout << sum.at(0) << endl;
       return 0;
}

上記コードでvimで動作確認をして、コメントや入力を促すメッセージなど消して、atcoderの書式に合わせて提出したらなんとか正解となりました。

STLのソート関数とリバース関数を解く直前にatcoderのコンテンツで知ったことが解くポイントになったかと思います。便利なSTLはやっぱりどんどん覚えて使いこなせるようにしたほうがいいかもと思いました。

あと問題文の解釈が少し難しいので、とりあえず解釈した方針で作っていってコードテストして提出して確認するのも大切かもと思いました。