코드포스 문제모음

https://blog.naver.com/PostList.naver?blogId=rlaisqls&from=postList&categoryNo=1&parentCategoryNo=1

Codeforces Round #769 (Div. 2) AB+C

A. ABC

이진문자열이 주어질때, 길이 1 이상의 팰린드롬 부분문자열이 없도록 재배열할 수 있는지 검사하는 문제이다.

일단 같은 문자가 2개 이상 붙어있으면 팰린드롬이다.

근데 같은 문자가 2개이상 붙어있지 않고 “10101…”과 같은 꼴로 배열된다? 그럼 그것도 팰린드롬이다.

그렇기 때문에 길이가 1인 문자열, 또는 길이가 2이고 “11”이나 “00”이 아닌 문자열 빼고 나머지는 다 불가능하다.

라고 출력해주면 되는 문제였다.

#include<iostream>
using namespace std;
void solve(){
    int i,n;
    string a;
    cin>>n>>a;
    if(n==2&&a[0]==a[1])cout<<"NO\n";
    else if(n<=2)cout<<"YES\n";
    else cout<<"NO\n";
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
}

B. Roof Construction

인접한 숫자들끼리 ⊕한 값의 최댓값이 최소가 되도록 0부터 n-1까지의 숫자를 배열하는 문제이다.

얜 솔직히 운으로 푼 느낌이 강하다. 정확한 풀이라기보다는 그냥 직관적으로 짰다고 해야할까?

일단 내가 문제를 풀때는, 가장 큰 숫자가 위험하다는 느낌이 들었다.

그래서 2의 (int)log2(n-1)승과 n-(2의 (int)log2(n-1)승)을 n-1의 양옆에 배치해서 n-1이 엄청난 숫자를 만들지 않도록 해줬고나머지는 그냥 적당히 순서대로 배열했다. 자세히 설명하자면 이런 느낌이다.

짤때는 되게 논리적인 코드라고 생각했는데, 지금보니까 솔직히 이게 왜 맞았는지 모르겠다.

비트연산자에 대해선 아직 내가 모르는 부분이 너무 많다.

#include<iostream>
#include<cmath>
using namespace std;
void solve(){
    int i,n;
    cin>>n;
    n--;
    int m=pow(2,(int)log2(n)), l=n-pow(2,(int)log2(n));
    for(i=m;i<=n;i++)cout<<i<<' ';
    for(i=l;i<m;i++)cout<<i<<' ';
    for(i=0;i<l;i++)cout<<i<<' ';
    cout<<'\n';
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
}

C. Roof Construction

a와 b가 주어진다. 그리고 우리는 세가지의 연산을 할 수 있다.

1. a=a+1

2. b=b+1

3. a=(a|b)

여기서 a와 b를 똑같이 만들기 위해선 위의 연산을 최소 몇 번 써야할까?

//1. 무지성 덧셈 (1번 연산만 사용)
res=min(res,b-a);
//2. a에 b밑부분 맞추기
if(b%((int)pow(2,(int)log2(a)+1))<=a)
    res=min(res,a-(b%((int)pow(2,(int)log2(a)+1)))+1);
//3. b밑부분에 a 맞추기
if(a<=b-pow(2,(int)log2(b)))
    res=min(res,b-((int)pow(2,(int)log2(b)))-a+1);

이 문제를 보고 처음에 작성했던 코드는 이 세가지 경우만 고려하는 코드였다. 이런 코드를 짠 이유는 3번 연산을 무조건 마지막에만 쓰는것이 최선이라고 생각했기 때문이 아니라, 그냥 귀찮았기 때문이었다.

암튼 제대로 풀어보자. 일단 3번 연산을 여러번 사용하는 것은 비효율적인 행위라는건 확실하다.

내가 놓쳤던 것은 3번 연산 뒤에 무언가 올 수도 있다는 사실이다.

3번 연산은 (a=a|b) a의 크기를 대폭상승 시켜줄 수 있다. or연산을 해주면 a가 무조건 b와 같거나 그보다 큰 값이 나올 수 밖에 없다. 그렇다는건 1,2번 연산으로 a와 b를 세팅한 후엔, 3번 연산 한 번과 (a|b)-b번 만큼의 2번 연산을 적용하는 것이 최선이라는 뜻이다.

그렇기 때문에 a가 a부터 b-1까지 1씩 증가하는 모든 경우의 수에서 3번 연산을 사용하기 적절한 b의 값을 구하고 그때 필요한 연산의 수가 나오면 res 변수랑 비교해서 최솟값을 저장해주면 답이 나온다.

어찌저찌 풀이를 이해하긴 했지만 정말 벽을 느낀 문제였다. 어렵다 진짜…

#include<iostream>
#include<cmath>
using namespace std;
void solve(){
  int i,a,b,res;
  cin>>a>>b;
  res=b-a;
    for(int a1=a;a1<b;a1++){
        int b1=0;
        for(i=21;i>=0;i--){
            if((b>>i)&1){
                b1^=(1<<i);
            }else{
                if((a1>>i)&1){b1^=(1<<i);break;}
            }
        }
        res=min(res,a1-a-b+(a1|b1)+1);
    }
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

Educational Codeforces Round 122 (Rated for Div. 2) AB

A. Div. 7

숫자 n이 주어질때, n에서 최대한 적은 자릿수를 바꿔서 7의 배수로 만드는 문제였다.

근데 사실 “n에서 최소 자릿수를 바꿔서 7의 배수를 만든다”고 문제에 써있긴 하지만,

일의 자릿수만 고려하면 쉽게 풀 수 있는 문제였다.

#include<iostream>
using namespace std;
void solve(){
  int n,i;
  cin>>n;
  if(n%7==0)cout<<n<<'\n';
  else{
    for(i=0;i<10;i++){
      int m=(n/10)*10+i;
      if(m%7==0){cout<<m<<'\n';return;}
    }
  }
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B. Minority

0과 1로만 이뤄진 문자열이 있다. 우리는 이 문자열중 일부를 선택하여 그 부분문자열 속에서 같은 문자의 갯수가 더 적은 문자를 모두 삭제할 수 있다.

예를 들어

• 100101010100 이라는 문자열이 있고
• 100"10101"0100 저 부분을 선택한다면
• 100"111"0100 0 두개를 삭제해서 이렇게 만들 수 있다.

그럼 문자를 최대 몇개까지 삭제시킬 수 있냐? 를 묻는 문제였다.

전체 문자열에서 0과 1의 갯수가 같다면 그 갯수-1 을 출력하고, 아니라면 그 둘 중에 더 작은 숫자를 출력하면 답이 나온다.

#include<iostream>
using namespace std;
void solve(){
  string a;
  int i,z=0,o=0;
  cin>>a;
  for(i=0;i<a.length();i++){
    if(a[i]=='0')z++;
    else o++;
  }
  if(z==o)cout<<o-1<<'\n';
  else cout<<min(o,z)<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

Codeforces Round #770 (Div. 2) A+BC

A. Reverse and concatenate

뒷 문제 설명이 더 중요하기 때문에 A번 문제설명은 생략한다.

그냥 문자열이 팰린드롬이거나 연산횟수가 0번인 경우엔 1을 출력하고 아닌경우 2를 출력하면 되는 문제였다.

#include<iostream>
using namespace std;
void solve(){
  int i,a,b;
  string s;
  cin>>a>>b>>s;

  bool flag=1;
  for(i=0;i<a/2;i++)if(s[i]!=s[a-1-i]){flag=0;break;}
  if(b==0||flag)cout<<"1\n";
  else cout<<"2\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B. Fortune Telling

이번 B번 문제는 C번 문제보다도 푼 사람 수가 더 적었다. 내가 B번에서 막혔을때는 그냥 내가 비트연산자에 무지해서겠거니 싶었는데 이 문제에서 고난을 겪은 사람이 나 뿐만이 아니었던 것 같다.

암튼 문제 설명을 해보자면, 앨리스와 밥이라는 친구가 점치기 놀이를 하기로 했다.

앨리스는 x, 밥은 x+3에서 시작해서 +a[i] 또는 ⊕a[i]중 하나를 각자 골라서 연산해준다.

그 결과값이 y가 나왔을때, 그 숫자가 밥이 만든건지 아니면 앨리스가 만든건지 맞추면 되는 문제다.

잘 생각 해보자.

• 홀수 + 홀수 = 짝수
• 홀수 ⊕ 홀수 = 짝수
• 짝수 + 홀수 = 홀수
• 짝수 ⊕ 홀수 = 홀수
  
• 홀수 + 짝수 = 홀수
• 홀수 ⊕ 짝수 = 홀수
• 짝수 + 짝수 = 짝수
• 짝수 ⊕ 짝수 = 짝수

위 표에서 1,2번째 행은 홀수를 +또는 ⊕하는 경우이고 홀수는 짝수로 짝수는 홀수로 반전된다.

3,4번째 행은 짝수를 +또는 ⊕하는 경우이고 홀수 짝수 둘다 그대로 유지된다.

이 성질을 사용한다면, 앨리스와 밥이 실제로 어떤 연산을 선택해서 숫자를 만들었든 상관이 없다.

어차피 앨리스와 밥은 서로 다른 수에서 시작하고 똑같이 a 배열의 값을 사용한다는 것을 알고있기 때문에 결과값이 홀수인지, 짝수인지만 알면 누구의 숫자로부터 나왔는지도 알 수 있다.

​

• x+y가 짝수이고, (둘다 짝수거나 둘다 홀수, 즉 숫자가 유지되었고) sum도 짝수라면 앨리스이다.
• x+y가 짝수이고, sum은 홀수라면 밥이다.
• x+y가 홀수이고, (하나는 홀수고 하나는 짝수, 즉 숫자가 반전되었고) sum은 짝수라면 밥이다.
• x+y가 홀수이고, sum도 홀수라면 앨리스이다.

그래서 결국 (sum+x+y)%2 일때 밥, 아니면 앨리스가 되는 것이다. ​

알고 보면 그렇게 복잡한 문제는 아니지만 풀이를 떠올리는게 좀 어렵긴 했다. 근데 이 문제를 못 푼 사람이 많은 이유는, “B번 정도에서 나올만 한 난이도” 의 코드를 생각하려고 했기 때문이 아닐까 싶다. 의외로 아이디어가 어려웠고 의외로 코드가 쉬웠다.

#include<iostream>
using namespace std;
void solve(){
  long long n,x,y,i,sum=0;
  cin>>n>>x>>y;
  for(i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    sum+=tmp;
  }
  if((sum+x+y)%2)cout<<"Bob\n";
  else cout<<"Alice\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

C. OKEA

nk 크기의 선반에 1번부터 nk번 까지의 물건을 진열한다.

그때, 한 행의 연속부분수열의 평균이 항상 정수가 되게 진열할 수 있을지 판단하는 문제였다.

세가지의 경우의 수를 따져보자.

​- (1) k가 1인 경우 - 한 행에 물건을 하나씩 배열하므로, 어떻게 하든 상관 없이 평균이 정수가 된다.

• (2) n이 홀수인 경우

  • 모든 연속부분수열의 평균이 정수가 되려면, 짝수와 홀수가 인접해있으면 안된다. 왜냐? 짝수와 홀수 사이의 평균은 정수가 아니니까!

    그렇기 때문에 각 행이 모두 짝수로 이뤄져있거나, 모두 홀수로 이뤄져야 한다.

    근데 n이 홀수면 그렇게 만들 수가 없으므로, 즉시 “NO”를 출력해준다.

• (3) 둘다 아닌 경우

  • k가 1이 아니고 n이 짝수라면

  • i가 n보다 작은 자연수인동안 i, i+n, i+2⋅n, …, i+n⋅(k−1) 를 각각 한줄씩 배열해주면 된다.

    아니 이게 이렇게 간단히 된다고? 싶을 수 있지만 잘 생각해보자.

    i, i+n, i+2⋅n, …, i+n⋅(k−1)중 특정 범위를 선택했을때 전체합은 위와 같다.

    우리가 궁금한건 부분 범위의 평균이 정수가 나오냐, 인데 n이 짝수이므로 평균이 정수가 될 수 밖에 없다.

    그렇기 때문에 그렇게 출력해주는 코드만 짜면 끝난다.

이 문제는 좀 수학적 사고가 필요한 문제였다. B번을 볼 시간에 이 문제를 봤으면 풀 수 있었을 것 같은데, B 에서 멘탈이 털렸기 때문에 어쩔 수 없었던 것 같다.

#include<iostream>
using namespace std;
void solve(){

  int n,k,i,j;
  cin>>n>>k;
  if(k==1){cout<<"YES\n";for(i=1;i<=n;i++)cout<<i<<' ';return;}
  if(n%2==1){cout<<"NO\n";return;}

  cout<<"YES\n";
  for(i=1;i<=n;i++){
    for(j=1;j<=k;j++)cout<<(j-1)*n+i<<" ";
    cout<<endl;
  }

}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

그래서 결국엔 A만 4분만에 풀고 나머진 못풀고 잤다. 근데 몸 컨디션이 안좋았기 때문이었다고 변명을 좀 해보고 싶다. 문제에 맞는 아이디어를 잘 떠올리려면 대체 어떻게 해야 할까??

풀이를 보고 공부를 하면 할수록 현타만 온다… ‘아 이렇게 푸는거였구나!’ 하는 깨달음을 얻는 것도 좋긴 좋은데, 막상 실전에서는 그게 별로 도움이 안된다. 다음 코포까지는 시간이 좀 남았으니까 그 사이에는 내가 안봤던 회차 버츄얼이나 돌려봐야겠다.

Codeforces Global Round 19 C

C. Andrew and Stones

조건만족이 가능한 경우에 답이 res+=(a[1~n-2]+1)/2로 나온다는 것 까지는 캐치했지만, 조건만족이 불가능한 경우가 언젠지에 대한 판단이 안돼서 틀린 문제였다. 그냥 멘탈이 나가버려서 모르겠다 걍..

#include<iostream>
using namespace std;
int a[100001];
void solve(){
  int i,n,m=0;
  long long res=0;
  cin>>n;

  int tmp;
  cin>>tmp;
  for(i=0;i<n-2;i++){
    cin>>a[i];
    m=max(m,a[i]);
  }
  cin>>tmp;

  if(m==1||(n==3&&a[0]%2==1))cout<<"-1\n";
  else{
    for(i=0;i<n-2;i++)res+=(a[i]+1)/2;
    cout<<res<<'\n';
  }

}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B 모음집

​### codeforcesround #768 (div.2) B. Fun with Even subarrays

어떤 수열이 주어졌을 때, 우리는 일정 부분을 선택해서 같은 길이의 뒷부분을 복사해올 수 있다.

그렇다면 배열의 모든 숫자를 같게 만들려면 최소 몇 번 복사해야 할까?에 대한 문제다.

수열이 어떻게 돼있는지랑 상관없이 최소 log2 n 번만에 해결할 수 있다는 생각에 사로잡혀서 최적해를 구하는 아이디어를 떠올리지 못했던 것이 이 문제를 풀지 못한 이유였다.

#include<iostream>
using namespace std;
int a[200001];
void solve(){
  int i,n,res=0,x=1;
  cin>>n;
  for(i=1;i<=n;i++)cin>>a[i];
  while(x<n){
    if(a[n-x]==a[n]){
      x++;
      continue;
    }
    res++;
    x*=2;
  }
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

codeforcesround #767 (div.2) B. GCD Arrays

l부터 r까지의 숫자가 연속해있는 배열이 하나 있고 배열에서 두 수를 골라서 배열에서 빼고, 두 수의 곱을 배열에 넣는 연산을 k 번 할 수 있을 때 배열 전체의 최대공약수가 1보다 크도록 할 수 있는지를 구하는 문제이다.

문제에는 “Insert their product back into a”라고 써있었는데 이게 왜 곱셈이라는 뜻인진 잘 모르겠지만, 테스트케이스 설명을 보면 곱셈으로 대신한다는 게 맞는 것 같긴 하다.

일단은 최대공약수가 1보다 크려면 배열에 있는 수 모두가 공통된 약수를 가지고 있어야 한다.

근데 연속된 수들을 쫙 나열해놨을 때 가장 흔한 공통된 약수는 2이다. 그렇기 때문에 홀수에 짝수를 하나씩 짝지어서 곱하여 연산하는 것이 최소 연산으로 문제를 해결하는 방법이다.

l과 r이 같고 1이 아닌 경우, 또는 홀수의 개수보다 k가 크거나 둘이 같은 경우 YES,

아니면 NO를 출력해 주면 되는 문제였다.

#include<iostream>
using namespace std;
void solve(){
  int l,r,k;
  cin>>l>>r>>k;
  if(l==r&&l!=1)cout<<"YES1\n";
  else if(k>=((r+1)/2)-(l/2))cout<<"YES2\n";
  else cout<<"NO\n";
    /* ((r+1)/2)는 1부터 r까지의 홀수의 갯수,
    (l/2는 1부터 l까지의 홀수의 갯수를 뜻한다. */
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​### Educational Codeforces Round 121 B. Minor Reduction

어떤 수가 주어졌고 인접한 두 자릿수를 합한 것으로 그 자리를 대체하는 연산을 한번 수행할 때, 그 결과의 최댓값이 얼마인지를 구하는 문제이다.

일단 합이 10이 넘는 두 수를 합치는 게 그렇지 않은 것보다 이득이다.

그리고 합이 10이 넘는 두 수를 합치는 경우 최대한 오른쪽에 있는 두 수를 합치는 게 이득이다.

합이 10이 넘는 두 수가 없다면, 최대한 앞 자릿수를 키워주는 게 이득이다.

그대로 침착하게 코드 짜면 맞는 문제였다. 그리고 난 침착하지 못했다.

#include<iostream>
#include<algorithm>
using namespace std;
void solve(){
  string n;
  int i,j;
  cin>>n;
  for(i=n.length()-2;i>=0;i--){
    if((n[i]-'0')+(n[i+1]-'0')>=10){
      for(j=0;j<n.length();j++){
        if(j==i){cout<<(n[i]-'0')+(n[i+1]-'0');j++;}
        else cout<<n[j];
      }
      cout<<'\n';return;
    }
  }
  cout<<(n[0]-'0')+(n[1]-'0');
  for(i=2;i<n.length();i++)cout<<n[i];
  cout<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

codeforcesround #766 (div.2) B. Not Sitting

솔직히 이 문제는 왜 이게 맞는지 잘 모르겠다.

그렇기 때문에 설명은 패스…

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void solve() {
  int i,j,n,m;
  cin>>n>>m;
  vector <int> p;
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      int d=i+j;
      d=max(d,(n-1-i)+j);
      d=max(d,i+(m-1-j));
      d=max(d,(n-1-i)+(m-1-j));
      p.push_back(d);
    }
  }
  sort(p.begin(),p.end());
  for(i=0;i<n*m;i++)cout<<p[i]<<" ";
  cout<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

codeforcesround #765 (div.2) B. Elementary Particles

어떤 수열이 주어지고, 그 수열에서 같은 위치에 같은 숫자가 있도록 하는 동일한 길이의 최장 부분 수열의 크기를 구하는 문제이다. 이 문제는 정말 오랜만에 editorial을 보지 않고 푼 문제라서 좀 기쁘다.

근데 풀이 안 보고 푼 문제라서 문제 설명을 자세히 못하겠다. 항상 a 번 문제 설명을 날려 쓰는 거랑 마찬가지의 기분이랄까? 내가 풀이 설명을 쓰는 이유는 쓰면서 문제를 더 확실히 이해하기 위한 것인데, 이미 문제를 다 이해해서 풀고 난 후에는 뭘 더 써야겠다는 생각이 안든다. 그렇기 때문에 이 문제도 설명은 패스…^^

#include<iostream>
#include<string.h>
using namespace std;
int ch[150002];
void solve(){
  memset(ch,0,sizeof(ch));
  int i,n,res=0;
  cin>>n;
  for(i=1;i<=n;i++){
    int a;
    cin>>a;
    if(ch[a])res=max(res,min(ch[a],i)+min(n-ch[a],n-i));
    ch[a]=i;
  }
  if(res)cout<<res<<'\n';
  else cout<<"-1\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

codeforcesround #764 (div.3) B. Make AP

숫자 세 개 a, b, c가 주어지고 그중 하나의 수에 양의 정수를 아무거나 곱할 수 있을 때, {a, b, c}가 등차수열이 될 수 있는지 구하는 문제이다. 그냥 if 문으로 개무식하게 짠 코드이기 때문에 딱히 설명할게 없다.

#include<iostream>
using namespace std;
void solve(){
  int a,b,c;
  cin>>a>>b>>c;
  if(0<=c-b&&0<b-(c-b)&&a<=b&&(b-(c-b))%a==0)cout<<"YES\n";
  else if(0<=c-a&&(c+a)%2==0&&((c+a)/2)%b==0)cout<<"YES\n";
  else if(0<=b-a&&c<=(b+(b-a))*2&&(b+(b-a))%c==0)cout<<"YES\n";
  else{
    swap(a,c);
    if(0<=c-b&&0<b-(c-b)&&a<=b&&(b-(c-b))%a==0)cout<<"YES\n";
    else if(0<=c-a&&(c+a)%2==0&&((c+a)/2)%b==0)cout<<"YES\n";
    else if(0<=b-a&&c<=(b+(b-a))*2&&(b+(b-a))%c==0)cout<<"YES\n";
    else cout<<"NO\n";
  }
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

C. Elementary Particles

제목은 B 조지기지만, div3는 C까지 풀 만하기 때문에 풀어봤다. 큰 수부터 시작해서 체크가 안되어있는 n이하의 수가 나올때까지 2로 나눠보고, 그 수가 0이 되면 그냥 바로 NO를 출력해주면 되는 문제였다. 그렇게 복잡한 문제는 아닌데, 이런 깔끔한 방식을 떠올려내는게 어려운 것 같다. 솔직히 풀이 안봤으면 평생 못풀었을 것 같다.

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
int a[51];
bool ch[51];
void solve(){
  memset(ch,0,sizeof(ch));
  int i,n;
  cin>>n;
  for(i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  for(i=n-1;i>=0;i--){
    int x=a[i];
    while(x>n||ch[x])x/=2;
    if(x>0)ch[x]=1;
    else {cout<<"NO\n";return;}
  }
  cout<<"YES\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

Hello 2022

A. Stable Arrangement of Rook

n*n 크기의 체스판 위에, 룩이 k개 있다. 이때 k개의 룩이 각자 인접한 칸으로 움직여도 서로 죽일 수 없게 배치할 수 있을까? 만약 그렇게 배치할 수 있다면 어떻게 배치해야할까? 를 알아내는 문제였다.

체스의 룩은 직선으로 움직일 수 있다. 같은 열이나 행에 룩을 두개 배치하면 안된다는 뜻이다. 그리고 그 룩이 인접한 칸으로 움직인 후에 같은 열이나 행에 위치해서도 안되기 때문에, 룩의 현재행(또는 열)과 인접한 행(또는 열)에 다른 룩이 없도록 해주면 된다. 그렇게 배치하려면 대각선 라인을 타고 1칸 띄워서 하나씩 놓는게 가장 간단하고 예쁜 방법이다. 그래서 그렇게 코드를 짜줬다.

#include<iostream>
using namespace std;
void solve(){
  int i,j,n,k;
  cin>>n>>k;
  if(k>(n+1)/2)cout<<"-1\n";
  else{
    int cnt=0;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
        if(i==j&&(i+2)%2==0&&cnt++<k)cout<<'R';
        else cout<<'.';
      }
      cout<<'\n';
    }
  }
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B. Integers Shop

l부터 r까지의 정수를 c[i]원으로 파는 세트를 n개 가지고 있는 가게가 있다. 그리고 이 가게에서는 손님이 이미 산 정수 사이에 있는 수는 서비스로 그냥 준다. (동일한 정수는 두번 살 수도 없고, 서비스로 두번 받을 수도 없다.)

그렇다면 이 가게에서 가장 많은 갯수의 정수를 사려면 최소 얼마를 써야할까? 를 구하는 문제이다.

일단 서비스를 후하게 주는 가게이기 때문에, 가장 높은 정수와 가장 낮은 정수가 포함되어있는 세트를 두개 사는게 가장 이득이다. 하지만 가장 높은 정수와 가장 낮은 정수가 둘다 포함되어있는 세트가 있다면? 그걸 사는게 이득이다.

그래서 그냥 가장 높은 정수와 가장 낮은 정수의 값, 그리고 그 인덱스값을 저장하는 정수를 만들어서 그 네개만 실시간으로 갱신해주면서 출력할 생각이었는데, 그렇게 하면 가장 높은 정수와 가장 낮은 정수가 둘다 포함되어있는 세트에 대해서 처리해주는게 어려웠다. 그래서 가장 높은 정수와 가장 낮은 정수가 포함된 세트만 저장하는 친구를 만들어주고 범위가 가장 넓은 세트(가장 높은 정수와 가장 낮은 정수가 둘다 포함되어있는 세트를 포함함)를 저장하는 친구를 만들어줘서 그 둘을 비교해서 출력해주는 형식으로 코드를 짜보았다.

솔직히 이 글만 읽고 이 문제의 내용과 풀이를 이해할 수 있는 사람은 아무도 없을 것 같다. 처음엔 읽는 사람에게 조금이라도 도움이 돼야겠다는 생각으로 시작했던 블로그인데 그냥 나 혼자 복습하는 용도에 점점 더 가까워지고 있는 것 같다. 하지만 별로 상관없다.

암튼~ 아래가 이 문제의 코드다. 좀 더럽고 난해해보이지만, 어쩔 수 없는 문제였다.

using namespace std;
int c[100001];
void solve(){
  int i,j,n;
  pair<int,int> m,M,t;
  m.v=1000000001;m.ind=0;
  M.v=0;M.ind=0;
  t.v=0;t.ind=0;
  cin>>n;
  for(i=0;i<n;i++){
    int l,r;
    cin>>l>>r>>c[i];

    if(r-l>t.v) t.v=r-l;t.ind=i;
    else if(r-l==t.v) t.ind=(c[i]<c[t.ind])?i:t.ind;

    if(l<m.v) m.v=l;m.ind=i;
    else if(l==m.v) m.ind=(c[i]<c[m.ind])?i:m.ind;

    if(M.v<r) M.v=r;M.ind=i;
    else if(r==M.v) M.ind=(c[i]<c[M.ind])?i:M.ind;

    if(M.v-m.v<t.v) cout<<c[t.ind]<<'\n';
    else if(M.v-m.v==t.v) cout<<min(c[m.ind]+c[M.ind],c[t.ind])<<'\n';
    else cout<<c[m.ind]+c[M.ind]<<'\n';

  }
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

Good Bye 2021: 2022 is NEAR

A. Integer Diversity

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int cnt[101];
void solve(){
  memset(cnt,0,sizeof(cnt));
  int i,n,res=0;
  cin>>n;
  for(i=0;i<n;i++){
    int a;
    cin>>a;
    if(cnt[abs(a)]++<2)res++;
  }
  if(1<cnt[0])res--;
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}​

B. Mirror in the string

한 스트링에서 1~k번까지의 문자를 뒤집어서 붙인 문자열들중에 사전순으로 가장 빠른 것을 찾는 문제이다,

다음 문자가 더 작거나 같은 접미사(단, 첫번째 문자에서 같을때 제외) 를 구해서 잘 출력해주면 된다.

#include<iostream>
using namespace std;
void solve(){
  int i,j,n,k=1;
  string s;
  cin>>n>>s;
  while(k<n&&(s[k]<s[k-1]||(k>1&&s[k]==s[k-1])))k++;
  for(i=0;i<k;i++)cout<<s[i]; for(i=k-1;0<=i;i--)cout<<s[i];
  cout<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

C. Representive Edges

어떤 배열이 주어지고, 그 배열에서 숫자 몇개를 바꿔서 등차수열을 만들려면 최소 몇개의 숫자를 바꿔야하는지는 구하는 문제였는데, 이 문제가 진짜 개재밌었다. 왜 재미있었냐면 코드가 깔끔하게 복잡해서 재밌었다.

#include<iostream>
using namespace std;
int a[71];
void solve(){
  int i,j,k,n,res=2;
  cin>>n;
  for(i=0;i<n;i++)cin>>a[i];
  if(n<3){cout<<"0\n";return;}
  for(i=0;i<=n;i++){
    for(j=i+1;j<n;j++){
      int cnt=0;
      for(k=0;k<n;k++){
        if((i-k)*(a[j]-a[k])-(j-k)*(a[i]-a[k])==0)cnt++;
      }
      res=max(res,cnt);
    }
  }
  cout<<n-res<<"\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B 모음집 2

codeforcesround #763 (div.2) B. Game on Range

#include<iostream>
using namespace std;
bool map[1001][1001];
int n;
void f(int l,int r){
  int i,j;
  if(l==r){
    cout<<l<<' '<<r<<' '<<l<<'\n';
    map[l][r]=0;
    return;
  }

  if(map[l+1][r]==1){
    cout<<l<<' '<<r<<' '<<l<<'\n';
    map[l+1][r]=0;
    f(l+1,r);
    return;
  }

  for(i=l+1;i<r;i++){
    if(map[l][i-1]==1&&map[i+1][r]==1){
      cout<<l<<' '<<r<<' '<<i<<'\n';
      map[l][i-1]=0;
      map[i+1][r]=0;
      f(l,i-1); f(i+1,r);
      return;
    }
  }

  if(map[l][r-1]==1){
    cout<<l<<' '<<r<<' '<<r<<'\n';
    map[l][r-1]=0;
    f(l,r-1);
    return;
  }
}
void solve(){
  int i;
  cin>>n;
  for(i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    map[a][b]=1;
  }
  map[1][n]=0;
  f(1,n);
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

Educational Codeforces Round 120 B. Berland Music

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int arr[200001];
bool cmp(int a,int b){
  return arr[a]<arr[b];
}
void solve(){
  vector <int> L,DL;
  int i,n,p=1;
  cin>>n;
  for(i=0;i<n;i++)cin>>arr[i];
  for(i=0;i<n;i++){
    char tmp;cin>>tmp;
    if(tmp=='1')L.push_back(i);
    else DL.push_back(i);
  }
  sort(L.begin(),L.end(),cmp);
  sort(DL.begin(),DL.end(),cmp);
  for(i=0;i<DL.size();i++)arr[DL[i]]=p++;
  for(i=0;i<L.size();i++)arr[L[i]]=p++;
  for(i=0;i<n;i++)cout<<arr[i]<<' ';
  cout<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

codeforcesround Global Round 18 B. And It’s Non-Zero

난 이런 문제가 제일 싫다.

아이디어는 금방 떠올랐는데 미묘하게 식이 틀려서 그거 고치는데 3시간을 썼다.

이 방식 자체가 잘못된건가? 라는 생각을 수십번은 더 한 것 같다.

하지만 그런 의심이 든다고 하더라도 꿋꿋히 자신만으 ㅣ 길을 걸어가는 사람이 성공을 손에 쥘 수 있다는 말을 어디서 본 것 같다. 아직도 푼게 믿기지 않는다. 근데 시간이 너무 아ㅏㄲ밥다 이거 풀시간에 딴거풀걸

#include<iostream>
#include<cmath>
using namespace std;
int cal(int n,int i){
  int v;
  if(n<pow(2,i))v=n+1;
  else{
    v=(n/((int)pow(2,i))+1)/2*(pow(2,i));
    if((n/((int)pow(2,i))+1)>2&&(n/((int)pow(2,i)))%2==0){
      v+=n%(int)pow(2,i)+1;
    }
  }
  return v;
}
void solve(){
  int i,a,b,res;
  cin>>a>>b;
  res=b-a;
  for(i=0;i<20;i++)res=min(res,+cal(b,i)-cal(a-1,i));
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

​

codeforcesround #762 (div.3) B. Squares and Cubes

제곱근이랑 세제곱근을 컴퓨터가 계산해줘서 참 다행이다.

#include<iostream>
#include<cmath>
using namespace std;
void solve(){
  long long i,n,res=1;
  cin>>n;
    int x=sqrt(n);
    int y=cbrt(n);
    int z=sqrt(y);
    cout<<x+y-z<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B 모음집 3

Ecucational Codeforces Round 119 A. Equal or not Equal

#include<iostream>
using namespace std;
void solve(){
  string s;
  int i,cnt=0;
  cin>>s;
  for(i=0;i<s.length();i++)if(s[i]=='N')cnt++;
  if(cnt!=1)cout<<"YES\n";
  else cout<<"NO\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}
​```

### B. Triangles on a Rectangle

```c
#include<iostream>
using namespace std;
long long max(long long a,long long b){
  if(a>b)return a;
  else return b;
}
void solve(){
  int i,j,w,h;
  long long res=0;
  cin>>w>>h;
  for(i=0;i<2;i++){
    int k,a,b;
    cin>>k>>b;
    for(j=1;j<k;j++){
      cin>>a;
      res=max(res,(long long)(a-b)*h);
    }
  }
  for(i=0;i<2;i++){
    int k,a,b;
    cin>>k>>b;
    for(j=1;j<k;j++){
      cin>>a;
      res=max(res,(long long)(a-b)*w);
    }
  }
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}
​

​

Codeforces Round #761 (div.2) A. Forbidden Subsequence

#include<iostream>
#include<cstring>
using namespace std;
int cnt[27];
void solve(){
  memset(cnt,0,sizeof(cnt));
  int i,j;
  string s,t;
  cin>>s>>t;
  for(i=0;i<s.length();i++)cnt[s[i]-'a']++;
  if(t=="abc"&&cnt[0]&&cnt[1]&&cnt[2]){
    for(j=0;j<cnt[0];j++)cout<<'a';
    for(j=0;j<cnt[2];j++)cout<<'c';
    for(j=0;j<cnt[1];j++)cout<<'b';
    for(i=3;i<26;i++)for(j=0;j<cnt[i];j++)cout<<(char)(i+'a');cout<<'\n';
  }else{for(i=0;i<26;i++)for(j=0;j<cnt[i];j++)cout<<(char)(i+'a');cout<<'\n';}
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B.GCD problem

#include<iostream>
using namespace std;
int gcd(int a,int b){
  if(a<b) return gcd(b,a);
  if(b==0) return a;
  else return gcd(b,a%b);
}
void solve(){
  int i,n;
  cin>>n;
  for(i=2;i<n;i++){
    if(gcd(n-i-1,i)==1){
      cout<<i<<" "<<n-1-i<<" 1\n";
      return;
    }
  }
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

Codeforces Round #779 (Div. 2)

A. Marin and Photoshoot

0과 0사이에 0의 갯수보다 1의 갯수가 더 많도록 문자열을 수정하려면 1을 최소 몇개 출력해야하는지를 구하는 문제였다. 사이에 껴있는 1의 갯수가 3개 이하면 그 사이 1의 갯수가 3개가 넘도록 해주면 된다.

#include<iostream>
#include<vector>
using namespace std;
void solve(){
  vector <int> V;
  V.clear();
  int i,n,res=0;
  string s;
  cin>>n>>s;
  for(i=0;i<n;i++)if(s[i]=='0')V.push_back(i);
  for(i=1;i<V.size();i++){
    if(V[i]-V[i-1]<=2){
      cout<<2-(V[i]-V[i-1])+1<<endl;
      res+=2-(V[i]-V[i-1])+1;
    }
  }
  cout<<res<<'\n';
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

B. Marin and Anti-coprime Permutation

1부터 n까지의 정수로 이뤄진 집합A가 있다. 이 집합 A {a11,a22,a33,a44…}의 최소공배수는 1 이상이다.

그럴때 배열 A가 될 수 있는 순열은 총 몇개인가? 를 구하는 문제였다.

​

일단 gcd가 k라고 쳐보자. k를 기존에 약수로 가지고 있는 수는 k번마다 한번씩 나타난다. 근데 k가 3이상인 경우는 있을 수 없다. 왜냐하면 저 기본으로 곱해주는 1,2,3,4,5..들이 있고 숫자가 1,2,3,4,5..들이 있으니까 3을 약수로 가지고 있는 애들끼리 잘 합쳐준다고 해도 숫자 3개중에 하나는 3을 약수로 지닐 수가 없다.

그렇다면 무조건 gcd가 2이므로 짝수엔 홀수를 곱해주고 홀수엔 짝수를 곱해줘야한다. 근데 만약에 홀수의 갯수가 짝수의 갯수보다 더 많다면? gcd를 2로 만드는게 무조건 불가능하다. 무조건. n이 홀수인 경우는 그냥 제껴준다.

if(n%2==1){ cout<<0<<'\n; return 0; }

반대로 n이 짝수인 경우. 홀수의 갯수와 짝수의 갯수는 똑같다. 그리고 배열에 기본적으로 곱해지는 수들의 홀·짝수의 갯수도 똑같다. 곱해지는 수들의 배치 순서는 이미 정해져있으므로, (1부터 n까지 순서대로) 나머지 수들만 어떻게 잘 해결을 해주면 된다. 그럼 걍 답은 (n/2)!*(n/2)! 이거다. 근데 수가 1000까지니까 수 하나씩 곱해주면서 998,244,453로 나눈 나머지로 바꿔주면 풀린다.

#include<iostream>
#include<vector>
using namespace std;
void solve(){
  long long res=1;
  int i,n;
  cin>>n;
  if(n%2==1){cout<<"0\n";return;}
  for(i=2;i<=n/2;i++){
    res=(res*i*i)%998244353;
  }
  cout<<res<<"\n";
}
int main(){
  int T;
  cin>>T;
  while(T--)solve();
}

C. Shinju and the Lost Permutation

심상치 않은 문제라고 생각했는데 생각보다 별거 아닌 문제였다. 문제에 주어진 상황이 어떤 상황인지를 잘 생각해보면 간단하게 나온다. 오늘의 자습시간을 불태워서 풀어야겠다고 생각했었는데 너무 허무하다. 코드 짜면서도 아니 이게 진짜 맞나…?라는 의구심이 계속해서 내면에서 솟구쳤으나 정말로 이게 맞았다.

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
bool solve(){
  queue <int> Q;
  int res[100001];
  int i,n;
  int ch=0;
  cin>>n;
  for(i=0;i<n;i++){
    int a;
    cin>>a;
    Q.push(a);
    if(a==1)ch++;
  }
  if(ch!=1)return 0;
  int s=Q.size();
  for(i=0;i<s&&!Q.empty();i++){
    int x=Q.front();
    if(x==1)break;
    Q.pop(); Q.push(x);
  }
  if(Q.front()!=1)return 0;
  Q.pop();
  int b=1;
  while(!Q.empty()){
    int x=Q.front(); Q.pop();
    if(b+1<x)return 0;
    b=x;
  }
  return 1;
}
int main(){
  int T;
  cin>>T;
  while(T--)cout<<(solve()?"YES\n":"NO\n");
}