제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플 제발 퍼플
+)
A
문제가 복잡하게 써져 있지만 결국 1번 위치만 본다면, 1->2로 가고 2->4로 가고... 임을 알 수 있다. 따라서 n 이하인 가장 큰 2^k까지 간다.
참고로 이것과 매우 유사한 문제가 흐즈로컵 3회에 있었는데, 그 이유는 이 문제 출제자가 흐즈로컵 출제자이기 때문이다.
#include <bits/stdc++.h>
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 1000000007
#define MOD2 998244353
#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;
ll i=1;
for(; i <= n ; i*=2);
cout<<i/2<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
B
사전순 최소인 문자열을 구할 수 있다면 개수 세주는 건 dp로 해줄 수 있다.
일단 아래와 오른쪽 이동밖에 없으므로 아래 이동을 1번 하는 것이 전체 문자열을 결정한다.
이때 사전순 최소여야 하므로 0을 최대한 따라가면 된다. 현재 (0,i)에 있다고 하자. 그리디하게 생각해보면 이때 내려가야 하는 경우는 i = n-1이거나, (0,i+1)이 1이고 (1,i)가 0인 경우 뿐이다. 이렇게 사전순 최소를 구해줄 수 있고 이후는 단순 dp다.
#include <bits/stdc++.h>
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 1000000007
#define MOD2 998244353
#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;
ll dp[2][202020];
string s[2];
ll n;
string want;
ll f(ll x, ll y, ll cnt=0){
if(x==1 and y==n-1)return 1;
ll &ret = dp[x][y];
if(~ret)return ret; ret = 0;
if(x==0 and want[cnt+1] == s[x+1][y])ret += f(x+1,y,cnt+1);
if(y<n-1 and want[cnt+1] == s[x][y+1])ret += f(x,y+1,cnt+1);
return ret;
}
void make(ll x, ll y){
want += s[x][y];
if(x==1 and y==n-1)return;
if(y==n-1){
make(x+1,y);
}
else if(x==1)make(x,y+1);
else{
if(s[x+1][y] < s[x][y+1])make(x+1,y);
else make(x,y+1);
}
}
void solve(){
cin>>n>>s[0]>>s[1];
want="";
for(int i = 0 ; i < n ; i++)dp[0][i]=dp[1][i]=-1;
make(0,0);
cout<<want<<"\n"<<f(0,0)<<"\n";
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
C (+2)
먼저 최댓값(n-1)을 O(N)번의 질문으로 찾아주자.
그러면 답을 구하기 위해서는 최댓값과 xor 했을 때 1111...111 꼴이 되는 수를 구해야 한다.
일단 앞에서부터 보면서 최댓값과 xor을 해서 최대인지를 판별해주자.(최대일 때 항상 1111...111 꼴이기 때문이다.)
이제 최대인 위치들 중 그 값이 가장 작은 위치가 답이 된다.
말이 어려우니 예를 들어 보자. 11010이 최댓값이라고 하면 우리가 원하는 수는 00101이다. 그리고 11010과 OR했을 때 최대인 수는 00101, 00111, 11111 등등.. 여러가지가 있다. 하지만 이 중 최소인 00101만이 xor 했을때도 중복되는 비트가 없어 1로 꽉 채워짐을 알 수 있다.
#include <bits/stdc++.h>
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 1000000007
#define MOD2 998244353
#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;
char query(ll a, ll b, ll c, ll d){
cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
char x; cin>>x;
return x;
}
void solve(){
ll n; cin>>n;
ll idx = 0, mx = -1;
for(int i = 1 ; i < n ; i++){
char res = query(idx,idx,i,i);
if(res=='<')idx = i;
}
for(int i = 0 ; i < n ; i++){
if(i==idx)continue;
if(mx<0)mx = i;
else{
char res = query(mx,idx,i,idx);
if(res=='<')mx = i;
else if(res=='='){
char res2 = query(i,i,mx,mx);
if(res2=='<')mx = i;
}
}
}
cout<<"! "<<mx<<" "<<idx<<endl;
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
여담으로 처음에 낸 WA 코드는 다음과 같았다.
else{
char res = query(mx,idx,i,idx);
if(res=='<')mx = i;
else if(res=='>'){
char res2 = query(i,i,mx,mx);
if(res2=='<')mx = i;
}
}
AC 코드와 단 1문자 차이임을 알 수 있다. 얘만 아니었으면 패널티 100점 + 시간 7분 아껴서 10등대였을 텐데 아쉽다.
D
이동 경로가 복잡해 보이지만 생각보다 단순하다. 일단 처음에 적혀있는 방향 (<, >)에 따라 쭉 이동하다가, 그 반대를 만나면 반사되는 것처럼 쭉 돌아가서 원위치로 돌아가고, 이제 그 반대방향으로 쭉 이동하다가 또 그 반대를 만나면 또 반사되서 또 자기 자리로 돌아온다. 이 과정을 반복하다가 반사되는 게 없으면 끝난다.
방향이 '<'든 '>'든 논리는 똑같기 때문에 '<'라고 가정하자. 그럼 왼쪽으로 한번 갔다가, 오른쪽으로 한번 갔다가, 다시 자기 자리로 돌아오는 과정이 반복되다가 탈출할 것이다.
이 때 중요한 점은 왼쪽과 오른쪽을 분리해서 생각할 수 있다는 것이고, 왼쪽으로 탈출하기 위해서 필요한 반사 횟수는 왼쪽에 있는 '>'에 개수, 오른쪽으로 탈출하기 위해서 필요한 반사 횟수는 오른쪽에 있는 '<'의 개수와 같다는 것이다. 이는 반사가 일어날 때마다 다른 부등호는 그대로고 양쪽에 있는 저것들만 하나씩 줄어들기 때문에 그렇다. 그래서 이 정보를 가지고 탈출하기 위한 최소 반사 횟수와 그 때의 이동거리를 prefix sum + binary search로 열심히 구현해주면 된다.
#include <bits/stdc++.h>
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 1000000007
#define MOD2 998244353
#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 cntL=0,cntR=0;
ll n; cin>>n;
string s; cin>>s;
vector<ll> ssum(n), scnt(n), psum(n), pcnt(n);
for(auto i : s)if(i=='<')cntR++;
scnt[n-1] = (s[n-1]=='>');
for(int i = n-2 ; i >= 0 ; i--){
scnt[i] = scnt[i+1] + (s[i] == '>');
ssum[i] = ssum[i+1] + (s[i] == '>' ? (n-1 - i) : 0);
}
reverse(all(scnt));
reverse(all(ssum));
pcnt[0] = (s[0]=='<');
for(int i = 1 ; i < n ; i++){
pcnt[i] = pcnt[i-1] + (s[i] == '<');
psum[i] = psum[i-1] + (s[i] == '<' ? i : 0);
}
for(int i = 0 ; i < n ; i++){
ll res = 0;
if(s[i]=='<')cntR--;
if(s[i]=='<'){
if(cntL <= cntR){ //left로 빠짐
res += ((ssum[n-1] - ssum[n-i-1]) - cntL * (n-1-i))*2 + i+1;
auto it = lower_bound(pcnt.begin()+i, pcnt.begin()+n, pcnt[i]+cntL);
res += (psum[(it-pcnt.begin())] - psum[i] - cntL * i)*2;
}
else{ //right로 빠짐
res += ((psum[n-1] - psum[i]) - cntR * i)*2 + (n-i);
auto it = upper_bound(scnt.begin()+(n-i-1), scnt.begin()+n, scnt[n-i-1]+cntR);
res += (ssum[(it-scnt.begin())] - ssum[n-i-1] - (cntR+1) * (n-i-1))*2;
}
}
else{
if(cntR <= cntL){ //right
res += ((psum[n-1] - psum[i]) - cntR * i)*2 + (n-i);
auto it = lower_bound(scnt.begin()+(n-i-1), scnt.begin()+n, scnt[n-i-1]+cntR);
res += (ssum[(it-scnt.begin())] - ssum[n-i-1] - cntR * (n-i-1))*2;
}
else{ //left
res += ((ssum[n-1] - ssum[n-i-1]) - cntL * (n-1-i))*2 + i+1;
auto it = upper_bound(pcnt.begin()+i, pcnt.begin()+n, pcnt[i]+cntL);
res += (psum[(it-pcnt.begin())] - psum[i] - (cntL+1) * i)*2;
}
}
cout<<res<<" \n"[i==n-1];
if(s[i]=='>')cntL++;
}
}
int main(){
fast;
ll t; cin>>t; while(t--)solve();
}
E, F
D가 싫어하는 스타일의 문제여서 처음에 넘기고 E, F 둘다 읽었다. E는 dp아니면 그래프 모델링 문제 같았다. 더러워보여서 넘겼다.
F는 웰노운 같았는데 아니었다. 좀 고민하다가 D로 다시 도망갔다.
아마 E는 업솔빙할 것 같다. 물론 귀찮아서시간 없어서 안 할 수도
'codeforces > div2' 카테고리의 다른 글
| Codeforces Round 924 (Div.2) (0) | 2024.02.11 |
|---|---|
| Codeforces Round 917 (Div.2) (1) | 2023.12.25 |
| Codeforces Round 915 (Div.2) (1) | 2023.12.17 |
| Codeforces Round 904 (Div.2) + 905 (Div.2) (2) | 2023.10.23 |
| Codeforces Round 665 (Div. 2) A~D (0) | 2023.09.24 |
