(200712) 코드포스 - Educational Codeforces Round 91

Contest link: https://codeforces.com/contests/1380

이… 디비젼들은 뭔가여? 전에도 여러번 본거 같은데

div1 unrank ~ legendary grand master (누텔라)
div2 unrank ~ master candidate (바이올렛)
div3 unrank ~ specialist (시안)
해당 Contest가 측정 할 수 있는 rating 이 적용되는 구간이에요.
specialist 상위인 expert가 되면 더이상 div3에서 평가를 못 받는 거죠.

A번 풀었는데 서버가 터져서 ㄷㄷ 뭘 못하고 있네요.

ㅗㅜㅑ 마스터캔디뎃!

ㄷㄷ 서버 살아나서 봤더니 unrated round가 되버렸네요 ㅜ

D번 반례를 못찾겠네요 ㅋㅋ

unrated 되니까 사람들이 많이 안푸네요.


Common codes for codefoces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

using SolveFunc = std::function<void()>;

template<typename MultiRunner>
void Run(SolveFunc solve_func);

template<>
void Run<std::true_type>(SolveFunc solve_func) {
  int test_case;
  std::cin >> test_case;

  while (test_case--) {
    solve_func();
  }
}

template<>
void Run<std::false_type>(SolveFunc solve_func) {
  solve_func();
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  explicit Solver(solver::SolveFunc solve_func) {
    solver::Run<run_type>(solve_func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
    : true_value(_true_value),
      false_value(_false_value) {}

  const T true_value;
  const T false_value;

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };
};

}  // predefined;

#define LOG_INFO predefined::Log<predefined::LogType::INFO>()
#define LOG_DEBUG predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LOG(LEVEL) LOG_##LEVEL
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOG(DEBUG).Open(); \
Contest1380A
namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

INIT_STRING_ANSWER("YES", "NO");
}  // unnamed namespace;

void solve() {
  int n;
  cin >> n;

  vector<int> numbers(n);

  for (auto &input : numbers) cin >> input;

  int left_index = 0;
  bool left = false;
  for (int i = 0; i < n - 1; ++i) {
    if (numbers[i] < numbers[i + 1]) {
      left_index = i;
      left = true;
      break;
    }
  }

  int right_index = n - 1;
  bool right = false;
  for (int i = n - 1; i > 0; --i) {
    if (numbers[i] < numbers[i - 1]) {
      right_index = i;
      right = true;
      break;
    }
  }

  bool ans = (left & right) && (right_index > left_index);

    LOG_INFO << GET_ANSWER(ans);

  if (ans) {
    int mid_index = numbers[left_index + 1] > numbers[right_index - 1] ?
                    left_index + 1 :
                    right_index - 1;
    LOG_INFO << left_index + 1 << ' ' << mid_index + 1 << ' ' << right_index + 1;
  }
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver(std::bind(&solve));

  return 0;
}

Contest1380B

namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

enum RPS {
  ROCK = 0,
  PAPER = 1,
  SISSOR = 2,
  RPS_MAX = 3
};

void solve() {
  string input;
  cin >> input;

  int counts[RPS_MAX] = {0, 0, 0};
  for (const auto &c : input) {
    switch (c) {
      case 'R' : ++counts[ROCK]; break;
      case 'P' : ++counts[PAPER]; break;
      case 'S' : ++counts[SISSOR]; break;
      default : break;
    }
  }

  int max_value = max({counts[ROCK], counts[PAPER], counts[SISSOR]});

  if (max_value == counts[ROCK]) {
    for (int i = 0; i < input.size(); ++i) cout << 'P';
  } else if (max_value == counts[PAPER]) {
    for (int i = 0; i < input.size(); ++i) cout << 'S';
  } else {
    for (int i = 0; i < input.size(); ++i) cout << 'R';
  }
  cout << '\n';
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver(std::bind(&solve));

  return 0;
}

Contest1380C

namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

void solve() {
  int n, x;
  cin >> n >> x;

  vector<int> skills(n);

  for (auto &input : skills) cin >> input;

  sort (skills.begin(), skills.end(), greater<int>());

  int ans = 0;
  int count = 0;
  for (const auto &skill : skills) {
    ++count;
    if (count * skill >= x) {
      count = 0;
      ++ans;
    }
  }

  LOG_INFO << ans;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver(std::bind(&solve));

  return 0;
}

Contest1380D 오답
namespace {
using namespace std;

constexpr bool kMultiTestCase = false;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

void solve() {
  int n, m;
  int64_t x, k, y;
  cin >> n >> m >> x >> k >> y;

  vector<int64_t> a_array(n);
  vector<int64_t> b_array(m);

  for (auto &input : a_array) cin >> input;
  for (auto &input : b_array) cin >> input;
  
  vector<vector<int64_t>> subsequences;
  vector<pair<int64_t, int64_t>> start_end;

  int64_t ans = 0;
  int a_index = 0;
  int64_t start = -1;
  for (const auto &b : b_array) {
    if (a_index == a_array.size()) {
      ans = -1;
      break;
    }

    vector<int64_t> temp;
    while (a_index < a_array.size()) {
      if (a_array[a_index] == b) {
        if (temp.size() != 0) {
          subsequences.emplace_back(std::move(temp));
          start_end.emplace_back(start, b);
          start = b;
        }
        ++a_index;
        break;
      }
      temp.push_back(a_array[a_index]);
      ++a_index;
    }
  }

  if (ans == -1) {
    LOG_INFO << ans;
    return;
  }

  if (a_index < a_array.size()) {
    vector<int64_t> temp;
    while (a_index < a_array.size()) {
      temp.push_back(a_array[a_index]);
      ++a_index;
    }
    subsequences.emplace_back(std::move(temp));
    start_end.emplace_back(start, -1);
  }

  auto boundary_it = start_end.begin();
  for (const auto &subsequence : subsequences) {
    int64_t max_value = *max_element(subsequence.begin(), subsequence.end());
    bool boundary_berserker = (boundary_it->first > max_value) | (boundary_it->second > max_value);
    bool useless_fireball = x > k * y;

    if (boundary_berserker) {
      if (useless_fireball) {
        ans += y * subsequence.size();
      } else {
        ans += x * (subsequence.size() / k);
        ans += y * (subsequence.size() % k);
      }
    } else {
      if (subsequence.size() < k) {
        ans = -1;
        break;
      }

      if (useless_fireball) {
        ans += x * 1;
        ans += y * (subsequence.size() - k);
      } else {
        ans += x * (subsequence.size() / k);
        ans += y * (subsequence.size() % k);
      }
    }

    ++boundary_it;
  }

  LOG_INFO << ans;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver(std::bind(&solve));

  return 0;
}