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を考える。A
、B
、i
の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;
}
解法
右手と左手の位置を記憶しておく変数ri
、le
を用意する。両手の初めの位置を記録しておく。初めの位置からどれだけ動いたかを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]
となる場合をカウントする。カウントした値を毎回答えに加算することで結果が求まる。