A - Equally
O(1)
Aの配列を昇順にソートします。
A_0 + A_1 = A_2
A_0 = A_1 = A_2
の時にYesです
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int n = 3;
vector<int> v(n);
rep(i, n) cin >> v[i];
sort(v.begin(), v.end());
if(v[2] == v[1] + v[0] || v[2] == v[1] && v[1] == v[0]){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
B - Santa Claus 1
O(N)
シミュレートしましょう。
Tの文字列の通りにパターン分けして座標を更新します。
'@'を探索した時、'.'へ更新して一度のみの判定にしましょう。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int H, W, X, Y;
cin >> H >> W >> X >> Y;
X--; Y--;
vector<string> S(H);
rep(i, H) cin >> S[i];
string T;
cin >> T;
int ans = 0;
rep(i, T.size()){
int nx = X, ny = Y;
if('U' == T[i]) nx--;
if('D' == T[i]) nx++;
if('L' == T[i]) ny--;
if('R' == T[i]) ny++;
if(S[nx][ny] == '#') continue;
X = nx, Y = ny;
if(S[X][Y] == '@'){
S[X][Y] = '.';
ans++;
}
}
cout << X+1 << ' '<< Y+1 << ' ' << ans << endl;
return 0;
}
C - Illuminate Buildings
多分O(N^2)
最初の２つの等間隔に並んでいるビルを探索します。
２つのビルを基準に、等間隔に並んでいるビルを探索します。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
vector<int> H(N);
rep(i, N) cin >> H[i];
int ans = 1;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
if(H[i] == H[j]){
int cnt = 2;
int d = j - i;
while(j+d < N && H[j+d] == H[i]){
d+=j-i;
cnt++;
}
ans = max(ans, cnt);
}
}
}
cout << ans << endl;
return 0;
}
D - Santa Claus 2
O(MlogN)
x軸を基準に家を管理するデータ構造w、y軸のを基準に家を管理するデータ構造hを用意します。
map<long long, set<long long>>のデータ構造が適しています。
二分探索で、移動する直線上の要素を探索します。
w, hのデータ構造から要素を削除し、カウントを計測します。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
ll n, m, sx, sy;
cin >> n >> m >> sx >> sy;
map<ll, set<ll>> h, w;
rep(i, n){
ll x, y;
cin >> x >> y;
w[x].insert(y);
h[y].insert(x);
}
ll x = sx, y = sy;
ll ans = 0;
rep(i, m){
char d;
ll c;
cin >> d >> c;
if('U' == d){
ll dy = y + c;
auto l = w[x].lower_bound(y);
while(l != w[x].end() && *l <= dy){
h[*l].erase(x);
l = w[x].erase(l);
ans++;
}
y = dy;
}
if('D' == d){
ll dy = y - c;
auto l = w[x].lower_bound(dy);
while(l != w[x].end() && *l <= y){
h[*l].erase(x);
l = w[x].erase(l);
ans++;
}
y = dy;
}
if('L' == d){
ll dx = x - c;
auto l = h[y].lower_bound(dx);
while(l != h[y].end() && *l <= x){
w[*l].erase(y);
l = h[y].erase(l);
ans++;
}
x = dx;
}
if('R' == d){
ll dx = x + c;
auto l = h[y].lower_bound(x);
while(l != h[y].end() && *l <= dx){
w[*l].erase(y);
l = h[y].erase(l);
ans++;
}
x = dx;
}
}
cout << x << ' ' << y << ' ' << ans << endl;
return 0;
}