[AtCoder]ABC 044 – 美しい文字列 ~ 046 [C++]

プログラミング

引き続き、B問題を解いていきます。やはり、A問題のようにサクサクはいきませんね〜。

ABC B044 – 美しい文字列

問題

wを、英小文字のみからなる文字列とします。 wが以下の条件を満たすならば、wを美しい文字列と呼ぶことにします。

  • どの英小文字も、w中に偶数回出現する。

文字列 wが与えられます。wが美しい文字列かどうか判定してください。

自分の回答

#include <bits/stdc++.h>
using namespace std;

int main() {
  string w;
  cin >> w;

  for (int i = 0; i < w.length(); i++) {
    if(count(w.begin(), w.end(), w[i]) % 2 != 0){
      cout << "No" << endl;
      exit(0);
    }
  }
  cout << "Yes" << endl;
}

forで一文字ずつ取り出して、count関数を使って、対象となる文字が含まれる個数が偶数か奇数かを判断すればいいですね。一回でも”No”となったら、そこでプログラム終了させるために、exit関数を使っています。

exit関数
exit関数はプログラムを終了させる関数です。return 0と書いても結果的には一緒になります。

count関数
count(変数名.begin(), 変数名.end(), ‘数えたい対象’)という形で使います。
ただし、変数の型はstring型でないと使えないので注意です。

ABC 045B – 3人でカードゲームイージー

問題

A さん、B さん、C さんの3人が以下のようなカードゲームをプレイしています。

  • 最初、3人はそれぞれ a、b、c いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた順番に持っており、途中で並べ替えたりしない。
  • Aさんのターンから始まる。
  • 現在自分のターンである人がカードを1枚以上持っているならば、そのうち先頭のカードを捨てる。その後、捨てられたカードに書かれているアルファベットと同じ名前の人 (例えば、カードに a と書かれていたならば A さん) のターンとなる。
  • 現在自分のターンである人がカードを1枚も持っていないならば、その人がゲームの勝者となり、ゲームは終了する。

3人が最初に持っているカードがそれぞれ先頭から順に与えられます。 具体的には、文字列 SA、SB、SCが与えられます。文字列 SAの ii 文字目 ( 1≤i≤|SA|) に書かれている文字が、Aさんの持っている中で先頭から ii 番目のカードに 書かれている文字です。文字列 SB、 SCについても同様です。最終的に誰がこのゲームの勝者となるかを求めてください。

自分の回答

#include <bits/stdc++.h>
using namespace std;

int main() {
  string SA, SB, SC;
  cin >> SA >> SB >> SC;

  string turn = "a";

  while(1) {
    if(turn == "a"){
      if(SA.length() == 0){
        cout << "A" << endl;
        exit(0);
      }
      turn = SA[0];
      SA.erase(0,1);
    }else if(turn == "b"){
      if(SB.length() == 0){
        cout << "B" << endl;
        exit(0);
      }
      turn = SB[0];
      SB.erase(0,1); 
    }else if(turn == "c"){
      if(SC.length() == 0){
        cout << "C" << endl;
        exit(0);
      }
      turn = SC[0];
      SC.erase(0,1);
    }
  }
}

解くのに時間がかかってしまいました。

変数turnは誰のターンかを判別するのに使います。問題文より、最初はAさんから始まるので、”a”を代入しています。そして、その人の持っている先頭のカードがその都度代入されます。turn = SA[0];としているところですね。
その後、erase関数を使って先頭のカードを削除しています。
注意するのは、lengthを使って長さが0かどうかを確認して勝者を出力していますが、先頭カードのturnへの代入や削除の前に、この操作を行うことです。勝者になるためには、カードが0になったタイミングではなく、カードが0になった状態で、もう一度自分のターンが回ってこないといけません。なので、eraseの後にif文でlengthを確認してまうと、0になったタイミングで勝者判定を出してしまい、間違いとなります。
また、新しい要素として、while(1)というものが出てきましたね。

while(1)
while文の応用的な使い方。無限ループさせています。条件式は、成立した時には1、不成立の時は0を返すので、初めから条件式のところに1を書いておけば、常に条件が成立し、無限ループさせることができます。
処理の中の、exit(0);と書いている部分でループから抜け出しています。今回の場合は、いずれかの文字列が0となった時に、exit(0);で抜け出します。

ABC B046 – AtCoDeerくんとボール色塗り

問題

シカのAtCoDeerくんは一列に並んだN個のボールをそれぞれK色のペンキの色のうちのどれかで塗ろうとしています。見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。ボールの塗り方としてあり得るものの個数を求めてください。

自分の回答

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;

  cout << int(K * pow(K - 1, N - 1)) << endl;
}

端から塗っていくと考えると、一番最初のボールにはどのペンキも塗れるのでK通りとなります。次からのボールは前に塗ったペンキ以外なので、K-1通りです。次のボールも同じようにK-1通りの塗り方があります。問題となるのは、直前に塗ったペンキの色だけですので、最初以外はK-1通りの塗り方があり、それが全体のボールから1引いた分、つまりN-1個あります。
よって、答えはK * K-1^N-1となります。pow関数を使えばいいですね。
ただし、pow関数は小数で返してくるので、整数型の指定をしましょう。指定をしないと、NとKの値が大きくなった場合、答えが3.22829e+08というふうに表示され、間違いになります。

ABC B047 – すぬけ君の塗り絵 2 イージー

問題

xy平面上に、左下の座標が(0,0)、右上の座標が(W,H)で、各辺がx軸かy軸に平行な長方形があります。最初、長方形の内部は白く塗られています。
すぬけ君はこの長方形の中にN個の点を打ちました。i個目(1≦i≦N)点の座標は(xi,yi)でした。
また、すぬけ君は長さNの数列aを決めて、各1≦i≦Nに対し、

  • ai=1のときは長方形のx<xiをみたす領域
  • ai=2のときは長方形のx>xiをみたす領域
  • ai=3のときは長方形のy<yiをみたす領域
  • ai=4のときは長方形のy>yiをみたす領域

を黒く塗りました。
塗りつぶしが終わったあとの長方形内での白い部分の面積を求めてください。

自分の回答

#include <bits/stdc++.h>
using namespace std;

int main() {
  int W, H, N;
  cin >> W >> H >> N;
  int x, y, a;

  int w[] = {0,W};
  int h[] = {0,H};

  for (int i = 0; i < N; i++) {
    cin >> x >> y >> a;
    if(a == 1){
      w[0] = max(w[0], x);
    }else if(a == 2){
      w[1] = min(w[1], x);
    }else if(a == 3){
      h[0] = max(h[0], y);
    }else if(a == 4){
      h[1] = min(h[1], y);
    }
  }

  if(w[1] - w[0] > 0 && h[1] - h[0] > 0){
    cout << (w[1] - w[0]) * (h[1] - h[0]) << endl;
  }else{
    cout << 0 << endl;
  }
}

まず、白いエリアのx軸とy軸の初期値を用意しておきます。
次に、aの値によって処理を変えていきます。例えば、aが1だった場合、xよりも小さいところが削られるので、現在のx軸の下限値w[0]とxを比べて、大きい方を残します。そうすることで、黒く塗られた部分を除外することができます。aが2だった場合、xよりも大きいところが削られるので、現在のx軸の上限値w[1]とxを比べて、小さい方を残します。
最後に、場合によっては上限値と下限値の差がマイナスになる可能性があるので、どちらも正の値の時に、計算結果を出力します。

タイトルとURLをコピーしました