AtCoder Beginner Contest 206（Sponsored by Panasonic)

A. Maxi-Buying

$\lfloor 1.08 \times N \rfloor$ 값과 206을 비교하는 문제이다.

#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 n;
  cin>>n;
  int res=1.08*n;
  if(res<206) cout<<"Yay!";
  else if(res==206) cout<<"so-so";
  else cout<<":(";
  return 0;
}

B. Savings

돼지 저금통에 $i$번째 날에 $i$엔을 넣을 때, 저금통에 $N$엔보다 많거나 같을 날을 계산하는 문제이다.

$N$의 범위가 $N \le 10^9$이므로 완전탐색할 수 있습니다.

#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);
  ll n;
  cin>>n;
  ll i=1;
  while(1) {
    ll res=i*(i+1)/2; // 1부터 N까지 더하는 공식
    if(res>=n) {
      cout<<i;
      return 0;
    }
    i++;
  }
  return 0;
}

C. Swappable

주어진 배열 $A = (A_1,A_2,...,A_N)$가 있고, 다음 두 조건을 만족하는 $(i,j)$의 수를 구하는 문제이다.

• $A_i \ne A_j$
• $1\le i < j \le N$

예를들면, 1 2 3 1 2 3이 주어지는 경우 총 12개가 가능하다.

• $(0,1)$, $(0,2)$, $(0,4)$, $(1,5)$
• $(1,2)$, $(1,4)$, $(1,5)$
• $(2,3)$, $(2,4)$
• $(3,4)$, $(3,5)$
• $(4,5)$

여기서 알 수 있는 것은 현재 인덱스보다 뒤로 가면서 본인과 같은 값을 제외한 개수를 더해주고 있다.

그래서 미리 각 원소의 개수를 세어준 후 하나씩 돌면서 (뒤에 남은 원소의 개수 - 현재 가리키는 수와 같은 수의 개수)를 누적해준다.

#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);
  map<int,int> m;
  for(auto &it : a) {
    cin>>it;
    m[it]++;
  }
  ll ans=0;
  for(int i=0;i<n-1;i++) {
    // cout<<a[i]<<' '<<(n-i-1)-(m[a[i]]-1)<<endl;
    ans+=(n-i-1)-(m[a[i]]-1);
    m[a[i]]--;
  }
  cout<<ans;
  return 0;
}

D. KAIBUNsyo

주어진 수열이 팰린드롬이 되기 위해 최소 몇번 바꿔야 하는지 계산하는 문제이다.

에디토리얼을 보면 수열들을 그래프로 연결된 것으로 가정하여 해결하고 있다.

• $a_i$와 $a_{n-1-i}$가 연결되어있다고 가정

연결된 노드들이 $k$개의 원소로 구성되어 있다면 $k-1$번의 변환을 통해 같은 원소로 통일할 수 있다.

예를들어 1 5 3 2 5 2 3 1인 수열이 들어왔다고 가정하면 $(2,3,5)$와 $(1)$이 각각 그래프를 이루고 있다고 할 수 있다.

이때, $(2,3,5)$의 집합은 2번의 연산을 통해 같은 원소로 변환할 수 있고 $(1)$은 연산을 할 필요가 없다. 따라서 위의 수열은 2번만에 팰린드롬으로 만들 수 있다.

DFS나 BFS를 이용해 그래프를 이루는 원소들의 개수를 세어준 후 1을 빼준 값을 누적해서 계산하면 된다.
또한, Disjoint-set을 이용해서 문제를 해결할 수도 있다.

#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;

vector<int> graph[200001];

void dfs(int v, vector<int> &visit, int& count) {
  if(graph[v].empty()) return;
  visit[v]=1;
  for(int next : graph[v]) {
    if(!visit[next]) {
      visit[next]=1;
      count++;
      dfs(next,visit,count);
    }
  }
}

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);
  for(auto &it : a) cin>>it;
  for(int i=0;i<n/2;i++) {
    graph[a[i]].push_back(a[n-i-1]);
    graph[a[n-i-1]].push_back(a[i]);
  }
  vector<int> visit(200001,0);
  int ans=0;
  for(int i=0;i<n/2;i++) {
    if(!visit[a[i]]) {
      int count=1;
      dfs(a[i],visit,count);
      ans+=count-1;
    }
  }
  cout<<ans;
  return 0;
}