AtCoder 勉強記録[C++] その11

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
私のアカウント
解いた問題

本日解いた問題

本日は尺取り法の勉強のためにこちらの記事を参考に問題を解いた。

C - 列

C - 列
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, k;
  cin >> n >> k;
  vec s(n);
  rep(i, n) {
    cin >> s[i];
    if(s[i] == 0){
      cout << n << endl;
      exit(0);
    }
  }
  ll right = 0, res = 0, mul = 1;
  for(int left = 0; left < n; left++){
    while(right < n && mul * s[right] <= k){
      mul *= s[right];
      right++;
    }
    res = max(res, right - left);
    if(left == right) right++;
    else mul /= s[left];
  }
  cout << res << endl;
}

解法

尺取り法を用いて解いていく。数列に0が含まれていた場合、最も長い部分列は与えられた数列と同じになる。

C - 単調増加

C - 単調増加
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n;
  cin >> n;
  vec a(n);
  rep(i, n) cin >> a[i];
  ll right = 1;
  ll res = 0;
  for(int left = 0; left < n; left++){
    while(right < n && (a[right-1] < a[right] || right <= left)){
      right++;
    }
    res += right - left;
    if(right == left) right++;
  }
  cout << res << endl;
}

解法

こちらも尺取り法を用いて解いていく。

B - Takahashi's Failure

B - Takahashi's Failure
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll n, k, tmp;
  cin >> n >> k;
  vec a(n);
  vec b(k);
  rep(i, n) cin >> a[i];
  rep(i, k) cin >> b[i];
  vec c = a;
  sort(c.rbegin(), c.rend());
  string res = "No";
  rep(i, n){
    if(c[0] == a[i]) tmp = i + 1;
    rep(j, k) {
      if(b[j] == tmp) res = "Yes";
    }
  }
  cout << res << endl;
}

解法

おいしさの最大値を求めておき、最大値の食品がBiと一致するかを判定する。一致したらYes、一致しなかったらNoを出力する。

B - Distance Between Tokens

B - Distance Between Tokens
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<pair<ll, ll>> coo(2);
  ll cnt = 0;
  rep(i, h){
    rep(j, w){
      if(s[i][j] == 'o'){
        coo[cnt].first = i;
        coo[cnt].second = j;
        cnt++;
      }
    }
  }
  ll res = abs(coo[1].first - coo[0].first);
  res += abs(coo[1].second - coo[0].second);
  cout << res << endl;
}

解法

二つのoの座標を確保しておき、横方向縦方向両方の差を求めることで移動回数が求まる。

参考文献

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
↑控えめに言って神です