Educational Codeforces Round 90 (Rated for Div. 2) (A ~ D) 풀이

A. Donut Shops

도넛을 낱개로 파는 첫번째 가게, 도넛을 묶음으로 파는 두번째 가게가 있다.

첫번째 가게의 도넛의 가격 a, 묶음으로 파는 두번째 가게의 도넛의 가격 b개당 c 가 주어질 때

도넛을 최소 x개 사야할 때 첫번째 가게가 이득일 수 있는 x, 두번째 가게가 이득일 수 있는 x를 찾아 출력하는 문제였다.

 

간단하지만 시간이 좀 걸렸던 발상 + 수학문제이다.

우선 첫번째 가게가 이득일 수 있는 최고의 경우는 1개만 사도될 때 일 것이다.

따라서 a < c 이면 x = 1이 될 수 있다. 아닐 경우 이득일 경우가 존재하지 않을 것이다.

 

두번째 가게가 이득일 수 있는 최고의 경우는 묶음 갯수만큼만 구매해야 할 때 이다.

따라서 a * b > c  라면 b개를 샀을 때 두번째 가게가 이득이 될 수 있다.

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
 
int T;
 
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 
 
  cin >> T;
 
  while(T--) {
    ll a, b, c;
    cin >> a >> b >> c;
    ll ans1 = -1;
    ll ans2 = -1;
    if(a < c) {
      ans1 = 1;
    }
    if(c < a * b) {
      ans2 = b;
    }
    cout << ans1 << ' ' << ans2 << endl;
  }
} 

 

B. 01 Game

게임 이론이다.

1과 0으로 이루어진 문자열에서 인접한 문자가 다를 경우 그 둘을 삭제할 수 있다.

삭제가 불가능할 경우 그사람의 패배. 선공은 앨리스이다.

0과 1이 존재하는 문자열에서 0과 1 둘 중 적은 것은 항상 다른 수와 인접하게 될 것이다.

따라서 지울 수 있는 횟수는 0과 1의 갯수중 최소 횟수가 될 것이다.

선공은 앨리스이므로 횟수가 홀수일 경우 앨리스의 승리, 짝수일 경우 밥의 승리가 되겠다.

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
 
int T;
 
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 
 
  cin >> T;
 
  while(T--) {
    string s;
    cin >> s;
    bool flag = true;
    int one = 0;
    int zero = 0;
    for(int i = 0 ; i < s.size() ; i++) {
      if(s[i] == '0') zero++;
      if(s[i] == '1') one++;
    }
    int tmp = min(one, zero);
 
    if(tmp % 2 == 0) {
      cout << "NET" << endl;
    }
    else {
      cout << "DA" << endl;
    }
  }
} 

 

C. Pluses and Minuses

+와 -로 이루어진 문자열이 이루어진다.

다음 수도코드를 실행시켰을 때 나올 수 있는 res값을 출력하는 문제.

 

코드를 보면 관찰할 수 있는 점은

1. 0부터 inf로 증가하는 cur이 문자열을 모두 순회하는 동안 양수로 유지될 경우 프로그램이 종료된다.

2. 문자열을 순회하던 도중 cur이 음수가 될 경우 문자열의 순회를 종료한다.

 

cur은 0부터 증가하므로 cur이 0일때는 -1이 처음 등장하는 위치, cur이 1일때는 -2이 처음 등장하는 위치, ...를 찾고

못찾았을 경우에는 문자열을 모두 순회한 뒤 양수로 종료되었다는 의미이므로 문자열 길이 만큼을 더해준 뒤 답을 출력했다.

 

음수가 처음 등장하는 위치는 stl map을 이용했다.

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;

int T;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  cin >> T;

  while(T--) {
    string s;
    cin >> s;
    int num = 0;
    map<int, int> m;
    int minnum = INF;
    for(int i = 0 ; i < s.size() ; i++) {
      if(s[i] == '+') num++;
      else if(s[i] == '-') num--;
      if(num < 0) {
        if(m.find(num) == m.end()) {
          m.insert(mp(num, i + 1));
        }
      }

    }
    ll ans = 0;
    int cur = -1;
    while(1) {
      if(m.find(cur) == m.end()) {
        ans += s.size();
        break;
      }
      else {
        ans += m[cur];
      }
      cur--;
    }
    cout << ans << endl;
  }
} 

D. Maximum Sum on Even Positions

배열의 구간 [L, R]의 서브스트링을 최대 한번 뒤집어서 짝수 인덱스의 합을 최대로 하여 그 합을 출력하는 문제

대회 중에 풀긴 했지만 너무 늦게 풀었다.

홀수개는 바꿔봐야 짝수 인덱스는 변하지 않는다는 걸 너무 늦게 발견했다.

 

배열 7,3,1 을 생각해보자 이것을 3개를 전부 뒤집으면 1,3,7이되므로 짝수 인덱스는 1, 7과 7, 1로 동일하다.

꼭 3개가 아니여도 홀수개를 뒤집었을 경우에는 짝수 인덱스는 동일하게 유지된다는 것을 알 수 있다.

따라서 시작점이 0, 1일때로 나누어 수를 바꾸었을 때의 손익값을 저장하여 dp를 이용해 최대 연속구간합을 구해 둘 중 최댓값을 원래 짝수 인덱스의 합 값에서 더해주자.

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;

int T;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  cin >> T;

  while(T--) {
    int n;
    vector<ll> arr;

    cin >> n;
    ll sum = 0;
    for(int i = 0 ; i < n ; i++) {
      ll x;
      cin >> x;
      if(i % 2 == 0) sum += x;
      arr.pb(x);
    }
    if(n == 1) {
      cout << arr[0] << endl;
      continue;
    }
    else if(n == 2) {
      cout << max(arr[0], arr[1]) << endl;
      continue;
    }
    vector<ll> diff1;
    vector<ll> diff2;

    for(int i = 1 ; i < arr.size() ; i+= 2) {
      diff1.pb(arr[i] - arr[i - 1]);
    } 

    for(int i = 2 ; i < arr.size() ; i += 2) {
      diff2.pb(arr[i - 1] - arr[i]);
    }

    ll ans = 0;
    ll mx1 = 0;
    ll dp1[n + 1] = {};
    dp1[0] = max((ll)0, diff1[0]);
    mx1 = max(dp1[0], (ll)0);
    for(int i = 1 ; i < diff1.size() ; i++) {
      dp1[i] = max((ll)0, dp1[i - 1]) + diff1[i];
      mx1 = max(mx1, dp1[i]);
    }
    ans = max(ans, sum + mx1);
    ll mx2 = 0;
    ll dp2[n + 1] = {};
    dp2[0] = max((ll)0, diff2[0]);
    mx2 = max(dp2[0], (ll)0);
    for(int i = 1 ; i < diff2.size() ; i++) {
      dp2[i] = max((ll)0, dp2[i - 1]) + diff2[i];
      mx2 = max(mx2, dp2[i]);
    }
    ans = max(ans, sum + mx2);
    cout << ans << endl;
  }
}