Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）

A. Tiny Arithmetic Sequence

어떠한 배열 A에 대해 $A_3-A_2=A_2-A_1$이 되는 경우를 찾아내는 문제이다.

배열 A에 대해 순열을 구하면서 위의 조건이 맞는지 확인하면 된다.

#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);
  vector<int> a(3);
  for(int i=0;i<3;i++) cin>>a[i];
  do{
    if(a[2]-a[1]==a[1]-a[0]) {
      cout<<"Yes";
      return 0;
    }
  }while(next_permutation(a.begin(),a.end()));
  cout<<"No";
  return 0;
}

---

B. Do you know the second highest mountain?

산의 이름과 고도가 입력으로 주어지는데 두 번째로 높은 산의 이름을 출력하는 문제이다.

map을 이용하면 쉽게 풀 수 있다.

#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;
  map<int,string> m;
  for(int i=0;i<n;i++) {
    string s;
    int h;
    cin>>s>>h;
    m[h]=s;
  }
  auto it=m.end();
  it--; it--;
  cout<<it->second;
  return 0;
}

---

C. Secret Number

조건에 맞는 비밀번호의 개수를 구하는 문제이다. 비밀번호의 자릿수는 4자리 이므로 0000부터 9999까지 조건에 맞는 비밀번호를 찾아내면 된다.

조건에 해당하는 문자열 S는 길이가 10이므로 $O(M|S|), M=10^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);
  string s;
  cin>>s;
  int ans=0;
  for(int i=0;i<=9999;i++) {
    vector<bool> a(10,false);
    int t=i;
    for(int j=0;j<4;j++) { // t가 1000미만인 경우 '0'까지 포함시켜야 한다
      a[t%10]=true;
      t/=10;
    }
    bool flag=true;
    for(int j=0;j<10;j++) {
      if(s[j]=='o' && !a[j]) flag=false;
      if(s[j]=='x' && a[j]) flag=false;
    }
    if(flag) ans++;
  }
  cout<<ans;
  return 0;
}