0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Posted at

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

本日解いた問題

本日はAtCoder Beginner Contest 369に参加した。しばらくコンテストに参加できていなかったが集中して取り組むことができ、C問題まで解くことができた。また、勉強した尺取り法を使用してコーディングできたので勉強の成果を感じた。

A - 369

A - 369
解答

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

int main() {
  ll a, b;
  cin >> a >> b;
  ll res = 0;
  for(int i = -1000; i <= 1000; i++){
    if(b-a==i-b) res++;
    else if(i-b==a-i) res++;
    else if(a-i==b-a) res++;
  }
  cout << res << endl;
}

解法

1<=A,B<=100であるため、-1000から1000までの整数iを考える。ABiの3種類の並び方において、問題の条件が成り立つかを確認する。

B - Piano 3

B - Piano 3
解答

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

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<char> s(n);
  rep(i, n) cin >> a[i] >> s[i];
  ll le = 0, ri = 0;
  ll res = 0;
  rep(i, n) if(s[i] == 'L') {
    le = a[i];
    break;
  }
  rep(i, n) if(s[i] == 'R') {
    ri = a[i];
    break;
  }
  for(int i = 0; i < n; i++){
    if(s[i] == 'L') {
      res += abs(le - a[i]);
      le = a[i];
    } else if(s[i] == 'R'){
      res += abs(ri - a[i]);
      ri = a[i];
    }
  }
  cout << res << endl;
}

解法

右手と左手の位置を記憶しておく変数rileを用意する。両手の初めの位置を記録しておく。初めの位置からどれだけ動いたかをresに加算していき、現在の位置を更新する。

C - Count Arithmetic Subarrays

C - Count Arithmetic Subarrays
解答

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

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  vector<ll> dif(n-1);
  for(int i = 0; i < n-1; i++){
    dif[i] = a[i+1] - a[i];
  }
  ll res = n;
  ll ri = 0;
  for(int le = 0; le < n-1; le++){
    ll cnt = 1;
    while(ri < n-1){
      if(dif[le] == dif[ri]) {
        res+=cnt;
        cnt++;
        ri++;
      }else {
        break;
      }
    }
    if(ri==le) ri++;
  }
  cout << res << endl;
}

解法

A[i+1]-A[i]を記憶しておく配列difを用意する。r,lが同値の場合は必ず等差数列になるため、答えにあらかじめNを加算しておく。その後、尺取り法を用いてdifの要素の0からN-1までの間でdif[i+1]=dif[i]となる場合をカウントする。カウントした値を毎回答えに加算することで結果が求まる。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?