(200718) 코드포스 - Codeforces Round #656 (Div. 3)

Contest link: Dashboard - Codeforces Round #656 (Div. 3) - Codeforces

Codeforces Round #656 (Div. 3)

어제 있었던 Contest 이죠.
가상 참가 합니다! ㅎㅎ


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <queue>
#include <string>
#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; }
};

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(); \

그럼 가상응원 해 드림니다

@sh ㅋㅋㅋ 캄사합니다.

ABCD 풀었네요.
세그먼트 트리 구현에 재밌어서 시간 녹였습니다. ㅋㅋ
로컬 변수만 쓰려고 어거지로 recursive lambda도 만들어 보았습니다.

1385A

namespace {
using namespace std;

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

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

void solve() {
  int x, y, z;

  cin >> x >> y >> z;

  if (x == y && x == z) {
    LOG_INFO << GET_ANSWER(true);
    LOG_INFO << x << ' ' << x << ' ' << x;
  } else if (x == y && x > z) {
    LOG_INFO << GET_ANSWER(true);
    LOG_INFO << x << ' ' << z << ' ' << z;
  } else if (y == z && y > x) {
    LOG_INFO << GET_ANSWER(true);
    LOG_INFO << x << ' ' << x << ' ' << z;
  } else if (x == z && x > y) {
    LOG_INFO << GET_ANSWER(true);
    LOG_INFO << y << ' ' << x << ' ' << y;
  } else {
    LOG_INFO << GET_ANSWER(false);
  }

  bool ans;
}

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

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

  return 0;
}
1385B

namespace {
using namespace std;

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

}  // unnamed namespace;

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

  vector<bool> flag(n + 1, false);

  n *= 2;
  while (n--) {
    int dummy;
    cin >> dummy;
    if (flag[dummy] == false) {
      cout << dummy << ' ';
      flag[dummy] = true;
    }
  }
  cout << '\n';
}

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

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

  return 0;
}
1385C
namespace {
using namespace std;

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

}  // unnamed namespace;

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

  int ans = 0;
  int before;
  int first_unchanged_index = 0;
  cin >> before;
  bool is_increase = true;
  for (int i = 1; i < n; ++i) {
    int now;
    cin >> now;
    
    if (now > before) {
      if (is_increase == false) {
        if (first_unchanged_index != -1) ans = first_unchanged_index - 1;
        else ans = i - 1;
      }  
      first_unchanged_index = -1;
      is_increase = true;
    } else if (now < before) {
      first_unchanged_index = -1;
      is_increase = false;
    } else {
      if (first_unchanged_index == -1) {
        first_unchanged_index = i;
      }
    }
    before = now; 
  }
  LOG_INFO <<ans;
}

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

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

  return 0;
}

1385D

DP 길이 보였으나… ㅎㅎ 재밌네요.
real contest였으면 DP 했을듯요.

namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;
}  // unnamed namespace;

void solve() {
  vector<vector<vector<int>>> segment;
  vector<int> twos;

  int n;
  cin >> n;

  int two = n / 2;
  int count = 2;
  while (count <= n) {
    segment.emplace_back(vector<vector<int>>(count, vector<int>(26, 0)));
    twos.emplace_back(two);
    count *= 2;
    two /= 2;
  }

  string input;
  cin >> input;

  if (input.size() == 1) {
    LOG_INFO << (input[0] != 'a');
    return;
  }

  for (int i = 0; i < input.size(); ++i) {
    char c = input[i];
    for (int j = segment.size() - 1, now = i; j >= 0; --j, now /= 2) {
      ++segment[j][now][c - 'a'];
    }
  }

  auto get_answer = make_shared<unique_ptr<function<int(int, int, int)>>>();
  *get_answer = make_unique<function<int(int, int, int)>>(
    [&](int segment_index, int now, int count)->int{
      LOG_DEBUG << LABEL(segment_index) << LABEL(now) << LABEL(count);

      int ret = twos[segment_index] - segment[segment_index][now][count];
      LOG_DEBUG << LABEL(twos[segment_index]) << LABEL(segment[segment_index][now][count]) << LABEL(ret);

      int next = (now & 0x01) ? now - 1 : now + 1;
      if (segment_index + 1 < segment.size()) {
        ret += min((**get_answer)(segment_index + 1, next * 2, count + 1), (**get_answer)(segment_index + 1, next * 2 + 1, count + 1));
      } else if (segment_index + 1 == segment.size()) {
        ret += twos[segment_index] - segment[segment_index][next][count + 1];
      }
     return ret;
    }
  );

  LOG_INFO << min((**get_answer)(0, 0, 0), (**get_answer)(0, 1, 0));
}

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

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

  return 0;
}
2 Likes