현재 가채점 결과가 나왔다.
중간에 충전선에 아이패드가 걸려서 카메라가 넘어진 것 때문에 부정행위에 걸리지 않는 이상 3위는 고정일듯 하다.
타임라인 1줄요약
1->2->3긁기->4긁기->3->4긁기
아래부터 나와있는 풀이의 내용은 오류가 있을 수 있다. (부등호 실수, 조건 빠뜨림 등등?)
0:00 ~ 8:26 : 1번 해결 +100점
1번은 문제해석이 중요하다. 문제의 조건을 다 보지 않으면 예제 2의 답이 이상하게 느껴지기 때문이다.
문제를 요약하면 다음과 같다.
스케이트를 속력 0에서 시작하여, N개의 지점에서 아래와 같은 속력 조건에 맞춰 속력을 조정한 후 마지막에는 속력 0으로 끝날 때, 각 부분에서의 속력의 합의 최댓값은? (=N개의 지점에서의 속력의 합)
조건 1 : 배열 A = (a1, a2, a3, ..., an)에 대하여 i번 지점에서의 속력은 ai 이하이다.
조건 2 : 다음 지점으로 넘어갈 때 속력은 임의의 값만큼 올릴 수 있고, 낮출 때는 1씩만 가능하다.
이 문제에서 빠뜨리기 쉬운 조건은 속력 0에서 시작하고 0으로 끝난다는 것이다.
어쨌든 조건을 보면 생각하기 은근 까다롭다는 것을 알 수 있다. 여기서 반대로 생각해보자.
마지막 지점에서 출발하여, 첫번째 지점에서 속력 0으로 끝난다고 해보자. 그럼 조건 2를 다음과 같이 바꿀 수 있다.
조건 2 : 다음 지점으로 넘어갈 때 속력은 1만큼 올릴 수 있고, 낮출 때는 임의의 값만큼 가능하다.
이렇게 바꾸면 편리한 점은, 속력을 임의의 값만큼 낮출 수 있으므로 다음 지점으로 건너갈 때 속력이 속력 제한보다 크면, 그냥 속력 제한값으로 바꾸면 된다. 따라서 간단한 그리디 문제가 되며, 쉽게 해결 가능하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
vector<ll> v;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
reverse(v.begin(), v.end());
ll ans = 0;
ll cur_v = 0;
for(int i = 0 ; i < n ; i++){
cur_v = min(cur_v+1, v[i]);
ans += cur_v;
}
cout<<ans;
}1번은 solved.ac 기준 실버로 예상된다.
8:26 ~ 20:38 : 2번 해결 +100점
2번은 간단한, 그리고 한번쯤 풀어봤을? 유형의 dp 문제이다.
인접한 곳을 고를 수 없고, 원형이라는 점에서 https://www.acmicpc.net/problem/2482와 유사하다. (물론 약간 다르다.)
2482번: 색상환
첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.
www.acmicpc.net
일단 마지막 위치를 생각하지 않고 그냥 선형 배열이라고 치자.
i번째 개미굴 위치에 있을 때, 고를 수 있는 방법은 다음과 같다.
1. 방 하나를 고른다. (단, i>1일때 i-1번 위치에서 방을 고르지 않고 쪽방을 골랐어야 한다.)
2. 쪽방을 모두 고른다. (모두 고르는 이유는 자명하다.)
따라서 다음과 같은 dp 배열을 고려한다.
dp[i][j] := i번 위치에서 이전 위치에서 방을 골랐는지, 쪽방을 골랐는지에 대한 bool 값이 j일때, 가능한 최댓값
1,2번을 고려하면 식은 쉽게 나온다. 이제 원형만 고려해 주면 되는데, 그냥 2차원을 3차원 dp로 바꾸면 된다.
dp[i][j][k] := i번 위치에서 이전 위치에서 방을 골랐는지, 쪽방을 골랐는지에 대한 bool 값이 j이고, j=1일때의 bool 값은 k일때, 가능한 최댓값
k가 추가된 이유는 마지막 n번 위치에서 방을 고를때는 1번 방이 영향을 주기 때문이다.
아래 코드는 0-index이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll dp[252525][3][2];
ll n;
vector<ll> v;
ll f(ll x, ll is_1, ll is_prv){ //is_k가 1 : 이전에 쪽방, 0 : 이전에 방
ll &ret = dp[x][is_1][is_prv];
if(~ret)return ret;
ret = 0;
if(x==n-1){
if(is_1 and is_prv){ //1, n-2 모두 쪽방=>어디든 가능
ret = max(v[x], 1LL);
return ret;
}
else{ //그 외 : 쪽방만 가능
ret = v[x];
return ret;
}
}
if(x==0){
ret = max(f(x+1, 1, 1)+v[x], f(x+1, 0, 0)+1);
}
else if(is_prv){
ret = max(f(x+1, is_1, 1)+v[x], f(x+1, is_1, 0)+1);
}
else ret = f(x+1, is_1, 1)+v[x];
return ret;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
memset(dp, -1, sizeof(dp));
cout<<f(0,0,0);
}
2번은 boj 2482와 비슷한 티어인 G4~G3정도로 예상된다. (solved.ac 티어 기준)
작년보다 1,2번이 훨씬 쉬웠다. 작년 1번은 등차수열을 이용한 브루트포스(G5), 2번은 트리의 성질을 이용한 union-find + nC2(P5)였다.
그에 비해 이번 1,2번은 훨씬 간단한 것 같다.
20:38 ~ 40:31 : 3번 Subtask#1 해결 (S#1 : N,M≤1000) +5점
3번은 일단 문제 해석이 힘들었다. 꼬치를 왜 하필 +0.1이랑 +0.9에 꽃게 해놨는지도 모르겠다. 그냥 낚시인듯 하다.
(어차피 주어지는 점들의 좌표가 정수기 때문에, +0.1이든 +0.9든 +(π-3)이든 다 똑같다.)
문제를 보기 좋게 정리하면 다음과 같다.
0~10^9 사이 수직선에 직선 N개가 있다. 각 직선은 weight를 가진다.
그 후 M개의 쿼리가 주어지는데, 각 쿼리는 점 2개로 이루어진다.
구간 [l,r]을 가지는 어떤 직선이, 좌표가 x인 점에 대하여 l≤x이고 x<r을 만족하면, 이 점은 이 직선에 포함된다고 하자.
1≤i≤N인 직선 i에 대하여, 직선 i가 주어진 점 중 정확히 1개를 포함하면, 그 직선은 그냥 사라진다.
직선 i가 주어진 점 중 정확히 2개를 포함하면, 그 직선은 weight를 주고 사라진다.
각 쿼리에서 지워진 직선들은 그 이후 쿼리에서도 지워진 상태가 유지된다.
이때 각 쿼리에서는, 점 2개를 포함해서 사라진 직선들의 weight 합을 출력하면 된다.
(모든 좌표는 정수, 1≤N,M≤250,000)
정리가 왜 이렇게 긴지는 모르겠지만, 대충 이해는 될 것이다. 보자마자 이 문제는 바로 풀기는 힘들겠다고 생각이 들어, 서브태스크를 긁기로 했다.
문제를 이해했다면, Subtask#1은 그냥 구현임을 알 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll n, m;
vector<pair<pair<ll,ll>,ll>> v;
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < n ; i++){
ll a,b,c; cin>>a>>b>>c;
v.push_back({{a,b},c});
}
while(m--){
ll a,b; cin>>a>>b;
vector<ll> chk(n+1, 0);
ll ans = 0;
for(int i = 0 ; i < n ; i++){
auto [ran, w] = v[i];
auto [l,r] = ran;
if(l<=a and a<r)chk[i]++;
if(l<=b and b<r)chk[i]++;
if(chk[i]>0){
v[i].first.first=v[i].first.second=-1;
if(chk[i]==2)ans += w;
}
}
cout<<ans<<"\n";
}
}
40:31 ~ 54:08 : 3번 Subtask#2 해결 (S#2 : 각 직선이 차지하는 구간 크기는 5 이하이다.) +9점
각 직선이 포함하는 좌표가 최대 N*5개기 때문에, 각 직선이 포함하는 좌표를 그냥 저장하고, 점이 주어질때마다 그 좌표에 직선이 있는지를 확인하고, 직선을 삭제할 수 있으면 된다. 좌표압축을 하지 않고, 그냥 std::map같은 자료 구조에 넣으면 쉽게 구현할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll n, m;
map<ll, set<ll>> mp;
vector<ll> v;
ll chk[252525];
pair<ll,ll> li[252525];
int main(){
fast;
cin>>n>>m;
v.resize(n);
ll c = 0;
for(auto &i : v){
ll a,b; cin>>a>>b;
li[c]={a,b};
cin>>i;
for(int j = a ; j < b ; j++)mp[j].insert(c);
c++;
}
while(m--){
ll a,b; cin>>a>>b;
set<ll> s;
ll ans=0;
for(auto e : mp[a]){
chk[e]++;
s.insert(e);
}
for(auto e : mp[b]){
if(s.find(e)!=s.end()){
ans += v[e];
}
chk[e]++;
s.insert(e);
}
for(auto i : s){
for(int j = a-6 ; j <= a+6 ; j++){
if(mp[j].find(i)!=mp[j].end())mp[j].erase(i);
}
for(int j = b-6 ; j <= b+6 ; j++){
if(mp[j].find(i)!=mp[j].end())mp[j].erase(i);
}
}
cout<<ans<<"\n";
}
}
54:08 ~ 64:03 : 3번 Subtask#3 해결 (S#3 : i번 직선은 i-1번 직선 구간에 포함된다.) +11점
Subtask#3은 그림으로 보면 어떤 상황인지 바로 알 수 있다.
색에 의미는 없다. 어쨌든 위와 같은 형태기 때문에, 알 수 있는 사실은 다음과 같다.
어떤 위치 x에 존재하는 점에 의하여 i번 직선이 삭제된다면, i-1번 직선도 삭제된다. (i>1)
pf)i번 직선의 구간은 [L_i, R_i]이고, i-1번 직선의 구간은 [L_i-1, R_i-1]이다. 이때 L_i-1<L_i, R_i-1>R_i인데, L_i≤x<R_i이므로, L_i-1≤x<R_i-1는 자명해진다.
i번 직선이 삭제된다면 i-1번 직선이 삭제된다? 이는 i번 직선이 삭제된다면 연쇄적으로 1번 직선까지 삭제된다는 것임을 알 수 있다.
따라서 어떤 점에 의하여 삭제되는 직선의 최대 번호만 구하면 되므로, 파라메트릭 서치를 고려하자.
f(x, y) := x번 직선이 y위치의 점에 의하여 삭제되는가?
이는 O(1)에 판별 가능하고, 이분탐색으로 x의 최댓값을 찾을 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll n, m;
map<ll, set<ll>> mp;
vector<ll> v;
pair<ll,ll> li[252525];
ll M;
ll chk(ll x, ll p){
if(M>=x)return 1;
if(li[x].first<=p and p<li[x].second)return 1;
return 0;
}
int main(){
fast;
cin>>n>>m;
v.resize(n);
ll c = 0;
for(auto &i : v){
ll a,b; cin>>a>>b;
li[c]={a,b};
cin>>i;
c++;
}
M=-1;
while(m--){
ll ans=0;
ll a,b; cin>>a>>b;
ll l = -1, r = n+1;
while(l+1 < r){
ll mid = l+r>>1;
if(chk(mid, a))l = mid;
else r = mid;
}
ll res = l;
l = -1, r = n+1;
while(l+1 < r){
ll mid = l+r>>1;
if(chk(mid, b))l = mid;
else r = mid;
}
ll res2 = max(res, l);
res = min(res, l);
while(res>M){
ans += v[M+1];
M++;
}
M=max(M,res2);
cout<<ans<<"\n";
}
}
64:03 ~ 124:06 : 3번 Subtask#4 해결 (S#4 : 직선이 차지하는 구간 크기가 모두 같다) +23점
S#4부터는, 직선을 시작점을 기준으로(같다면 끝점을 기준으로) 오름차순으로 정렬하여 새로 번호를 매길 것이다.
각 직선의 구간 크기가 같다면, 무엇을 할 수 있을까? 그것은 바로 각 직선이 차지하는 구간의 크기를 s라 할때, 직선을 [L_i, L_i+s]로 나타낼 수 있다는 것이다. 또한, 직선을 정렬했기 때문에, 각 점에 의하여 삭제되는 직선을 구간으로 표현하면 그 구간이 연속적임을 알 수 있다.
따라서, 어떤 점에 의하여 삭제되는 가장 왼쪽 직선과, 가장 오른쪽 직선을 구하면 그 사이 직선을 싹 없애줄 수 있다.
어떤 점의 위치가 pos라고 하자. 다음과 같은 사실을 알 수 있다.
이 점에 의해 삭제되는 직선은, 0≤(pos와 L_i의 차이)<s인 모든 직선 i이다. (1≤i≤N)
이를 통해 알 수 있는 것은, pos-s<L_i≤pos를 만족하는 모든 직선 i가 사라짐을 알 수 있다.
직선이 오름차순으로 정렬되어 있으므로, 각 직선의 시작점 L_i에 대하여, pos-s의 upper_bound, pos의 upper_bound를 구하면, 삭제되는 직선을 알 수 있다.
이를 pos=a, pos=b인 경우에 대하여 모두 따진 후, Lazy propagation을 이용하여 구간 직선을 한꺼번에 처리할 수 있다.
솔루션은 꽤 명쾌하지만, 구현은 은근 어려워서 1시간을 날렸다. 차라리 풀이만 안상태에서 S#5를 건드리는게 나았을 것 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll n, m;
vector<pair<ll,ll>> v;
struct segtree{
struct asdf{
ll diff=0, lazy=0, chk=0;
};
vector<asdf> tree;
segtree(): tree(2020202) {}
void propagate(ll node, ll s, ll e){
auto &[diff, lazy, chk] = tree[node];
if(!chk)return;
diff = (e-s+1)*lazy;
if(s!=e)tree[node*2].lazy = lazy, tree[node*2].chk=1, tree[node*2+1].lazy = lazy;
lazy=0, tree[node*2+1].chk=1;
chk=0;
}
void upd(ll node, ll l, ll r, ll diff, ll s=1, ll e=n){
propagate(node, s,e);
if(l>r or r>n)return;
if(e<l or r<s)return;
if(l<=s and e<=r){
tree[node].diff = (e-s+1)*diff;
if(s==e)return;
tree[node*2].lazy = diff;
tree[node*2].chk=1;
tree[node*2+1].lazy = diff;
tree[node*2+1].chk=1;
return;
}
ll mid = s+e>>1;
upd(node*2,l,r,diff,s,mid);
upd(node*2+1,l,r,diff,mid+1,e);
tree[node].diff = tree[node*2].diff+tree[node*2+1].diff;
}
ll query(ll node, ll l, ll r, ll s=1, ll e=n){
propagate(node,s,e);
if(l>r or r>n)return 0;
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,l,r,s,mid)+query(node*2+1,l,r,mid+1,e);
}
} seg;
struct asdf2{
ll l, r, w;
bool operator < (const asdf2 o) const{
if(l==o.l)return r<o.r;
return l<o.l;
};
};
int main(){
fast;
cin>>n>>m;
vector<asdf2> v(n);
for(auto &[a,b,c]:v)cin>>a>>b>>c;
sort(all(v));
ll s = v[0].r-v[0].l;
vector<ll> v2(n);
for(int i = 0 ; i < n ; i++)v2[i]=v[i].l;
v2.push_back((ll)1e9+1);
sort(all(v2));
for(int i = 0 ; i < n ; i++){
seg.upd(1,i+1,i+1,v[i].w);
}
while(m--){
ll a,b; cin>>a>>b;
ll l = upper_bound(all(v2), a-s)-v2.begin()+1;
ll r = upper_bound(all(v2), a)-v2.begin();
ll l2 = upper_bound(all(v2), b-s)-v2.begin()+1;
ll r2 = upper_bound(all(v2), b)-v2.begin();
ll l3 = max(l,l2);
ll r3 = min(r,r2);
ll ans = seg.query(1LL,l3,r3);
cout<<ans<<"\n";
seg.upd(1LL,l,r,0LL);
seg.upd(1LL,l2,r2,0LL);
}
}
124:06 ~ 142:53 : 4번 Subtask#1 해결 (S#1 : N≤15) +10점
3번을 S#4까지 풀고, S#5는 뭔가 못 풀것 같아서 일단 4번을 넘어왔다. (현재 248점)
이 문제는 그냥 지문을 읽어보자. 겁나 꼬아놔서 정리하기가 힘들다.
이 문제 또한 문제를 제대로 이해했다면, S#1은 그냥 브루트포스이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
bool is_zigzag(vector<ll> &v){
if(v.size()<=2)return 1;
bool f = v[1]>v[0]; //f가 1이면 현재가 다음보다 작아야 함
for(int i = 2 ; i < v.size() ; i++){
if(f){
if(v[i]>v[i-1])return 0;
}
else if(v[i]<v[i-1])return 0;
f=!f;
}
return 1;
}
ll n;
int main(){
fast;
cin>>n;
vector<ll> v(n);
ll ans = 0;
for(auto &i : v)cin>>i;
for(int x = 1 ; x <= n ; x++){
for(int y = 0 ; y < n ; y++){
for(int z = y ; z < n ; z++){
ll res = 0;
for(int i = 0 ; i <= (1<<(z-y+1)) ; i++){
vector<ll> v2;
bool f=1;
for(int j = 0 ; j <= z-y ; j++){
if(i&(1<<j)){
if(v[y+j]>x){
f=0;
break;
}
v2.push_back(v[y+j]);
}
}
if(f and is_zigzag(v2))res = max(res, (ll)v2.size());
}
ans += res;
}
}
cout<<ans<<"\n";
ans=0;
}
}
142:53 ~ 175:25 : 4번 Subtask#2 해결 (S#2 : N≤100) +13점
N이 100이다 <=> O(N^4)
dp[i][j][k] := (i,j) 안에서 현재 지그재그 상태(?)가 k일때, 가능한 최댓값
지그재그 상태는 대충 올라가는 지그재그인지, 내려가는 지그재그인지를 판단하는 거다.
음... 그냥 코드를 보자. (풀이를 까먹었다.) 간단한 dp이다. 근데 계속 값이 틀려서 시간을 꽤 날렸다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll dp[505][505][3];
ll x, n;
vector<ll> v;
ll f(ll i, ll j, ll k){
ll &ret = dp[i][j][k];
if(~ret)return ret;
if(v[i]>x){
if(i==j)return 0;
return ret = f(i+1, j, k);
}
ret = 1;
for(int l = i+1 ; l <= j ; l++){
if(v[l]>x)continue;
if(k==1){
if(v[l]>v[i])continue;
}
else if(k==0){
if(v[l]<v[i])continue;
}
if(k==2){
if(v[l]<v[i])ret = max(ret, f(l,j,0)+1);
else ret = max(ret, f(l,j,1)+1);
}
else ret = max(ret, f(l, j, !k)+1);
}
return ret;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
for(x = 1 ; x <= n ; x++){
memset(dp, -1, sizeof(dp));
ll ans = 0;
for(int i = 0 ; i < n ; i++){
for(int j = i ; j < n ; j++){
ans += f(i,j,2);
}
}
cout<<ans<<"\n";
}
}
175:25 ~ 240:10 : 3번 해결 +52점
우리는 S#4 풀이를 확장할 것이다. 정확한 아이디어는 다음과 같다.
어떤 직선이 몇번 쿼리에 사라지는지를 빠르게 구할 수 있을까?
놀랍게도 가능하다! 이는 세그먼트 트리를 이용하면 된다. 먼저 직선과 모든 점들을 먼저 입력받자. 그리고 모든 좌표를 좌표압축시킨다.
우리는 어떤 점의 좌표가 pos일때, pos≤L_i, R_i<pos여야 삭제됨을 알고 있다. 또한 S#4에 의하여, 직선이 삭제되는 구간은 연속적임도 알고 있다. 이를 합치면, 각 직선이 어느 점에 의하여 가장 먼저 사라지는지를 알 수 있다!
세그먼트 트리에서 노드의 번호는 점의 위치, 노드의 값은 점의 쿼리 번호를 저장하게 할 것이다.
세그먼트 트리는 RMQ(구간 최솟값 쿼리)를 처리할 수 있도록 2개를 만들어둔다. 2개인 이유는 점 a, 점 b에 대한 세그트리를 따로 구성할 것이기 때문이다.
[L_i, R_i]를 차지하는 직선이 가장 먼저 삭제되는 쿼리를 어떻게 구해야 할까? 정답은 RMQ(L_i, R_i -1)이다. 왜냐?
1. L_i~R_i -1이 의미하는 것은, 이 직선에 포함되는 점들을 의미한다. (어떤 점의 위치가 pos이고 L_i≤pos<R_i이라면, 세그먼트 트리의 L_i~R_i -1번 사이 정점 어딘가에 위치하기 때문이다.)
2. 각 노드의 값들은 쿼리 번호를 의미하므로, RMQ(L_i, R_i -1)이 의미하는 것은, 이 직선에 포함되는 점들 중 쿼리가 가장 빠른 점의 쿼리 번호이다.
이를 a,b에 대하여 고려해준다. 그러면 둘 중 쿼리 번호가 작은 값의 쿼리에서 삭제된다고 저장하면 되고, a쿼리=b쿼리일 경우 2개의 점에 모두 포함된다는 의미이므로 weight를 더해주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll n, m;
vector<pair<ll,ll>> v;
struct segtree{
vector<ll> tree;
void init(){
tree.resize(4040404, INT_MAX);
}
void upd(ll node, ll idx, ll diff, ll s=1, ll e=(n+m)*2){
if(idx<s or e<idx)return;
if(s==e){
tree[node] = diff;
return;
}
ll mid = s+e>>1;
upd(node*2,idx,diff,s,mid);
upd(node*2+1,idx,diff,mid+1,e);
tree[node] = min(tree[node*2], tree[node*2+1]);
}
ll query(ll node, ll l, ll r, ll s=1, ll e=(n+m)*2){
if(e<l or r<s)return INT_MAX;
if(l<=s and e<=r)return tree[node];
ll mid = s+e>>1;
return min(query(node*2,l,r,s,mid),query(node*2+1,l,r,mid+1,e));
}
} minseg, minseg2;
struct asdf2{
ll l, r, w;
bool operator < (const asdf2 o) const{
if(l==o.l)return r<o.r;
return l<o.l;
};
};
pair<ll,ll> Q[252525]; //쿼리
vector<pair<ll,ll>> dline[1010101]; //dline[i] := i번 쿼리에서 삭제되는 직선들 번호
int main(){
fast;
minseg.init(); minseg2.init();
cin>>n>>m;
vector<asdf2> v(n);
for(auto &[a,b,c]:v)cin>>a>>b>>c;
sort(all(v));
ll s = v[0].r-v[0].l;
vector<ll> v2(n);
for(int i = 0 ; i < n ; i++)v2[i]=v[i].l;
v2.push_back((ll)1e9+1);
sort(all(v2));
vector<ll> e;
for(int i = 0 ; i < m ; i++){
cin>>Q[i].first>>Q[i].second;
e.push_back(Q[i].first);
e.push_back(Q[i].second);
}
for(int i = 0 ; i < n ; i++){
e.push_back(v[i].l);
e.push_back(v[i].r);
}
sort(all(e)); comp(e);
for(int i = 0 ; i < m ; i++){
ll a = lower_bound(all(e),Q[i].first)-e.begin()+1, b = lower_bound(all(e),Q[i].second)-e.begin()+1;
if(minseg.query(1,a,a)>i)minseg.upd(1,a,i);
if(minseg2.query(1,b,b)>i)minseg2.upd(1,b,i);
}
for(int i = 0 ; i < n ; i++){
ll l = lower_bound(all(e), v[i].l)-e.begin()+1;
ll r = lower_bound(all(e), v[i].r)-e.begin(); //원래 +1을 해야하지만, RMQ할때 어차피 r에는 1을 뺄거라서 안더함
ll A = minseg.query(1,l,r), B = minseg2.query(1,l,r);
if(A<INT_MAX or B<INT_MAX)dline[min(A,B)].push_back({i,(A==B)});
}
for(int i = 0 ; i < m ; i++){
ll a,b; a=Q[i].first, b = Q[i].second;
ll ans = 0;
for(auto [j,k] : dline[i]){
if(k)ans += v[j].w;
}
cout<<ans<<"\n";
}
}3번 문제는 플래티넘 중상위같으나(이게 가장 쉬운 풀이라면), 작년보단 쉬운 난이도같다. (solved.ac 티어 기준)
240:10 ~ 262:00 : 4번 Subtask#3 해결 (S#3 : N≤500) +17점
3번을 풀고 323점을 확보했으나, 340은 되야 금상에 안착할 수 있을 것 같았다. (물론 지금보니 커트라인은 243인가 그랬다.)
N≤500 <=> O(N^3)이다.
S#2에서 반복문 하나 줄이면 될것 같아서, 재귀를 최적화했더니 됐다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(), v.end()
#define rll(v) v.rbegin(), v.rend()
#define comp(v) v.erase(unique(all(v)), v.end())
ll dp[505][505][3];
ll x, n;
vector<ll> v;
ll notless[505];
ll f(ll i, ll j, ll k){
ll &ret = dp[i][j][k];
if(~ret)return ret;
if(v[i]>x){
if(i==j)return 0;
return ret = f(i+1, j, k);
}
ret = 1;
if(i==j)return ret;
if(notless[i]==-1 or notless[i]>j)return ret;
ll next = notless[i];
bool F=1;
if(k==1){
if(v[next]>v[i])F=0;
}
else if(k==0){
if(v[next]<v[i])F=0;
}
if(k==2){
if(v[next]<v[i])ret = max(ret, f(next,j,0)+1);
else ret = max(ret, f(next,j,1)+1);
}
else if(F)ret = max(ret, f(next,j,!k)+1);
ret = max(ret, f(next, j, k));
return ret;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &i : v)cin>>i;
for(x = 1 ; x <= n ; x++){
memset(dp, -1, sizeof(dp));
memset(notless, -1, sizeof(notless));
ll ans = 0;
for(int i = 0 ; i < n ; i++){
for(int j = i+1 ; j < n ; j++){
if(v[j]<=x){
notless[i]=j;
break;
}
}
}
for(int i = 0 ; i < n ; i++){
for(int j = i ; j < n ; j++){
ans += f(i,j,2);
}
}
cout<<ans<<"\n";
}
}
262:00~270:00 : 4번 S#4부터는 모르겠어서 걍 엎드려있었다. 4번은 풀질 못해서 티어는 모르겠다.
금상이 나왔으니 일단 만족한다. 작년에 동상이었는데(91점) 이정도면 꽤나 발전한 것 같다.
여담)3시간남았을때부터 화장실 가고싶었는데 흐름 끊길까봐 그냥 끝까지 참았다. 그냥 갈걸. 또한 4번 풀이가 부실한 이유는 이때 머릿속에 아무 생각도 없었기 때문이다(?)
'대회 > KOI' 카테고리의 다른 글
| 와 이걸 왜 대회 때 못풀었지 (0) | 2024.07.06 |
|---|---|
| KOI 2024 일기 (1) | 2024.05.12 |
| KOI 지역본선 2005 (0) | 2023.10.09 |
| KOI 지역본선 2004 (0) | 2023.10.09 |
