AtCoderメモ

最近AtCoderで覚えたことをメモします。初心者なのでだいたいAtCoder Beginners Selectionの問題を扱ってます。
https://atcoder.jp/contests/abs

ABC081B - Shift only

標準入力で入力した数値を何回2で割れるか出力する問題

解放1. 配列の要素を全て２で割っていって、最も小さい値をとる
解放2. 配列の各要素を２で割っていき、全ての数値が偶数であれば次回のループを実行し、その要素に１つでも奇数が紛れていればループを中断

解法１

C++.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> arr(n);
  
  for (int i = 0; i < n; i++){
    cin >> arr[i];
  }
  
  int min_power = 30;
  
  for (int i = 0; i < n; i++){
    int count = 0;
    int x = arr[i];
    
    while(x%2 == 0){
      x /= 2;
      count++;
    }
    
    min_power = min(min_power, count);
  }
  
  cout << min_power << endl;
  return 0;
}

解法２

C++.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
  int N;
  int loopCount = 0;
  bool loop = true;
  cin >> N;
  vector<int> num(N);

  for (int i = 0;i < N;i++){
    cin >> num[i];
  }
  while(loop){
    for (int i = 0;i < N;i++){
      if(num[i]%2 != 0){
        cout << loopCount << endl;
        loop = false;
        return 0;
      }
      num[i] /= 2;
    }
    loopCount++;
  }
  
  cout << loopCount << endl;
  return 0;
}

解放２（コンパクト版）

C++.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, cnt = 0;
  cin >> N;
  vector<int> num(N);
  for (int &x : num) cin >> x;

  while (true) {
    for (int &x : num) {
      if (x % 2) {
        cout << cnt << endl;
        return 0;
      }
      x /= 2;
    }
    cnt++;
  }
}

ABC049C - 白昼夢

標準入力で入力した文字列が、「dream dreamer erase eraser」の単語いずれかのみで構成可能かを試す問題
正直一番苦戦した・・・。競技プログラミングやってなきゃこんなコード組まないし大変。

入力した文字列を後ろから、先に示した各単語の文字数文とってきて一致してるか見る

⇒一致してたら同じことする

substrという関数を使います

解法

C++.cpp

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    string words[] = {"dream", "dreamer", "erase", "eraser"};
    
    while(s.size() > 0){
      bool found = false;
      for (string word : words){
        if(s.size() >= word.size() && s.substr(s.size() - word.size()) == word){
          s = s.substr(0, s.size() - word.size());//一致した文字数分切り取る
          found = true;
          break;
        }
      }
      if(!found){
        cout << "NO" << endl;
        return 0;
      }
    }
    
    cout << "YES" << endl;
    return 0;
}

ABC086C - Traveling

マンハッタン距離がわかればそんなに難しくない問題。コードが完成した時はこんなんで解けるのかちょっと信じがたかった

ポイントは前回との距離と時間の差分で到着可能かを判断させる

解法

C++.cpp

#include <iostream>
#include <cmath> // abs() を使うため
using namespace std;

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

    int t_prev = 0, x_prev = 0, y_prev = 0; // 初期位置

    for (int i = 0; i < N; i++){
        int t, x, y;
        cin >> t >> x >> y;

        int dist = abs(x - x_prev) + abs(y - y_prev); // マンハッタン距離
        int time = t - t_prev; // 使える時間

        if (time % 2 != dist % 2 || dist > time) {
            cout << "No" << endl;
            return 0;
        }

        t_prev = t;
        x_prev = x;
        y_prev = y;
    }
    cout << "Yes" << endl;
    return 0;
}

001 - Yokan Party（★4）

既に切り目が設定されている羊羹を定められた回数分割して、長さが最小の羊羹が最大値をとる区切り位置を求めてその最小の長さをこたえる。
ちなみに全然わかんなかった問題。

答えとなる最小の羊羹を仮決めしておき、それが成立するかどうかを判定するbool型の関数を定義して実装した

解法

C++.cpp

#include <iostream>
#include <vector>
using namespace std;

// M 以上の長さのピースを K+1 個作れるか判定
bool canCut(vector<int>& yokan, int N, int L, int K, int M) {
    int count = 0, lastCut = 0;
    for (int i = 0; i < N; i++) {
        if (yokan[i] - lastCut >= M) {
            count++;
            lastCut = yokan[i];  // 切る位置を更新
        }
    }
    // 最後のピースもチェック
    if (L - lastCut >= M) count++;

    return count >= K + 1;  // K回切ってK+1個作れるか
}

int main() {
    int N, L, K;
    cin >> N >> L >> K;
    
    vector<int> yokan(N);
    for (int i = 0; i < N; i++) {
        cin >> yokan[i];
    }
    
    // 二分探索の範囲
    int left = 1, right = L, ans = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;

        if (canCut(yokan, N, L, K, mid)) {
            ans = mid;  // Mを大きくする
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}