(201228) 간만에 코포 콘테스트 참가하였습니다.

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 을 출처로 명시합니다.

Problem - A - Codeforces
Problem - B - Codeforces
Problem - C - Codeforces


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <numeric>
#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 {

template <class Arg>
void GetArg(Arg& value) {
  std::cin >> value;
}

template <size_t index, class... Args>
typename std::enable_if<index == sizeof...(Args)>::type
GetArgsImpl(std::tuple<Args...>& args) {}

template <size_t index, class... Args>
typename std::enable_if<(index < sizeof...(Args))>::type
GetArgsImpl(std::tuple<Args...>& args) {
  GetArg(std::get<index>(args));
  GetArgsImpl<index + 1>(args);
}

template<typename ... Args>
std::tuple<Args...> GetArgs() {
  std::tuple<Args...> args;

  GetArgsImpl<0>(args);

  return args;
}

template<int...> struct IndexTuple {};

template<int I, typename T, typename... Types> 
struct MakeIndexesImpl; 

template<int I, int... Indexes, typename T, typename ... Types> 
struct MakeIndexesImpl<I, IndexTuple<Indexes...>, T, Types...> 
{ 
  typedef typename MakeIndexesImpl<I + 1, IndexTuple<Indexes..., I>, Types...>::type type; 
};

template<int I, int... Indexes> 
struct MakeIndexesImpl<I, IndexTuple<Indexes...> > 
{ 
  typedef IndexTuple<Indexes...> type; 
};

template<typename ... Types> 
struct MakeIndexes : MakeIndexesImpl<0, IndexTuple<>, Types...> 
{};

template<class... Args, int... Indexes > 
void RunImpl(void (*func)(Args...), std::tuple<Args...>&& args, IndexTuple< Indexes... >) 
{ 
  func(std::forward<Args>( std::get<Indexes>(args))... ); 
} 

template<class ... Args> 
void RunImpl(void (*func)(Args...), const std::tuple<Args...>& args) {
  RunImpl(func, std::tuple<Args...>(args), typename MakeIndexes<Args...>::type());
}

template<typename ... Args>
void Run(void (*func)(Args...)) {
  std::tuple<Args...> args = GetArgs<Args...>();

  RunImpl(func, args);;
}

template <typename T>
std::size_t GetTestCaseCount();

template <>
std::size_t GetTestCaseCount<std::true_type>() {
  std::size_t test_case_count;
  std::cin >> test_case_count;
  return test_case_count;
}

template <>
std::size_t GetTestCaseCount<std::false_type>() {
  return 1;
}

} // 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;

  template <typename ... Args>
  static void Run(void (*func)(Args...)) {
    auto tc_count = solver::GetTestCaseCount<run_type>();
    while (tc_count--) solver::Run(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 inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };

  const T true_value;
  const T false_value;
};

}  // predefined;

#define LOGI predefined::Log<predefined::LogType::INFO>()
#define LOGD predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#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); \
  LOGD.Open();
A번
namespace {
using namespace std;

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

}  // unnamed namespace;

void solve(std::string s) {
  if (s.size() & 0x01) {
    cout << "NO\n";
    return;
  }

  int cnt = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == ')') {
      --cnt;
    } else {
      ++cnt;
    }

    if (cnt < 0) {
      cout << "NO\n";
      return;
    }
  }

  cnt = 0;
  for (int i = s.size() - 1; i >= 0; --i) {
    if (s[i] == '(') {
      --cnt;
    } else {
      ++cnt;
    }

    if (cnt < 0) {
      cout << "NO\n";
      return;
    }
  }

  cout << "YES\n";
}

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

  Solver::Run(&solve);

  return 0;
}
B번

namespace {
using namespace std;

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

constexpr int kMInf = -100000000;

}  // unnamed namespace;

vector<int> reds, blues;

int buf[101][101];

int dp(int red, int blue) {
  int &ret = buf[red][blue];

  if (ret != kMInf) {
    return ret;
  }

  if (red == reds.size() && blue == blues.size()) {
    return 0;
  }

  if (red != reds.size()) {
    ret = max(ret, reds[red]);
    ret = max(ret, reds[red] + dp(red + 1, blue));
  }

  if (blue != blues.size()) {
    ret = max(ret, blues[blue]);
    ret = max(ret, blues[blue] + dp(red, blue + 1));
  }

  return ret;
}

void solve() {
  int r,b;
  
  cin >> r;
  reds.resize(r);
  for (int i = 0; i < r; ++i) {
    cin >> reds[i];
  }

  cin >> b;
  blues.resize(b);
  for (int i = 0; i < b; ++i) {
    cin >> blues[i];
  }

  for (int i = 0; i <= r; ++i) {
    for (int j = 0; j <= b; ++j) {
      buf[i][j] = kMInf;
    }
  }

  int ans = dp(0, 0);
  ans = max(ans, 0);

  cout << ans << endl;
}

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

  Solver::Run(&solve);

  return 0;
}
C번(정답X)
namespace {
using namespace std;

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

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

struct Section {
  Section() {}
  Section(const Section &rhs) : id(rhs.id), ground(rhs.ground), sup(rhs.sup) {}
  int id;
  int ground;
  int sup;
};

bool operator<(const Section &lhs, const Section &rhs) {
  return (lhs.ground + lhs.sup) < (rhs.ground + rhs.sup);
}

void solve(int n, int k) {
  bool ans = true;

  priority_queue<Section> pq;
  vector<Section> sections(n);
  vector<bool> checked(n, false);

  for (int i = 0; i < n; ++i) {
    cin >> sections[i].ground;
    sections[i].id = i;
    sections[i].sup = 0;

    pq.push(sections[i]);
  }

  checked[0] = true;
  checked[n - 1] = true;

  while (!pq.empty()) {
    Section now = pq.top();
    pq.pop();

    if (checked[now.id] == true) continue;

    Section &left = sections[now.id - 1];
    if (left.id == 0 ) {
      if (now.ground + now.sup >= k + left.ground) {
        cout << GET_ANSWER(false) << endl;
        return;
      }
    } else {
      if (now.ground + now.sup >= k + left.ground + k - 1) {
        cout << GET_ANSWER(false) << endl;
        return;
      } else if (left.sup == 0) {
        int sup = k + 1 - (now.ground + now.sup - left.ground); 
        left.sup = (sup >= 0) ? sup : 0;
      }
    }

    Section &right = sections[now.id + 1];
    if (right.id == n - 1 ) {
      cout << "right.id:" << right.id << endl;
      cout << "k + right.ground:" << k + right.ground << endl;
      if (now.ground + now.sup >= k + right.ground) {
        cout << GET_ANSWER(false) << endl;
        return;
      }
    } else {
      if (now.ground + now.sup >= k + right.ground + k - 1) {
        cout << GET_ANSWER(false) << endl;
        return;
      } else if (right.sup == 0) {
        int sup = k + 1 - (now.ground + now.sup - right.ground); 
        right.sup = (sup >= 0) ? sup : 0;
      }
    }

    checked[now.id] = true;
  }

  cout << GET_ANSWER(true) << endl;
}

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

  Solver::Run(&solve);

  return 0;
}

반갑습니다.
간만에 풀었더니 C번이 안풀리는군요. :frowning:

코톡에서 안보이는 동안 재테크에 빠져 살았습니다 ㅎㅎ
부동산 코스닥 코스피 나스닥 금 비트코인까지 건들여 봤네요.

재테크는 이제 어느정도 감이 잡혀서 최근에 우선순위를 재점검 해보았는데요.
다시 알고리즘입니다.

더 나이먹기 전에 고농도로 알고리즘 실력을 축적하는 시간 가져서,
나중에 이 때 쌓아놨던 실력을 파먹고 살아가야 겠습니다.

아~다행입니다. 전 또 갑자기 안보이셔서, 무슨일이라도 생길건지 걱정했네요.

저는 노후자금을 주식으로 준비하고 있읍니다.

1 Like

ㅜㅜ 걱정하셨다니 감동입니다.
새로운 세계 탐험하다 왔습니다.
나스닥 만세입니다. ㅎㅎ

1 Like