Codeforces Round #462 (Div. 2)

* Codeforces Round #462 (Div. 2)

A. A Compatible Pair

  곱셈에 대해 가장 작게 만들기 위해 for문을 세 개로 구성해서 Brute force로 알아낼 수 있다.

  O(N^2 M)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <iostream> using namespace std; using ll = long long; ll min_v(ll a, ll b) { return a < b ? a : b; } ll max_v(ll a, ll b) { return a > b ? a : b; } int main() {     int n, m,i,j,k;     ll ans=1e18, tmp, A[50], B[50];     cin >> n >> m;     for (i = 0; i < n; i++) cin >> A[i];     for (i = 0; i < m; i++) cin >> B[i];       for (i = 0; i < n; i++) {         tmp = -1e18;         for (j = 0; j < n; j++) {             if (i == j) continue;             for (k = 0; k < m; k++)                 tmp = max_v(tmp, A[j] * B[k]);         }         ans = min_v(ans, tmp);     }     cout << ans;     return 0; }

B. A Prosperous Lot

  숫자 안에 갇힌 공간의 수를 세는 프로그램이다. 1e18을 넘어선 안되는 점을 감안하고, 0이 맨 앞에 없다는 것을 생각한다면 8과 6,4로 충분히 구현할 수 있음을 알 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include <iostream> using namespace std; using ll = long long; int main() {     int k,pos=0;     ll n = 0;     cin >> k;     while (pos < 18 && k) {         n *= 10;         if (k == 1) n += 6, k--;         else n += 8, k -= 2;         pos++;     }     cout << (k ? -1 : n);     return 0; }

C. A Twisty Movement

  부분 수열과 특정 증명 방법을 통해 알 수 있다.

  부분 수열에 대해 1..2..1..2 형식일 때 중간 2..1을 뒤집을 때 최대가 되는 부분을 찾아야한다.

  1212 순서에 대해 먼저 각 part가 끝나는 경우에 대해서 처리해준다. 그 다음 각 part 다음 숫자에 대해 처리할 때 앞에서 처리한 것에 대해 dynamic하게 처리해준다.

시간 복잡도 : O(N)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <cstdio> int max_v(int a, int b) { return a > b ? a : b; } int main() {     int n, i, j, *A, ans = 0, *up, *down, tmp, dp[5][2001] = {}, parts[5] = { 0,1,2,1,2 };     scanf("%d", &n);     A = new int[n + 1]{};     for (i = 1; i <= n; i++)         scanf("%d", &A[i]);     for (i = 1; i < 5; i++) {         for (j = 1; j <= n; j++)             dp[i][j] = max_v(dp[i][j - 1] + (parts[i] == A[j]), dp[i - 1][j]);     }     printf("%d", dp[4][n]);     return 0; }

D. A Determined Cleanup

E. A Colourful Prospect