[atcoder] Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）

3 솔

https://atcoder.jp/contests/abc222

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

1. A

- 아주 간단한 문제 : "%04d"..

#include <iostream>
#include <string>
using namespace std;
 
 
int main() {
  string s;
  cin>>s;
 
  for(int i = 0; i < 4-s.size();i++) {
    	cout<<0;
  }
  cout<<s;
}

#include<stdio.h>
int main(){
	int n;
	scanf("%d",&n);
	printf("%04d\n",n);
}

2. B

- 아주 간단한 문제 : b 보다 작은 횟수..

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int a, b;
  cin>>a>>b;
  vector<int> c(a);
  int answer = 0;
  for(int i = 0; i < a; i++) {
    cin>>c[i];
    if(c[i] <b) {
      answer++;
  }
  }
    cout<<answer;
}

 

3. C

- 가위바위보 문제 - 랭크순으로 정렬하여 앞에서부터 두명씩 가위바위보

#include <algorithm>
 
using namespace std;
 
vector<vector<char>> A;
int N, M;
 
void solve()
{
    vector<pair<int, int>> rank(A.size());
    for (int i = 0; i < rank.size(); i++)
    {
        rank[i] = {0, i};
    }
    for (int m = 0; m < M; m++)
    {
        for (int a = 0, b = 1; a < rank.size(); a += 2, b += 2)
        {
            int aa = rank[a].second;
            int bb = rank[b].second;
            // C0 = scissor. < G1= rock , < P2 = paper
            if ((A[aa][m] + 1) % 3 == A[bb][m])
            {
                rank[b].first++;
            }
            else if (A[aa][m] == A[bb][m])
            {
            }
            else
            {
                rank[a].first++;
            }
        }
        sort(rank.begin(), rank.end(), [](pair<int, int> &aaa, pair<int, int> &bbb)
             {
                 if (aaa.first == bbb.first)
                     return aaa.second < bbb.second; // 작은것 위로
                 else
                     return aaa.first > bbb.first; // 많이 이긴놈 위로
             });
    }
    for (int i = 0; i < rank.size(); i++)
    {
        cout << rank[i].second + 1 << "\n";
    }
}
 
int main()
{
    cin >> N >> M;
    A.clear();
    A.resize(2 * N, vector<char>(M));
    for (int i = 0; i < 2 * N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> A[i][j];
            if (A[i][j] == 'C')
            {
                A[i][j] = 0;
            }
            if (A[i][j] == 'P')
            {
                A[i][j] = 2;
            }
            if (A[i][j] == 'G')
            {
                A[i][j] = 1;
            }
        }
    }
    solve();
}

 

4. D

- 수열 A와 B 가 주어지는데 이 두 수열 사이에 올 수 있는 수열의 개수들을 세는 문제

  (Ai <= Ci <= Bi 인 C수열들을 찾는 문제)

https://atcoder.jp/contests/abc222/editorial/2761

int N;
vector<int> A;
vector<int> B;

const long long MOD = 998244353;
long long cached[3001][3001];
long long dp(int idx, int left)
{
    if (idx == A.size())
    {
        return 1;
    }
    long long &ret = cached[idx][left];
    if (ret == -1)
    {
        ret = 0;
        int lo = max(left, A[idx]);

        ret = (ret + dp(idx + 1, lo)) % MOD;
        if (lo + 1 <= B[idx])
        {
            ret = (ret + dp(idx, lo + 1)) % MOD;
        }
    }
    return ret % MOD;
}
void solve()
{
    cout << dp(0, 0);
}

// 아래는 시간초과 풀이 -> 한 부분문제당 m개의 부분문제를 생성하기 때문. (위 풀이는 2개의 부분문제를 생성)

long long dp(int idx, int left)
{
    if (idx == A.size())
    {
        return 1;
    }
    long long &ret = cached[idx][left];
    if (ret == -1)
    {
        ret = 0;
        for (int lo = max(left, A[idx]); lo <= B[idx]; lo++)
        {
            ret = (ret + dp(idx + 1, lo)) % MOD;
        }
    }
    return ret % MOD;
}

//editorial 풀이

#include <iostream>
#include <vector>

#include "atcoder/modint.hpp"
using namespace std;
using mint = atcoder::modint998244353;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (auto& x : A) cin >> x;
  for (auto& x : B) cin >> x;
  int MAX = 3000;
  vector dp(vector(N + 1, vector(MAX + 1, mint{0})));
  dp[0][0] = 1;
  rep(i, N + 1) {
    rep(j, MAX) dp[i][j + 1] += dp[i][j];
    if (i != N) {
      for (int j = A[i]; j <= B[i]; j++) dp[i + 1][j] += dp[i][j];
    }
  }
  cout << dp[N][MAX].val() << "\n";
}