나쁘지 않은 결과이다. 다시 민트에 올라왔으니 만족
0:00 ~ 1:30 - A 풀이
역시 구현이다. 오늘은 좀 귀찮은 구현이 나왔다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, m;
string s,t,r;
set<ll> st;
int main(){
fast;
vector<ll> v(8);
for(auto &i : v)cin>>i;
auto e = v;
sort(all(e));
if(v!=e)return cout<<"No",0;
for(int i = 0 ; i < 8 ; i++){
if(100<=v[i] and v[i]<=675 and v[i]%25==0)continue;
return cout<<"No",0;
}cout<<"Yes";
}
1:30 ~ 4:57 - B 풀이
B는 또 뭐가 귀찮은게 많은 구현이다.
시간끌리기 좋은 문제이다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, m;
string s,t,r;
set<ll> st;
ll no;
int main(){
fast;
cin>>n>>m;
map<string, ll> M;
vector<string> v(n);
for(int i = 0 ; i < n ; i++)cin>>v[i];
vector<string> e(m);
for(int i = 0 ; i < m ; i++)cin>>e[i];
cin>>no;
for(int i = 0 ; i < m ; i++){
ll a; cin>>a;
M[e[i]]=a;
}
ll ans = 0;
for(int i = 0 ; i < n ; i++){
if(M.find(v[i])==M.end())ans += no;
else ans += M[v[i]];
}
cout<<ans;
}
4:57 ~ 11:01 - C 풀이
C는 cmp 함수를 통해 그냥 정렬하는 문제
...
처럼 보이나 사실 실수오차를 없애는 방법을 찾는 문제이다.
정렬되었을 때 i<j이면
$$ \frac{A[i]}{A[i] + B[i]} > \frac{A[j]}{A[j] + B[j]}$$
를 만족해야 하므로 (인덱스는 알아서)
$$ A[i] * (A[i]+B[j]) > B[i] * (A[i] + B[i]) $$
를 만족하면 된다.
나눗셈이 곱셈이 되었으므로 실수오차를 없앨 수 있다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n;
typedef pair<pair<ll,ll>,ll> P;
vector<P> v;
bool cmp(P a, P b){
if(a.first.first*b.first.second==b.first.first*a.first.second){
return a.second < b.second;
}
return a.first.first*b.first.second > b.first.first*a.first.second;
}
int main(){
fast;
cin>>n;
for(int i = 0 ; i < n ; i++){
ll a,b; cin>>a>>b;
v.push_back({{a,a+b},i+1});
}
sort(all(v), cmp);
for(auto [a,b] : v)cout<<b<<" ";
}
11:01 ~ 16:51 - D 풀이
그냥 bfs 구현이다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, m;
string s[505];
ll dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
bool visited[505][505];
struct asdf{
ll a,b;
ll idx;
};
queue<asdf> q;
inline ll mod(ll x){ return x%5; }
string snuke = "snuke";
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < n ; i++)cin>>s[i];
if(s[0][0] != snuke[0])return cout<<"No",0;
q.push({0,0,1});
visited[0][0]=1;
while(q.size()){
auto [x,y,idx] = q.front();
q.pop();
if(x==n-1 and y==m-1)break;
for(int i = 0 ; i < 4 ; i++){
ll nx = x+dx[i], ny = y+dy[i];
if(nx<0 or ny<0 or nx>n-1 or ny>m-1)continue;
if(visited[nx][ny])continue;
if(snuke[idx] != s[nx][ny])continue;
visited[nx][ny]=1;
q.push({nx,ny,mod(idx+1)});
}
}
cout<<(visited[n-1][m-1] ? "Yes" : "No");
}
16:51 ~ 31:25 - E 풀이
M,E,X 순서대로 배열되어야 하므로, E를 기준으로 M과 X를 세는 방법을 고려할 수 있다.
P_m[i][j]를 S[i] = 'M', A[i] = j인 prefix sum으로,
P_x[i][j]를 S[i] = 'X', A[i] = j인 suffix sum으로 정의하고,
E의 위치에 따라 m,x의 개수를 조합하여 해결하면 된다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n;
ll a[101010*2];
ll psum_m[202020][3];
ll psum_x[202020][3];
string s;
int main(){
fast;
memset(psum_m, -1, sizeof(psum_m));
memset(psum_x, -1, sizeof(psum_x));
cin>>n;
for(int i = 0 ; i < 3 ; i++)psum_m[0][i] = psum_x[n+1][i] = 0;
for(int i = 1 ; i <= n ; i++)cin>>a[i];
cin>>s; s = '#' + s;
for(int i = 1 ; i <= n ; i++){
if(s[i]=='M'){
psum_m[i][a[i]] = psum_m[i-1][a[i]]+1;
}
for(int j = 0 ; j < 3 ; j++){
if(psum_m[i][j]==-1)psum_m[i][j] = psum_m[i-1][j];
}
}
for(int i = n ; i >= 1 ; i--){
if(s[i]=='X'){
psum_x[i][a[i]] = psum_x[i+1][a[i]]+1;
}
for(int j = 0 ; j < 3 ; j++){
if(psum_x[i][j]==-1)psum_x[i][j] = psum_x[i+1][j];
}
}
ll ans = 0;
for(int i = 2 ; i <= n ; i++){
if(s[i]!='E')continue;
for(int j = 0 ; j < 3 ; j++){
for(int k = 0 ; k < 3 ; k++){
ll mex = 0;
if(a[i]==0 or j==0 or k==0){
mex++;
if(a[i]==1 or j==1 or k==1){
mex++;
if(a[i]==2 or j==2 or k==2){
mex++;
}
}
}
ans += (psum_m[i][j] * psum_x[i][k]) * mex;
}
}
}
cout<<ans;
}
31:25 ~ 43:54 - F 풀이
누가봐도 그리디다.
쿠폰을 매칭시키는 문제인데, 작은 가격의 값부터 보면서 현재 가격에서 가능한 쿠폰을 다 pq에 넣고 큰거부터 빼면 된다.
증명은 나중에 적겠다. 직관적으로 이 방법이 성립하는 이유는, 큰거에서 쓸 수 있는 쿠폰은 자명하게 작은거에서 쓸 수 있는 쿠폰을 모두 쓸 수 있으므로 작은것부터 고려해도 손해를 보지 않는다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
ll n, m;
ll p[202020];
pair<ll,ll> a[202020];
priority_queue<ll> pq;
int main(){
fast;
cin>>n>>m;
for(int i = 1 ; i <= n ; i++)cin>>p[i];
sort(p+1, p+n+1);
for(int i = 1 ; i <= m ; i++)cin>>a[i].first;
for(int i = 1 ; i <= m ; i++)cin>>a[i].second;
sort(a+1, a+m+1);
ll idx=1;
for(int i = 1 ; i <= n ; i++){
while(idx<=m and a[idx].first <= p[i]){
pq.push(a[idx].second);
idx++;
}
if(pq.empty())continue;
p[i] -= pq.top();
pq.pop();
}
ll ans = 0;
for(int i = 1 ; i <= n ; i++)ans += p[i];
cout<<ans;
}43:54 ~ 100:00 - G 풀이 고민
f(x) := 현재 상태에서 xor을 x 이하로 할 수 있는가? 를 생각할 때,
M[i]를 i번 비트부터 29번 비트까지만 고려할때의 값이라 하면 M[i]에서 합이 2^(비트수)-2^i 꼴인 값이 존재할때 XOR값이 2^i 이하임을 이용해서 해결하려고 했으나, 구현이 복잡하여 하지 못했다.
공식 풀이는 인접한 원소에서만 최솟값이 나옴을 증명해서 구하는 것 같다.
다시 민트로 왔으니 블루까지 쭉 올라가야겠다.
