[C++]AtCoder Beginner Contest 158を解いてみた(A~D)

プログラミング

AtCoder Beginner Contest 158に参加しました。C問題までは解けましたが、D問題が解けませんでした。もう少し時間があれば、解けたのですが、C問題に時間をかけすぎました、、、。

A – Station and Bus

問題

AtCoder市には3つの駅があり、1,2,3の番号がつけられています。
これらの駅は、それぞれ鉄道会社A, Bのいずれかが管理しています。管理状況は長さ3の文字列Sで表され、駅iはSiがAのとき鉄道会社 A が、Bのとき鉄道会社Bが管理しています。
鉄道会社Aが管理している駅と、鉄道会社Bが管理している駅の間には、交通の便のためにバスを運行することになりました。
実際にバスが運行することになる駅の組み合わせが存在するかどうかを判定してください。

自分の回答 

#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;

  if(count(S.begin(), S.end(), 'A') == 0 && count(S.begin(), S.end(), 'B') == 0){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
}

バスが運行するのはA→BまたはB→Aと並んだ時なので、文字列SにAとBどちらも含まれていればバスは運行することになります。なので、文字列Sが全て同じなら”No”を出力、それ以外の時は”Yes”を出力すればいいですね。

B – Count Balls

問題

高橋君は青と赤の2色のボールを持っており、これらを一列に並べようとしています。
初め、列にボールはありません。
根気のある高橋君は、次の操作を10^100回繰り返します。

  • 列の末尾に、A個の青いボールを加える。その後、列の末尾にB個の赤いボールを加える。

こうしてできる列の先頭からN個のボールのうち、青いボールの個数はいくつでしょうか。

自分の回答 

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

int main() {
  long int N, A, B;
  cin >> N >> A >> B;

  long int set = N / (A + B);
  long int amari = N % balls;

  if(amari <= A){
    cout << A * set + amari << endl;
  }else{
    cout << A * set + A << endl;
  } 
}

まずは、列Nの中に、赤と青のセットがいくつ含まれるかを求めます。これは、N/(A+B)で求まり、変数setとします。
次に、セットから溢れたボールの中にブルーが何個含まれているかを求めます。これは青いボールの数Aと余ったボールの数(amari)の大小関係によって場合分けします。
もし、余ったボールの数がA以下なら、余ったボールは全て青になります。なので、Aにset数をかけたものに、余ったボールの数を足せばいいです。
もし、余ったボールがAよりも大きい場合(amari > A)、余ったボールの中には赤のボールが含まれるということなので、青ボールの数Aを足します。

C – Tax Increase

問題

消費税率が8%のときA円、10％のときB円の消費税が課されるような商品の税抜き価格を求めてください。
ただし、税抜き価格は正の整数でなければならないものとし、消費税の計算において小数点以下は切り捨てて計算するものとします。
条件を満たす税抜き価格が複数存在する場合は最も小さい金額を出力してください。また、条件を満たす税抜き価格が存在しない場合は -1 と出力してください。

自分の回答 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  
  for(int i = 1; i < 1010; i++){
    int ans_A = i * 0.08;
    int ans_B = i * 0.1;
    if((ans_A == A) && (ans_B == B)){
      cout << i << endl;
      exit(0);
    }
  }
  cout << "-1" << endl;
}

解けてしまえば、とても簡単な問題ですが、すごく時間を取られてしまいました。
int型を宣言して、計算した後にA、Bと比較すればいいですね。int型で宣言すれば、小数点以下は自動で切り捨ててくれます。これをif文のところで、if(i * 0.08 == A)みたいに書いてしまうと、左辺が小数となり、いつまでも一致しないので”-1″が出力されてしまいます。これで自分は時間を取られてしまいました。
for文のiの範囲をi < 1010としているのは、1010円の消費税10%が101円となり、制約のB<=100に引っかかるからです。なので、iは1010未満にしておけば、十分かなという判断です。正しいかはわかりません。

D – String Formation

問題

高橋君は、英小文字から成る文字列Sを持っています。
このSから始めて、ある与えられた手順に従って文字列を作ることにしました。
手順はQ回の操作から成ります。操作 i(1≤i≤Q)では、まず整数Tiが与えられます。

  • Ti=1のとき : 文字列Sの前後を反転する。
  • Ti=2のとき : 追加で整数Fiと英小文字Ciが与えられる。
    • Fi=1のとき : 文字列Sの先頭にCiを追加する。
    • Fi=2のとき : 文字列Sの末尾にCiを追加する。

高橋君のために、手順の後に最終的にできる文字列を求めてあげてください。

自分の回答 (誤)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int Q;
  cin >> Q;
 
  for(int i = 0; i < Q; i++){
    int T;
    cin >> T;
    if(T == 1){
      reverse(S.begin(), S.end());
    }else if(T == 2){
      int F;
      string C;
      cin >> F >> C;
      if(F == 1){
        S.insert(0,C);
      }
      else if(F == 2){
        S.insert(S.size(),C);
      }
    }
  }
  cout << S << endl;
}

まずは、誤回答から見ていきましょう。問題文通りの条件をコードで書いていくと、上記のようになります。これでも例題は解け、正解を出力してくれます。初めてD問題まで解けた!と思って嬉しくなったのですが、提出すると実行時間超過となり、不正解となります、、、。

自分の回答(正)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int Q;
  cin >> Q;
  int count = 0;
  string front = "";
  string back = "";
 
  for(int i = 0; i < Q; i++){
    int T;
    cin >> T;
    if(T == 1){
      count += 1;
    }else if(T == 2){
      int F;
      string C;
      cin >> F >> C;
      if(count % 2 == 0){
        if(F == 1){
          front.insert(0,C);
        }
        else if(F == 2){
          back.insert(back.size(),C);
        }
      }else{
        if(F == 1){
          back.insert(back.size(),C);
        }
        else if(F == 2){
          front.insert(0,C);
        }
      }
    }
  }
  // 文字列Sに結合
  S.insert(0,front);
  S.insert(S.size(),back);
  
  // T==1の回数に応じて、そのままか反転するか判断
  if(count % 2 == 0){
    cout << S << endl;
  }else{
    reverse(S.begin(), S.end());
    cout << S << endl;
  }
}

実行時間を減らすために、コードを改善しました。
まず、文字列の反転は最後のみにします。その代わり、T=1となった時の回数をカウントするために変数countを用意しました。
また、文字列Sへの文字の挿入も最後にまとめて行います。そのために、文字列Sの先頭に挿入するものをfront、後ろに挿入するものをbackとそれぞれ用意して、状況に応じて、それぞれに挿入していきます。ただし、今文字列Sが反転しているかどうかで、front、backどちらに挿入するか場合分けをしなくてはいけないので、countを使って、文字Cを振り分けます。ここの場合わけがこの問題のキモですね。
文字Cのfront、backへの振り分けが終わったら、文字列Sに結合します。
最後に、T=1となった回数に応じて、文字列Sがそのままか、反転するかを場合分けして出力します。

感想

A、B問題はサクサク解けました。しかし、C問題でとても時間を取られてしまいました。そんなに難しい問題ではなかったので、もったいないですね。D問題も時間があれば解けたので、惜しかったです。
C、D問題は正解が出るコードを書けても、実行時間超過になってしまうことが多いです。この辺は、問題を多くといて、テクニックを身につけていくしかないのかなと思っています。

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