
나쁘지 않은 결과이다.

A (4분)
사실 풀이를 모른다. 그냥 사람들 푸는 속도 보고 예제 규칙보고 맞췄다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#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 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
ll a,b; cin>>a>>b;
cout<<max(a,b)<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
B (6분)
리프끼리 이어주면
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#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 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
ll n; cin>>n;
vector<ll> deg(n+1,0);
for(int i = 0 ; i < n-1 ; i++){
ll a,b; cin>>a>>b;
deg[a]++; deg[b]++;
}
ll cnt = 0;
for(int i = 1 ; i <= n ; i++){
if(deg[i]==1)cnt++;
}
cout<<(cnt+1)/2<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
C (15분)
아주 중요한 관찰 하나를 하면 된다. 그건 바로 사전순으로 가장 큰 부분집합에 항상 문자열의 마지막 원소가 포함된다는 점이다.
생각해보면 되게 당연하다. 그래서 이게 의미하는 것은, 처음에 사전순 가장 큰 부분 집합을 하나 찾으면, 걔를 cyclic 하면서 크기가 1씩 줄어들고 결국 사전순으로 가장 큰 문자가 마지막 원소로 이동해 더 이상 cyclic이 일어날 수 없게 된다. 즉 1번만 찾아서 cyclic해주면 된다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#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 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
ll n;
string s;
cin>>n>>s;
vector<ll> v;
for(int i = 0 ; i < n ; i++){
while(v.size() and s[v.back()] < s[i])v.pop_back();
v.push_back(i);
}
string t = s;
ll siz = v.size();
for(int i = 0 ; i < siz; i++){
t[v[i]] = s[v[siz-i-1]];
}
ll cnt = 0;
for(int i = 0 ; i < siz ; i++){
if(s[v[i]] != s[v[0]])break;
cnt++;
}
cout<<(is_sorted(all(t)) ? siz-cnt : -1)<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
D (57분, +3)
먼저 해야하는 관찰은,
먼저 배열을 2배 늘려서 모든 cyclic을 순회한다고 생각하자.

처음에 주어진 순열이 [1,3,0,2,4]라고 하자. 그럼 위 사진처럼 원본 순열의 값은 위와 같이 min(1,4)+min(2,4)+min(3,4)+min(4,4)+n이 된다. 이제 한번 left shift한 [3,0,2,4,1]을 보자.

그럼 이런식으로 값이 옮겨감을 알 수 있다. 이제 이것들이 실제로 어떤 값을 가지는지 알아보자. min(1,4)와 min(2,5)에는 어떤 관계가 있을까? 만약 min(1,4)가
우리가 [l..r]을 보고 있을 때, 실제로 값이 될 수 있는 원소는 r에서 시작해서, 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소를 반복해서 찾은 값들이다. 예를 들어 [0,4,1,3]에서는 가장 오른쪽인 3에서 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소는 1이 되며, 1 다음은 0이 된다.
그럼 이것들이 실제로 몇개에 영향을 주는지를 구하면 되며, 이는 결국 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소를 반복해서 찾은 값들의 인접한 인덱스 차임을 알 수 있다(가장 왼쪽은 자기 인덱스-구간 시작위치+1). 즉 [0,4,1,3]에서 [0,1,3]을 찾았을 때, 3과 1의 인덱스 차가 1이므로 3은 1개, 1과 0의 인덱스 차가 2이므로 1은 2개에 영향을 준다. 0은 시작지점부터 자기 인덱스까지 영향을 주므로 1개에 영향을 준다.
이제 이 방식을 구현하면 되는데, 이는 덱을 back에서 monotone increase하게 유지하면서, front에서 빠지는 값들을 빼주는 방식으로 구현할 수 있다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#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 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
ll n; cin>>n;
vector<ll> v(n);
for(auto &i : v)cin>>i;
if(n==1){
cout<<"1\n";
return;
}
ll ans = 0;
vector<ll> e = v;
for(auto i : v)e.push_back(i);
deque<ll> dq;
for(int i = 1 ; i < n ; i++){
while(dq.size() and e[dq.back()] > e[i])dq.pop_back();
dq.push_back(i);
}
ans = e[dq.front()]*dq.front();
for(int i = 1 ; i < dq.size() ; i++)ans += e[dq[i]]*(dq[i]-dq[i-1]);
ll cur = ans;
//for(auto i : dq)cout<<i<<" "; cout<<endl;
//DEB<<cur<<endl;
for(ll l = 2, r = n ; r < n*2 ; l++, r++){
if(dq.size())cur -= e[dq.front()];
if(dq.front()<l)dq.pop_front();
while(dq.size() and e[dq.back()] > e[r]){
if(dq.size()==1)cur -= e[dq.back()]*(dq.back()-l+1);
else cur -= e[dq.back()]*(dq.back()-dq[dq.size()-2]);
dq.pop_back();
}
dq.push_back(r);
if(dq.size()==1)cur += e[dq.back()]*(dq.back()-l+1);
else cur += e[dq.back()]*(dq.back()-dq[dq.size()-2]);
ans = max(ans,cur);
//for(auto i : dq)cout<<i<<" "; cout<<endl;
//DEB<<s<<" "<<cur<<endl;
}
cout<<ans+n<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}

그래프가 진동한다 ㄷㄷ..
'codeforces > div2' 카테고리의 다른 글
Codeforces Round 930 (Div.2) (+퍼플 달성) (3) | 2024.03.01 |
---|---|
Codeforces Round 924 (Div.2) (0) | 2024.02.11 |
Codeforces Round 917 (Div.2) (1) | 2023.12.25 |
Codeforces Round 904 (Div.2) + 905 (Div.2) (2) | 2023.10.23 |
Codeforces Round 665 (Div. 2) A~D (0) | 2023.09.24 |