결과
블루는 커녕 민트 복구도 못하게 생겼다. 근데 unrated???????
A - 0:00 ~ 0:40
그냥 구현. 바로 제출해서 맞았다.
풀이)문자열을 입력받고, 반복문으로 한 문자를 2번씩 출력하면 됩니다.
ll n, m, q, k;
string s,t;
set<ll> st;
int main(){
fast;
cin>>n>>s;
for(auto i : s)cout<<i<<i;
}
B - 0:40 ~ 5:03
이 대회를 망친 이유 1
읽자마자 그냥 이진수네? 하고 1:46에 제출하고 C를 읽고 있었으나 WA가 나왔다. 그래서 오버플로 문제겠거니 하고 바꿨는데 또 WA. 그래서 시프트 연산, pow 문제인가 하고 바꿨더니 또 WA.
알고보니 64개를 입력받아야되는데 63개를 받았다. (...) 불안해서 unsigned long long으로 바꾸고 2도 하나하나 곱하게 바꾼 후 다시 제출해서 AC. (5:03)
풀이)i번째로 입력받은 수가 1이면 2를 i번 곱해서 더하면 됩니다. (i는 0부터 시작)
unsigned long long n, m, q, k;
string s,t;
set<ll> st;
int main(){
fast;
for(int i = 0 ; i < 64 ; i++){
ll a; cin>>a;
unsigned long long b=1;
if(a){
for(int j = 0 ; j < i ; j++)b *= 2;
n += b;
}
}
cout<<n;
}
C - 5:03 ~ 8:04
간단한 정렬 문제였다.
풀이)숫자 하나당 3칸짜리 배열을 관리하게 한 후, 오름차순으로 인덱스를 넣습니다. 나중에 2번째 칸만 뽑아내서 정렬하면 됩니다.
ll n;
vector<ll> v[101010];
int main(){
fast;
cin>>n;
for(int i = 0 ; i < n*3 ; i++){
ll a; cin>>a;
v[a].push_back(i+1);
}
vector<pair<ll,ll>> ans;
for(int i = 1 ; i <= n ; i++){
ans.push_back({v[i][1],i});
}
sort(all(ans));
for(auto [a,b] : ans)cout<<b<<" ";
}
D - 8:04 ~ 15:17
누가봐도 dp였다. 전형적인 형태여서 금방 짤 줄 알았는데 답이 제대로 안나와서 구조를 살짝 바꿨다. 그래서 시간이 좀 더 걸렸다.
풀이)dp[i][j] := i번째에서 중독된 상태가 j일때 가능한 최댓값(j=0 : 정상 j=1 : 중독. j=2이면 불가능)으로 정의한 후, 냅색형태로 식을 세우면 됩니다.
#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
ll n;
ll dp[101010*3][3];
vector<pair<ll,ll>> v;
ll f(ll x, ll y){
if(y==2)return -1e18;
if(x==n)return 0;
ll &ret = dp[x][y];
if(~ret)return ret; ret = -1e18;
if(v[x].first==1)ret = max({ret, f(x+1, y), f(x+1, y+1)+v[x].second});
else ret = max({ret, f(x+1, y), f(x+1, 0)+v[x].second});
return ret;
}
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &[a,b] : v)cin>>a>>b;
memset(dp,-1,sizeof(dp));
cout<<max(0LL,f(0,0));
}
E - 15:17 ~ 86:08
망한 이유 2.
풀이는 금방 생각이 났다. 멀티셋을 2개 쓰는 더러운 풀이였는데 시간제한이 6초인 걸 보니 무조건 될 것 같았다. 그래서 구현을 시작했다.
망한 이유는 아이디어를 적지 않고 머리로 case 나눠서 구현하다가 멘탈이 나갔다. 주석이라도 달아서 어찌저찌 실행은 했고, 예제를 넣어봤는데 계속 RE가 났다. 역시 set은 구데기 그래서 디버깅하느라 20분 정도 날리고 예제가 제대로 떠서 제출했더니 채점에서 RE가 났다.
이때가 58분이었는데 이때 F를 잡았으면 아마 훨씬 좋았을 것이다. (F는 그냥 세그) 하지만 지금까지 구현한게 아까워서 그냥 계속 하는 최악의 선택을 하게 된다.
일단 어디서 RE가 나는지 확인하기 위해서 RE가 날거같은 부분을 while(1); 로 해서 RE가 뜨는지 TLE가 뜨는지를 채점으로 확인했다. 근데 하필 이때 또 앳코더 채점이 터졌다. 그래서 걍 멍때리다가 결과를 봤는데 RE였다. 이 짓을 3번 더했더니 TLE 나는 곳을 찾았다. 반례를 금방 찾았고, 케이스 하나를 잘못 고려한게 문제였다. 고쳤더니 바로 AC가 나왔다. (86:08)
풀이)multiset 2개를 준비합니다. 하나는 가장 큰 원소부터 k번째(이 멀티셋을 S라 하겠습니다)까지, 하나는 k+1번째부터 n번째까지(T라 하겠습니다)를 담고 있고, 처음엔 다 0입니다. 쿼리가 주어지면, 이전에 xi에 들어있던 값을 적절히 빼서, yi를 잘 넣어주는 작업을 반복하면 됩니다. 이때 xi가 S에 포함되어 있었다면 sum(출력할 합)에 xi를 빼주고, 만약 새로 들어온 yi가 S에 포함된다면 sum에 yi를 더합니다. 그렇지 않다면 T에서 가장 큰 원소를 S에 옮기고, T에서는 지워준 후 T에 yi를 넣습니다. 이 과정을 xi가 S에 포함되어 있지 않을 때도 비슷하게 수행합니다.
#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
ll n, k, q;
multiset<ll> s, t;
ll arr[505050];
vector<ll> v;
ll sum = 0;
int main(){
fast;
cin>>n>>k>>q;
for(int i = 0 ; i < k ; i++)s.insert(0);
for(int i = 0 ; i < n-k ; i++)t.insert(0);
while(q--){
ll a,b; cin>>a>>b;
if(arr[a]>=*s.begin()){ //업뎃 전이 들어감
s.erase(s.find(arr[a])), sum -= arr[a];
if(s.empty()){
t.insert(b);
auto it = t.end();
it--;
s.insert(*it);
sum += *it;
t.erase(it);
}
else if(s.empty() or b>*s.begin()){ //뒤는 들어감
s.insert(b);
sum += b;
}
else{ //안들어감
t.insert(b);
auto it = t.end();
it--;
s.insert(*it);
sum += *it;
t.erase(it);
}
arr[a]=b;
}
else{
t.erase(t.find(arr[a]));
if(s.empty() or b>*s.begin()){ //업뎃 전은 안들어가고 뒤는 들어감
s.insert(b);
sum += b;
t.insert(*s.begin());
sum -= *s.begin();
s.erase(s.begin());
}
else{ //둘다 안들어감
t.insert(b);
}
arr[a]=b;
}
cout<<sum<<"\n";
}
}
86:08~99:59 아무것도 안했다. F는 문제를 읽어도 뭔소린지 모르겠다.
BST + case work형 쿼리는 볼때마다 머리가 터지는 것 같다. 아무래도 set 다루는 연습을 해야할 거 같긴 하다. 아니면 되도록 PQ를 써야겠다.
upsolving
F - 20분 소요
문제 해석에 5분이나 먹었습니다. 이해가 안 될 경우 예제부터 보도록 합시다.
풀이)먼저 숫자가 중요한 게 아닌, 숫자의 대소가 중요하므로 숫자가 클 경우 좌표압축이 가능함을 기억합시다.
두 집합간 비교를 하는 것이 아닌, 한 집합을 잡고 나머지 집합과 한번에 비교하는 방법을 생각할 수 있습니다.
예제 1의 집합은 {1,3}, {2,8}, {4,6}이고, 구해야 하는 값은
{1,2,3,8}에서 1과 3의 인덱스, {1,3,4,6}에서 1과 3의 인덱스, {2,4,6,8}에서 2와 8의 인덱스입니다.
먼저 1번 집합만 고려해봅시다.
생각해보면 어떤 수의 인덱스라는 것은 그 수보다 작은 수의 개수+1과 같습니다. 따라서 {1,2,3,8}, {1,3,4,6}을 따로 계산하지 않고
{1,2,3,4,6,8}에서 3보다 작은 수(=2)의 개수+2, 1보다 작은 수의 개수(=0)+2를 계산하면 될 것입니다.
(1이 아닌 2를 더하는 이유는 집합이 {1,2,3,8}, {1,3,4,6} 2개이기 때문입니다. 일반적으로 i번 집합은 i+1,i+2, ... ,n번까지의 집합과 비교하므로 n-i를 더해야 합니다)
분명 {1,2,3,8}에서 1과 3의 인덱스, {1,3,4,6}에서 1과 3의 인덱스를 더하면 1+3 + 1+2 = 7인데, 위처럼 계산하면 4+2=6이 나옵니다.
그 이유는, 1이 3보다 작은 경우가 {1,2,3,8}에서 1번, {1,3,4,6}에서 1번 총 2번 세어져야 하기 때문입니다. 즉, 같은 집합 내에서는 여러번 더해질 수 있으므로 이를 전처리하여 더해주면 됩니다.
어떤 수보다 작은 수의 개수는 펜윅트리를 이용하여 O(logNM)에 구할 수 있습니다. 따라서 처음에는 모든 집합의 수를 펜윅트리에 넣어주고, 1번 집합부터 시작하여 계산한 후 펜윅트리 상에서 값을 제거해주면 됩니다.
시간복잡도는 O(NMlogNM)이 됩니다.
#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
ll n, m;
vector<ll> v;
ll c(ll x){ return lower_bound(all(v), x)-v.begin()+1; }
ll tree[1010101];
vector<ll> e[10101];
void upd(ll i, ll diff){
while(i<=n*m){
tree[i] += diff;
i += (i&-i);
}
}
ll sum(ll i, ll ret = 0){
while(i){
ret += tree[i];
i -= (i&-i);
}
return ret;
}
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < n ; i++){
e[i].resize(m);
for(auto &j : e[i])cin>>j, v.push_back(j);
sort(all(e[i]));
}
sort(all(v));
comp(v);
for(int i = 0 ; i < n ; i++){
for(auto &j : e[i]){
j = c(j);
upd(j, 1);
}
}
ll ans = 0;
for(int i = 0 ; i < n-1 ; i++){
ll s = 0;
for(int k = 0 ; k < m ; k++){
ll j = e[i][k];
ans += sum(j-1)+(n-i-1)*(k+1);
upd(j, -1);
}
}
cout<<ans;
}
