(200708) 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1367F1 - Codeforces


Example

Input

4
5
4 7 2 3 9
5
3 5 8 1 7
5
1 4 5 7 12
4
0 2 1 3

Output

2
2
0
2


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

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

반가운 마음에 먼 길 돌아 왔군요 ㅋㅋ

1367F1

LIS을 이용하는 문제인줄 알고 다시 공부해서 풀었는데,
LIS가 필요 없는 문제였네요. ㅜㅜ

namespace {
using namespace std;

constexpr int kMaxNumber = 3000;
}  // unnamed namespace;

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

  int test_case;
  cin >> test_case;

  vector<int> numbers(kMaxNumber);
  vector<pair<int,int>> indexes(kMaxNumber);

  const auto compare = [&](const pair<int,int> &lhs, const pair<int,int> &rhs)->bool {
    return lhs.first < rhs.first;
  };

  while (test_case--) {
    int n;
    cin >> n;
    for (int i = 0 ; i < n ; ++i) {
      cin >> numbers[i];
      indexes[i].first = numbers[i];
      indexes[i].second = i;
    }
    
    sort(indexes.begin(), indexes.begin() + n, compare);
    
    int ans = kMaxNumber;
    for (int order_num = 0; order_num < n; ++order_num) {
      const int &number = indexes[order_num].first;
      const int &index = indexes[order_num].second;

      int count = 0;

      int now = order_num - 1;
      for (int i = index - 1; i >= 0; --i) {
        if (now == -1) continue;
        if (numbers[i] == indexes[now].first) {
          --now;
          ++count;
        }
      }
      
      now = order_num + 1;
      for (int i = index + 1; i < n; ++i) {
        if (now == n) continue;
        if (numbers[i] == indexes[now].first) {
          ++now;
          ++count;
        }
      }

      ans = min(ans, n - 1 - count);
    }

    LOG_INFO << ans;
  }

  return 0;
}
1 Like