(200620) 코드포스 - Codeforces Round #651 (Div. 2)

Codeforces Round #651 (Div. 2) ㄱㄱ

참가 인원 현재 18000여명. 11시 35분에 시작합니다.

1370A

n보다 작은 서로 다른 두 값이 gcd max 값이 나오게 하는 문제인데요.
서로 다른 두 값이기 때문에 2로 나누는게 가장 작겠죠.
n 보다 가장 작은 짝수 / 2 가 답입니다.

6분만에 제출하고 넘어가서 시작이 좋았습니다.

#include <iostream>
#include <string>
 
using namespace std;
 
namespace {
constexpr char kTrueString[] = "Yes";
constexpr char kFalseString[] = "No";
}  // unnamed namespace;
 
constexpr inline auto GetAnswerString(bool is_true) {
  return is_true ? kTrueString : kFalseString;
}
 
int main(int argc, char** argv) {
  ios::sync_with_stdio(false); 
  cin.tie(NULL);
//  freopen("input.txt", "r", stdin);
  
  int test_case;
  cin >> test_case;
 
  while (test_case--) {
    int n;
 
    cin >> n;
 
    n -= (n & 0x01);
 
    cout << n / 2 << endl;
 
  }
  return 0;
}

1370B

처음 딱 보고 B번이 뭐 이렇게 어려워 하고 넘어갔네요.
GCD를 최대값이 되게 만들어야 하는 줄 알았는데 1보다 큰 GCD면 되는거였네요. :frowning:
Contest 끝나고 다른 사람 코드 보고 알있습니다.

그리고 index를 출력해야 하는데 number를 출력했네요.

C번 풀고 돌아와서 제한시간 안에 못 풀었네요.
문제를 잘 읽어야 ㅜㅜ

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

namespace {
constexpr int kMaxGCD = 2000;
constexpr int kMaxN = 2000;

constexpr char kTrueString[] = "Yes";
constexpr char kFalseString[] = "No";
}  // unnamed namespace;

constexpr inline auto GetAnswerString(bool is_true) {
  return is_true ? kTrueString : kFalseString;
}

int rest_count[kMaxGCD];
int rest_numbers[kMaxGCD][kMaxGCD];
int buffer[kMaxN];

int main(int argc, char** argv) {
  ios::sync_with_stdio(false); 
  cin.tie(NULL);
//  freopen("input.txt", "r", stdin);
  
  int test_case;
  cin >> test_case;

  while (test_case--) {
    int n;
    int sum = 0;
    int min1 = 1001, min2 = 1001;
    cin >> n;


    for (int i = 0; i < 2 * n; ++i) {
      cin >> buffer[i];
      sum += buffer[i];
      int &bigger_min = min1 > min2 ? min1 : min2;
      bigger_min = min(bigger_min,buffer[i]);
    }

    sum -= (min1 + min2);

    int average = sum / (n - 1);

    for (int i = average; i >= 2; --i) {
      for (int j = 0; j < i; ++j) {
        rest_count[j] = 0;
      }

      for (int j = 0; j < 2 * n; ++j) {
        int rest = buffer[j] % i;
        rest_numbers[rest][rest_count[rest]] = buffer[j];
        ++rest_count[rest];
      }

      int unmatched_count = rest_count[0] % 2;
      rest_count[0] -= rest_count[0] % 2;

      for (int j = 1; j < (i + 1) / 2; ++j) {
        unmatched_count += abs(rest_count[j] - rest_count[i- j]);
        if(rest_count[j] > rest_count[i- j]) rest_count[j] = rest_count[i- j];
        else rest_count[i- j] = rest_count[j];
      }

      if(!(i & 0x01)) {
        unmatched_count += rest_count[i / 2] % 2;
        rest_count[i / 2] -= rest_count[i / 2] % 2;
      }

      if(unmatched_count <= 2) {
        if(unmatched_count == 0) {
          if(rest_count[0] >= 2) {
            rest_count[0] -= 2;
          } else {
            if((!(i & 0x01)) && (rest_count[i / 2] >= 2)) {
              rest_count[i / 2] -= 2;
            } else {
              for (int j = 1; j < (i + 1) / 2; ++j) {
                if(rest_count[j] >= 1) {
                  --rest_count[j];
                  --rest_count[i - j];
                }
                break;
              }
            }
          }
        }

        for(int j = 0; j < rest_count[0]; j +=2) {
          cout << rest_numbers[0][j] << " " << rest_numbers[0][j+1] << endl;
        }

        for(int j = 1; j < (i + 1) / 2; ++j) {
          unmatched_count += abs(rest_count[j] - rest_count[i - j]);
          for (int k = 0; k < rest_count[j]; ++k) {
            cout << rest_numbers[j][k] << " " << rest_numbers[i - j][k] << endl;
          }
        }

        if(!(i & 0x01)) {
          for(int j = 0; j < rest_count[i / 2 + i % 2]; j +=2) {
            cout << rest_numbers[i / 2][j] << " " << rest_numbers[i / 2][j+1] << endl;
          }
        }

        break;
      }
    }
  }
  return 0;
}

1370C

B 건너뛰고 바로 C로 와서 풀기 시작했는데요.
판단식은 10분만에 세웠는데,
실수가 많아서 오래 걸리고 여러 번 제출하여 penalty point를 많이 먹었네요.

#include <iostream>
#include <string>
#include <tuple>
#include <vector>
 
using namespace std;
 
namespace {
constexpr int kPrimeMax = 31625;
 
constexpr char kTrueString[] = "Ashishgup";
constexpr char kFalseString[] = "FastestFinger";
}  // unnamed namespace;
 
constexpr inline auto GetAnswerString(bool is_true) {
  return is_true ? kTrueString : kFalseString;
}
 
bool prime[31623];
int odd_prime_max_index = 0;
int odd_prime[31623];
 
std::tuple<int, int> DivideEven(int even_n) {
  int two_count = 0;  
  while (!(even_n & 0x01)) {
    even_n /= 2;
    ++two_count;
  }
 
  return {even_n, two_count};
}
 
int OddDivisorCount(int odd_n) {
  int ret = 0;
  for(int i = 0; odd_prime[i] * odd_prime[i] <= odd_n;++i) {
    while(odd_n % odd_prime[i] == 0) {
      odd_n /= odd_prime[i];
      ++ret;
    }
  }
  if(odd_n != 1) ++ret;
 
  return ret;
}
 
int main(int argc, char** argv) {
  ios::sync_with_stdio(false); 
  cin.tie(NULL);
//  freopen("input.txt", "r", stdin);
 
  for (int i = 2; i < kPrimeMax; i++) {
    if (prime[i] == false) {
      for (int j = i*2; j < kPrimeMax; j += i) {
        prime[j] = true;
      }
    }
  }
 
  int max_index = 0;
  for (int i = 3; i < kPrimeMax; i++) {
    if(prime[i] == false) {
      odd_prime[max_index++] = i;
    }
  }
  odd_prime[max_index++] = 100000;
 
  odd_prime_max_index = max_index;
 
  int test_case;
  cin >> test_case;
 
  while (test_case--) {
    int n;
    cin >> n;
    
    if (n == 1) {
      cout << GetAnswerString(false) << endl;
    } else if (n == 2) {
      cout << GetAnswerString(true) << endl;
    } else if (n & 0x01) {
      cout << GetAnswerString(true) << endl;
    } else {
      int two_count;
      std::tie(n, two_count) = DivideEven(n);
 
      if(n == 1) {
        cout << GetAnswerString(false) << endl;
      } else {
        int odd_divisor_count = OddDivisorCount(n);
 
        if(odd_divisor_count > 1) {
          cout << GetAnswerString(true) << endl;
        } else {
          if(two_count == 1) {
            cout << GetAnswerString(false) << endl;
          } else {
            cout << GetAnswerString(true) << endl;
          }
        }
      }
    }
 
  }
  return 0;
}