(200806) 코드포스

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

Original problem link: https://codeforces.com/problemset/problem/1360/F
Difficulty:1700


Example

Input

5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c

Output

abab
-1
aaa
ab
z


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

새로운 문제로써 제로베이스에서 풀기보다,
데이터가 쌓이니까 거기서부터 나오는 잘 못 된 직관을 끌어다 쓰는거 같네요.

1360F 오답
namespace {
using namespace std;

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

}  // unnamed namespace;

void solve(int n, int m) {
  vector<string> inputs(n);
  for (auto &input : inputs) cin >> input;

  bool is_one_changed_ans = true;
  bool is_one_changed = false;
  int one_changed_index;
  for(int i = 0; i < m; ++i) {
    int count = 0;
    for (int j = 1; j < n; ++j) {
      if (inputs[0][i] != inputs[j][i]) ++count;
    }

    if (count != 0) {
      if (is_one_changed) is_one_changed_ans = false;
      is_one_changed = true;
      one_changed_index = i;
    }
  }

  string ans;
  if (is_one_changed_ans) {
    ans = inputs[0];
    LOG_INFO << ans ;
    return;
  }

  vector<bool> used(n, false);
  bool is_multi_changed_ans = true;
  for(int i = 0; i < m && is_multi_changed_ans; ++i) {
    int count = 0;
    int changed_index;
    for (int j = 1; j < n; ++j) {
      if (inputs[0][i] != inputs[j][i]) {
        ++count;
        changed_index = j;
      }
    }

    if (count == n - 1 && used[0] == false) {
      used[0] = true;
      ans.push_back(inputs[1][i]);
    } else if(count == n - 1 && used[0] == true) {
      char j1 = inputs[1][i];
      for (int j = 1; j < n; ++j) {
        if (j1 == inputs[j][i] && used[j] == false) {
          used[j] = true;
        } else {
          is_multi_changed_ans = false;
          break;
        }
      }
      ans.push_back(inputs[0][i]);
    } else if (count == 1 && used[changed_index] == false) {
      used[changed_index] = true;
      ans.push_back(inputs[0][i]);
    } else if (count == 0) {
      ans.push_back(inputs[0][i]);
    } else {
      char unused_char = '?';
      for (int j = 0; j < n; ++j) {
        if (used[j] && (unused_char == '?' || unused_char == inputs[j][i])) {
          unused_char = inputs[j][i];
        } else if (used[j] == false) {
          used[j] = true;
        } else {
          is_multi_changed_ans = false;
          break;
        }
      }
      ans.push_back(unused_char);
    }
  }

  if (is_multi_changed_ans) {
    LOG_INFO << ans;
  } else {
    LOG_INFO << -1;
  }
}

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

  Solver::Run(&solve);

  return 0;
}

참고 코드: https://codeforces.com/contest/1360/submission/81218602

1360F 정답

정답이 될 수 있는 모든 것을 다 해본다는 해결책이네요.

namespace {
using namespace std;

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

}  // unnamed namespace;

void solve(int n, int m) {
  vector<string> inputs(n);
  for (auto &input : inputs) cin >> input;

  string ans;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      string candidate = inputs[0];
      candidate[j] = inputs[i][j];

      bool valid_candidate = true;
      for (int i2 = 1; i2 < n && valid_candidate; ++i2) {
        int count = 0;
        for (int j2 = 0; j2 < m && valid_candidate; ++j2) {
          if (candidate[j2] != inputs[i2][j2]) {
            if (++count > 1) valid_candidate = false;
          }
        }
      }
      if (valid_candidate) ans = candidate;
    }
  }

  if (ans.empty()) LOG_INFO << -1;
  else LOG_INFO << ans;
}

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

  Solver::Run(&solve);

  return 0;
}