AtCoder Beginner Contest 202

1. A. Three Dice

      

      

      

    
    

      <cpp />
    
void solution() {
      cin >> a >> b >> c;
      cout << 21-a-b-c;
}

2. B. 180°

      

      

      

    
    

      <cpp />
    
char f(char x) {
      if (x == '6') return '9';
      if (x == '9') return '6';
      return x;
}

void solution() {
      cin >> s;
      reverse(ALL(s));
      for (char c : s) {
          cout << f(c);
      }
}

구현에서 요령 피우면 쉽게 풀 수 있다. $f(x)$를 설정하는 것과 reverse 함수를 활용하는 것이 요령.

주의할 점은 문자 형태로 ' '를 씌워야 한다는 것이다.

3. C. Made Up

      

      

      

    
    

      <cpp />
    
void input() {
      cin >> n;
      REP(i,1,n) cin >> a[i];
      REP(i,1,n) cin >> b[i];
      REP(i,1,n) cin >> c[i];
}

void solution() {
      input();
      REP(i,1,n) ++cnt[b[c[i]]];
      ll ans = 0;
      REP(i,1,n) ans += cnt[a[i]];
      cout << ans;
}

약간 고민하면 배열에 $N$ 범위를 담는게 가능하고, $\mathrm{cnt}$ 배열로 만들어서 활용하면 되겠단 걸 알 수 있다.

4. D. aab aba baa

      

      

      

    
    

      <cpp />
    
ll C(int n, int r) {
      if (n == r || r == 0) return 1;
      if (ready[n][r]) return dp[n][r];
      ready[n][r] = true;
      return dp[n][r] = C(n-1,r)+C(n-1,r-1);
}

void solution() {
      cin >> a >> b >> k;
      while (a+b) {
            if (!a || !b) break;
            if (ll c = C(a-1+b,b); c < k) {
                  k -= c; cout << 'b'; --b;
            } else {
                  cout << 'a'; --a;
            }
      }
      REP(i,1,a) cout << 'a';
      REP(i,1,b) cout << 'b';
}

진법의 아이디어이다. 전에 포스팅한 2020.11.09 - [수학/조합론 공부] - 계승 진법이 이해에 도움이 될 것이라 생각한다.

뭐 엄밀하게 증명도 가능하겠는데, 바로 알겠으니 필요 없을 듯.