AISing Programming Contest 2021（AtCoder Beginner Contest 202）

A. Three Dice

3개의 주사위를 굴렸을 때 윗면에 있는 숫자를 보고 밑면의 숫자를 더하는 문제이다.

(1,6), (2,5), (3,4)가 맞은편에 있는 것을 구현하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int ans=0;
  for(int i=0;i<3;i++) {
    int a;
    cin>>a;
    if(a==1) ans+=6;
    else if(a==2) ans+=5;
    else if(a==3) ans+=4;
    else if(a==4) ans+=3;
    else if(a==5) ans+=2;
    else ans+=1;
  }
  cout<<ans;
  return 0;
}

---

B. 180°

0, 1, 6, 8, 9로 이루어진 문자열 S를 180도 뒤집었을 때 나타나는 문자열을 출력하는 문제이다.

180도 뒤집었을 때 6 -> 9, 9 -> 6으로 바뀌는 것만 처리해주면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  string s;
  cin>>s;
  string ans="";
  for(int i=s.size()-1;i>=0;i--) {
    char c=s[i];
    if(c=='6') ans+='9';
    else if(c=='9') ans+='6';
    else ans+=c;
  }
  cout<<ans;
  return 0;
}

---

C. Made Up

주어진 A, B, C 배열에서 $A_i=B_{C_j}$를 만족하는 $(i,j)$의 수를 구하는 문제이다.

$N$의 범위가 $1≤N≤10^5$이므로 $O(N^2)$의 시간 복잡도를 가져서는 안된다.

그래서 B와 C를 map을 통해 미리 $B_{C_j}$의 수를 계산해놓았다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  vector<int> a(n+1), b(n+1), c(n+1);
  map<int,int> bm;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++) cin>>b[i];
  for(int i=1;i<=n;i++) {
    cin>>c[i];
    bm[b[c[i]]]++;
  }
  // for(auto it : bm) cout<<it.first<<' '<<it.second<<endl;
  ll ans=0;
  for(int am : a) {
    if(b[am]!=0) ans+=bm[am];
  }
  cout<<ans;
  return 0;
}

---

D. aab aba baa

editorial 참고

‘a’를 A번, ‘b’를 B번 반복하여 만들 수 있는 모든 문자열 중 사전식 순서로 정렬했을 때, K번째 문자열을 출력하는 문제이다.

만약, ‘a’로 시작하는 문자열의 수가 K보다 같거나 많다면 우리가 찾고자 하는 문자열은 ‘a’로 시작하는 것이 맞다. K보다 작다면 ‘b’로 시작한다.

예를들어, 3개의 ‘a’와 1개의 ‘b’를 가지고 2번째 문자열을 찾으려고 한다.

• 이때, 앞이 a로 시작하여 남은 문자들로 만들 수 있는 문자열은 aab, aba로 2개이다. 따라서, 첫 번째 문자는 ‘a’가 확실하다.
• 다음 1개의 ‘a’와 1개의 ‘b’를 가지고 2번째 문자열을 찾으려고 한다. 이때, ab로 1개의 문자열을 만들 수 있으므로 다음 글자는 ‘b’가 확실하다.
• 남은 글자 ‘a’를 뒤에 붙이면 aaba가 우리가 찾고자하는 문자열이다.

그럼 ${}_i \mathrm{C}_j$ 를 $C(i,j)$ 라 표현하고 $S(i,j,k)$를 ‘a’를 i번, ‘b’를 j번 사용하여 만든 문자열 중 사전식 순서로 k번째 문자열이라고 가정하자.

다음의 조건을 반복하여 K번째 문자열을 찾을 수 있다.

1. if $i = 0$, $j$ 번 반복한 ‘b’
2. if $j = 0$, $i$ 번 반복한 ‘a’
3. if $i>0, j>0$
   • if $C(i-1,j) ≥ k$, ‘a’ + $S(i-1,j,k)$
   • if $C(i-1,j) < k$, ‘b’ + $S(i,j-1,k-dp[i-1][j])$

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

ll dp[31][31];

string find_string(int a,int b,ll k) {
  if(a==0) {
    string tmp="";
    while(b--) tmp+='b';
    return tmp;
  }
  if(b==0) {
    string tmp="";
    while(a--) tmp+='a';
    return tmp;
  }
  if(k<=dp[a-1][b]) {
    return "a"+find_string(a-1,b,k);
  }
  else {
    return "b"+find_string(a,b-1,k-dp[a-1][b]);
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int a,b;
  ll k;
  cin>>a>>b>>k;
  // dp[i][j] = a를 i개 뽑고 b를 j개 뽑을 때 만들 수 있는 문자열의 경우의 수
  dp[0][0]=1;
  for(int i=0;i<=a;i++) {
    for(int j=0;j<=b;j++) {
      if(i>0) dp[i][j]+=dp[i-1][j];
      if(j>0) dp[i][j]+=dp[i][j-1];
    }
  }
  cout<<find_string(a,b,k);
  return 0;
}