백준 풀다가 할 게 없어서 대회가 있길래 참여했다.
체감 난이도 : A<C<B<D<F<E<G<H<I
A - 스케이트보드
풀이 : 구현
n번동안 2개, 5개 나눠서 입력받은 후 각각 최댓값을 구하면 된다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n;
int main(){
fast;
cin>>n;
ll ans=0;
while(n--){
vector<ll> v(2), e(5);
for(auto &i : v)cin>>i;
for(auto &i : e)cin>>i;
sort(rll(v)), sort(rll(e));
ans = max(ans, v[0]+e[1]+e[0]);
}
cout<<ans;
}
B - 회장님께 바치는 합성함수
풀이 : 수학(고등수학 이상), 많은 조건 분기
일단 합성함수를 직접 전개해보자.
$$ f(x) = ax^{2}+bx+c, g(x) = dx+e $$
라 하면,
$$ f(g(x)) = adx^{2}+bdx+cd+e $$
$$ g(f(x)) = ad^{2}x^{2}+(2ade + bd)x+ae^{2}+be+c $$
이다. 이제 이 둘의 관계를 따지면 된다.
f(x)-g(x)=0 꼴로 나타냈을 때,
$$ 0x^{2} + 0x + 0 $$ 이면 교점은 무수히 많다.
일차식 이하라면 일차항의 계수가 0일 때 0개, 0이 아닐 때 1개이다.
그 외 이차식이라면 판별식 $$ D = b^{2}-4ac $$ 의 부호를 이용하면 된다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n;
int main(){
fast;
ll a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
ll A = a*d*d, B = 2*a*d*e + b*d, C = a*e*e + b*e + c, D = a*d, E = d*b, F = c*d + e;
A-=D, B-=E, C-=F;
if(A==0 and B==0 and C==0)return cout<<"Nice",0;
if(A==0){
if(B==0){
cout<<"Head on";
return 0;
}
cout<<"Remember my character";
return 0;
}
ll DD = B*B-4*A*C;
if(DD<0)return cout<<"Head on", 0;
if(DD>0)return cout<<"Go ahead", 0;
cout<<"Remember my character";
}
C - 더하기
풀이 : ad_hoc
짝수번째 값과 홀수번째 값을 골라 더했을 때 일어나는 변화를 관찰하자.
짝수번째 값을 모두 더한 값을 S_even, 홀수번째 값을 모두 더한 값을 S_odd라 하자.
- 짝수번째 값을 고르면, S_even이 1 증가하고 S_odd가 2 증가한다.
- 홀수번째 값을 고르면, S_odd가 1 증가하고 S_even이 2 증가한다.
따라서 diff = |S_even - S_odd|라 할 때,
S_even > S_odd이면 짝수번째 값만 diff번 고르면 된다.
S_even < S_odd이면 홀수번째 값만 diff번 고르면 된다.
따라서 답은 |S_even - S_odd|가 된다.
이제 불가능한 경우를 생각해보자. N=3이라면, 짝수번째 값밖에 고를 수 없게 된다. 따라서 N=3이면서 S_even < S_odd이면 홀수번째 값을 고를 수 없기 때문에 S_even은 절대 S_odd 이상의 값이 될 수 없으므로 불가능한 경우가 된다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n;
ll s1, s2;
int main(){
fast;
cin>>n;
for(int i = 0 ; i < n ; i++){
ll a; cin>>a;
if(i&1)s1+=a;
else s2+=a;
}
if(n==3){
if(s1<s2)return cout<<-1, 0;
}
cout<<abs(s1-s2);
}
D - 카더가든
풀이 : 브루트포스
위 3가지 경우를 모두 따져주면 된다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n, m;
ll arr[303][303];
ll a,b,c;
bool safe(ll x, ll y){
if(x<1 or y<1 or x>n or y>m)return 0;
return 1;
}
ll sum1(ll x, ll y){
if(!safe(x+a-1,y+b+c-1))return 1e18;
ll ret=0;
for(int i = x ; i < x+a ; i++){
for(int j = y ; j < y+b+c ; j++)ret += arr[i][j];
}
return ret;
}
ll sum2(ll x, ll y){
if(!safe(x+a+b-1, y+a+c-1))return 1e18;
ll ret = 0;
for(int i = x ; i < x+a ; i++){
for(int j = y ; j < y+c ; j++)ret += arr[i][j];
}
for(int i = x+a ; i < x+a+b ; i++){
for(int j = y+c ; j < y+a+c ; j++)ret += arr[i][j];
}
return ret;
}
ll sum3(ll x, ll y){
if(!safe(x+a+c-1, y+a+b-1))return 1e18;
ll ret = 0;
for(int i = x ; i < x+a ; i++){
for(int j = y ; j < y+b ; j++)ret += arr[i][j];
}
for(int i = x+a ; i < x+a+c ; i++){
for(int j = y+b ; j < y+a+b ; j++)ret += arr[i][j];
}
return ret;
}
int main(){
fast;
cin>>n>>m>>a>>b>>c;
for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= m ; j++)cin>>arr[i][j];
ll ans = 1e18;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
ans = min({ans, sum1(i,j), sum2(i,j), sum3(i,j)});
}
} cout<<ans;
}
E - 곱하기와 쿼리
풀이 : 정수론
x = A_i*A_j이므로 A_i, A_j는 x의 약수이다.
x는 1억 이하이며 쿼리가 5000개이므로 x의 약수를 일일히 구하여 따져볼 수 있다.
먼저 x가 0인 경우는 따로 처리하도록 하자.
x의 어떤 약수를 p라고 할때, p가 배열 A에 존재하는지와 x/p가 A에 존재하는지만 따지면 된다.
이떄 p*p=x이면 p가 배열 A에 2개 이상 존재하는지를 따지면 된다.
업데이트 쿼리는 삭제밖에 없고 A의 값은 10000 이하이므로, cnt[10000] 배열을 이용해서 존재 여부를 O(1)에 따질 수 있으므로 문제를 해결할 수 있다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n, q;
ll chk[10101];
bool iszero;
int main(){
fast;
cin>>n>>q;
vector<ll> v;
for(int i = 0 ; i < n ; i++){
ll a; cin>>a;
chk[a]++;
v.push_back(a);
}
while(q--){
ll a, b; cin>>a>>b;
if(a==1){
if(b==0){
cout<<iszero<<"\n";
continue;
}
vector<ll> p;
for(ll i = 1 ; i*i <= b ; i++){
if(b%i==0){
if(i*i<b)p.push_back(b/i);
p.push_back(i);
}
}
sort(all(p));
bool f=0;
for(int i = 0 ; i < p.size() ; i++){
if(p[i]*p[i]==b){
if(chk[p[i]]>=2){
f=1;
break;
}
}
else if(p[i]<=10000 and b/p[i]<=10000 and chk[p[i]]>0 and chk[b/p[i]]>0){
f=1;
break;
}
}
cout<<f<<"\n";
}
else{
iszero=1;
chk[v[b-1]]--;
v[b-1]=0;
}
}
}
F - XOR 카드 게임
풀이 : DP
가져가는 순서가 정해지지 않은 줄 알고 어려운 문제라고 생각했으나, 입력 순서대로 가져간다는 조건이 있어서 아주 간단한 DP로 풀린다.
dp[i] := i번 카드까지 가져갈 때 얻을 수 있는 최대 점수
dp[i] = max(dp[i-2] + f(a[i] ⊕ a[i-1]), dp[i-3] + f(a[i] ⊕ a[i-1] ⊕ a[i-2])) (i>2)
dp[i] = dp[i-2] + f(a[i] ⊕ a[i-1]) (i=2)
dp[i] = 0 (i<2)
f(i) := i를 이진수로 표현할 때 1의 개수
⊕는 xor이다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll dp[101010];
ll n;
vector<ll> v;
ll f(ll x){
if(x>n)return -1e18;
if(x==n)return 0;
ll &ret = dp[x];
if(~ret)return ret;
ret = max(f(x+2)+__builtin_popcount(v[x]^v[x+1]), f(x+3)+__builtin_popcount(v[x]^v[x+1]^v[x+2]));
return ret;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
v.push_back(0);
v.push_back(0);
v.push_back(0);
memset(dp,-1,sizeof(dp));
cout<<max(0LL,f(0));
}
G - 게임
풀이 : dfs + cycle 판정
i -> f(i)로 가는 간선을 잇는 outdegree가 최대 1인 그래프를 고려하자.
f(i) > 10^5이면 간선을 잇지 않는다고 생각하자.
g(i)에 정의에 따라 아래와 같은 결론을 내릴 수 있다.
1. i에서 출발하여 자기 루프가 생기는 정점으로 갈 수 있다면 g(i) = 1이다.
2. i에서 출발하여 자기 루프를 타지 않고 자기 자신으로 돌아올 수 있다면 g(i) = 0이다.
3. i에서 출발하여 사이클이 생기지 않고 탐색을 끝낼 수 있다면 g(i) = -1이다.
f(i)는 O(1)에 구할 수 있고, i는 1~10^5까지 dfs로 g(i)를 총 O(10^5)에 판별할 수 있으므로 문제를 해결할 수 있다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll l, r;
vector<ll> adj[101010];
inline ll f(ll x){
string s = to_string(x);
ll r1 = 0, r2 = 1;
for(auto i : s)r1 += i-'0', r2 *= (i-'0');
string s1 = to_string(r1), s2 = to_string(r2);
return stoll(s1+s2);
}
void make_edge(){
for(int i = 1 ; i <= 100000 ; i++){
if(f(i)<=100000)adj[i].push_back(f(i));
}
}
bool visited[101010];
bool finished[101010];
ll g[101010];
ll dfs(ll x){
visited[x]=1;
if(adj[x].empty()){
g[x] = -1;
finished[x]=1;
return -1;
}
ll next = adj[x][0];
if(visited[next]){
if(!finished[next]){
if(x==next)g[x]=1;
else g[x]=0;
finished[x]=1;
return g[x];
}
finished[x]=1;
return g[x] = g[next];
}
else{
g[x]=dfs(next);
finished[x]=1;
return g[x];
}
}
int main(){
fast;
make_edge();
for(int i = 1 ; i <= 100000 ; i++)if(!visited[i])dfs(i);
cin>>l>>r;
ll ans=0;
for(int i = l ; i <= r ; i++){
ans += g[i];
}
cout<<ans;
}
H - 의리 게임
풀이 : lazy propagation segment tree + parametric search
원래 유니온 파인드를 이용한 풀이를 생각하려 했으나, 확신이 들지 않아서 레이지 세그먼트 트리를 이용했다.
세그먼트 트리의 각 리프노드는 그 사람이 현재 마실 수 있는 술의 양을 나타낸다.
의리 게임을 i번에서 x리터를 가지고 시작해서 j번에서 끝났다고 하자. 이때 i~j-1번은 술을 더 이상 마실 수 없는 상태임이 자명하다. 따라서 i~j-1번 구간을 0으로 업데이트 해주면 된다. 그 전에 세그먼트 트리 상에서 i~j-1 구간의 합을 s라 하자. j번 사람은 x-s리터만큼 술을 마셨으므로 세그먼트 트리상에서 x-s를 빼주면 된다.
이제 남은 것은 의리게임을 i번에서 시작했을 때, 몇번에서 끝나는지를 빠르게 판별해주면 된다. 어떤 k(k>=i)에 대하여, 세그먼트 트리에서 i~k 구간의 합이 x 이하라면 적어도 k까지는 게임이 진행되었음을 알 수 있다. 따라서 의리게임이 끝났을때 번호인 j를 이분탐색으로 구할 수 있다. i~k 구간의 합은 O(logN)에 구할 수 있으므로 이분탐색을 O(log^2N)에 수행할 수 있고, i~j 처리는 위 문단처럼 O(logN)에 해줄 수 있으므로 O(Qlog^2N)에 해결할 수 있다.
using namespace std;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n, q;
struct lazyseg{
struct Node{
ll diff, lazy;
};
vector<Node> tree;
lazyseg(): tree(404040) {}
void propagate(ll node, ll s, ll e){
if(!tree[node].lazy)return;
auto [diff, lazy] = tree[node];
tree[node].diff = 0;
if(s!=e)tree[node*2].lazy = 1, tree[node*2+1].lazy = 1;
tree[node].lazy=0;
}
void upd(ll node, ll s, ll e, ll l, ll r, ll diff){
propagate(node,s,e);
if(e<l or r<s)return;
if(l<=s and e<=r){
tree[node].diff = 0;
if(s==e)return;
tree[node*2].lazy =1;
tree[node*2+1].lazy =1;
return;
}
ll mid = s+e>>1;
upd(node*2, s, mid, l, r, diff); upd(node*2+1, mid+1, e, l, r, diff);
tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
}
void upd2(ll node, ll s, ll e, ll idx, ll diff){
propagate(node,s,e);
if(idx<s or e<idx)return;
if(s==e){
tree[node].diff += diff;
return;
}
ll mid = s+e>>1;
upd2(node*2,s,mid,idx,diff); upd2(node*2+1,mid+1,e,idx,diff);
tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
}
ll query(ll node, ll s, ll e, ll l, ll r){
propagate(node,s,e);
if(e<l or r<s)return 0;
if(l<=s and e<=r)return tree[node].diff;
ll mid = s+e>>1;
return query(node*2,s,mid,l,r)+query(node*2+1,mid+1,e,l,r);
}
} seg;
bool chk(ll l, ll r, ll x){
if(seg.query(1,1,n,l,r) >= x)return 1;
return 0;
}
ll arr[101010];
int main(){
fast;
cin>>n>>q;
for(int i = 1 ; i <= n ; i++){
ll a; cin>>a;
arr[i]=a;
seg.upd2(1,1,n,i,a);
}
while(q--){
ll a,b,c; cin>>a>>b;
if(a==1){
cin>>c;
if(seg.query(1,1,n,b,n)<c){
seg.upd(1,1,n,b,n,0);
continue;
}
ll l = b-1, r = n+1;
while(l+1 < r){
ll mid = l+r>>1;
if(chk(b,mid,c))r = mid;
else l = mid;
}
swap(l,r);
seg.upd2(1,1,n,l,-(c-seg.query(1,1,n,b,l-1)));
if(b<=l-1)seg.upd(1,1,n,b,l-1,1);
}
else{
cout<<arr[b]-seg.query(1,1,n,b,b)<<"\n";
}
}
}
I - 점수 계산하기
풀이 : dfs + LCA
새로 루트가 될 정점을 newroot, 점수를 계산할 정점을 v라 하자.
(i)newroot에서 root로 가는 경로 사이에 v가 없다
핑크색 정점이 v이다. newroot와 원래 루트 사이 경로에 v가 없다면, v의 서브트리는 변하지 않으므로 점수도 변하지 않음을 알 수 있다. 따라서 원래 루트에서의 점수를 그대로 출력하면 된다.
(ii)newroot에서 root로 가는 경로 사이에 v가 있다
newroot가 루트에 있다고 하면, newroot->root 사이에 v가 존재하므로, v가 root의 조상이 된다. 반대로 원래 v는 newroot의 조상이었지만 이제는 newroot가 조상이 되었다. 따라서 원래 v의 자식 중 newroot를 포함하는 자식의 점수를 빼주면 된다. 그냥 쉽게 말해서,
빨간색 삼각형(전체 트리)의 점수 - 파란색 삼각형(서브트리가 newroot를 포함하는 v의 자식)의 점수가 답이 된다.
newroot의 점수를 빼는 것이 아닌, v의 자식 중 newroot를 포함하는 정점의 점수를 빼줘야 한다.
이제 v의 자식 중 newroot를 포함하는 정점을 빠르게 찾으면 되는데, v의 자식을 next라 할 때 next와 newroot의 lca가 next이면 됨을 알 수 있다.
(iii)v=newroot
v가 새로운 루트가 되므로 원래 루트의 점수를 출력하면 된다.
이제 (i), (ii), (iii)을 판별하면 된다. (iii)은 바로 처리되므로 일단 제외하고, (i)과 (ii)만 구별하면 된다. 잘 생각해보면, (ii)의 경우 newroot와 v의 lca가 v임을 알 수 있다. 따라서 lca(v,newroot)=v이면 (ii)로, v=newroot이면 (iii)로, 아니면 (i)로 처리하면 된다.
각 정점에서의 점수는 dfs로 쉽게 구할 수 있다.
#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;
typedef long long ll;
#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
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n, m;
ll depth[101010];
vector<ll> adj[101010];
bool visited[101010];
ll par[101010][22];
ll score[101010];
ll w[101010];
void dfs(ll x, ll y){
visited[x]=1;
score[x] = w[x];
for(auto next : adj[x]){
if(!visited[next]){
depth[next] = y+1;
par[next][0]=x;
dfs(next, y+1);
score[x] += score[next];
}
}
}
ll lca(ll a, ll b){
if(depth[a]<depth[b])swap(a,b);
ll diff = depth[a]-depth[b];
for(int i = 0 ; i < 20 ; i++){
if(diff&(1<<i))a = par[a][i], diff -= (1<<i);
}
if(a==b)return a;
for(int i = 20 ; i >= 0 ; i--){
if(par[a][i]!=par[b][i])a = par[a][i], b = par[b][i];
}
return par[a][0];
}
int main(){
fast;
cin>>n>>m;
for(int i = 1 ; i <= n ; i++)cin>>w[i];
for(int i = 0 ; i < n-1 ; i++){
ll a,b; cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
for(int j = 1 ; j <= 20 ; j++){
for(int i = 1 ; i <= n ; i++){
par[i][j] = par[par[i][j-1]][j-1];
}
}
while(m--){
ll newroot, v; cin>>newroot>>v;
if(newroot==v){
cout<<score[1]<<"\n";
continue;
}
if(lca(newroot, v) != v){
cout<<score[v]<<"\n";
continue;
}
for(auto next : adj[v]){
if(par[v][0]==next)continue;
if(lca(next,newroot)==next){
cout<<score[1]-score[next]<<"\n";
}
}
}
}
'백준' 카테고리의 다른 글
| Solved.ac Arena - 2023 충남대학교 SW-IT Contest Open - Division 1 (0) | 2023.09.18 |
|---|---|
| 단대소프트고 2023 알고리즘 대회 (작성중) (0) | 2023.09.09 |
| solved.ac 다이아 3 달성 (2) | 2023.09.01 |
| BOJ 1739 - 도로 정비하기 (0) | 2023.05.21 |
