A - Apple
パターン分け。
計算式は、
N / 3 * Y + N % 3 * X
です。
C++
#include <bits/stdc++.h>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 X, Y, N;
cin >> X >> Y >> N;
if(Y / 3 < X){
cout << N / 3 * Y + N % 3 * X << endl;
}else{
cout << N * X << endl;
}
return 0;
}
B - Explore
mapを使用して、$X_{i}$の部屋になった際、$Y_{i}$を加算する。
C++
#include <bits/stdc++.h>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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, T;
cin >> N >> M >> T;
vector<ll> A(N);
for(int i=0; i<N-1; i++) cin >> A[i];
map<ll, ll> mp;
for(int i=0; i<M; i++){
int x, y;
cin >> x >> y;
mp[x] = y;
}
for(int i=0; i<N; i++){
T += mp[i+1];
T -= A[i];
if(T<=0){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
C - Belt Conveyor
シミュレートします。
無限に続くかは同じルートを通るかにて判断をします。
C++
#include <bits/stdc++.h>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }
char G[510][510];
bool visible[510][510];
int main() {
int H, W;
cin >> H >> W;
for(int i=1; i<=H; i++){
string S;
cin >> S;
for(int j=1; j<=W; j++){
G[i][j] = S[j-1];
}
}
bool ok=false;
int x=1, y=1, cnt=0;
while(!ok){
if(visible[y][x]){
cout << -1 << endl;
return 0;
}
visible[y][x] = true;
if(G[y][x] == 'U' && y != 1){
y--;
}else if(G[y][x] == 'D' && y != H){
y++;
}else if(G[y][x] == 'L' && x != 1){
x--;
}else if(G[y][x] == 'R' && x != W){
x++;
}else{
ok = true;
break;
}
}
cout << y << ' ' << x << endl;
return 0;
}
D - Iroha and Haiku (New ABC Edition)
二分探索と累積和を使用する複数アルゴリズムの問題です。
累積和を使用して$A_x$から$A_{y-1}$までの合計を求めます。
事前に計算量を減らします。
- $A_x$から$A_{y-1}$
- $A_y$から$A_{z-1}$
- $A_z$から$A_{w-1}$
の制約なので、xからwまで連続したインデックスになります。
$A_0$から$A_{x-1}$の加算を行うとP、Q、Rと判定を行いやすくなります。
C++
#include <bits/stdc++.h>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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, P, Q, R;
cin >> N >> P >> Q >> R;
set<ll> st;
st.insert(0);
ll sum = 0;
for(int i=0; i<N; i++){
ll a;
cin >> a;
sum += a;
st.insert(sum);
}
for(auto x:st){
if(st.find(x+P) != st.end() && st.find(x+P+Q) != st.end() && st.find(x+P+Q+R) != st.end()){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}