백준 2016 국민대학교 교내 경시대회 풀이

https://www.acmicpc.net/category/detail/1541

2016 국민대학교 교내 경시대회

 

그렇다. 현재는 에디토리얼이 제공되고 있지 않으므로 후배로써 풀이를 복원하면 좋을 거 같아 글을 쓴다.

PA 13410 거꾸로 구구단

시키는 대로 구구단을 수행하면서 뒤집은 수의 최댓값을 구하면 된다. CPP에서는 std::to_string으로 구구단 결과를 문자열로 바꾼 후 std::reverse로 뒤집고 다시 std::stoi로 전환하는 방법이 있다. 파이썬에서는 역시 str()로 문자열로 바꾼 후 슬라이싱 문법으로 뒤집은 다음 int()로 전환할 수 있다. std 함수의 경우 상수 시간이 크지만 문제에선 제한이 작으므로 문제없이 돌아간다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int ans;
int n, k;
 
void solve()
{
  cin >> n >> k;
  for (int i = 1; i <= k; i++)
  {
    auto val = i * n;
    auto tmp = to_string(val);
    reverse(tmp.begin(), tmp.end());
    auto res = stoi(tmp);
    ans = max(ans, res);
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

PB 13411 하늘에서 정의가 빗발친다!

각 로봇의 인덱스와 유클리드 거리를 구한 후 $V_{i}$만큼 나눈 값을 페어로 저장해 오름차순으로 정렬하면 풀린다.

 

시간 복잡도: 제곱근을 구하므로 $O(N \sqrt{20000})$

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
using pdi = pair<double, int>;
int n;
vector<pdi> v;
 
void solve()
{
  cin >> n;
 
  for (int i = 0; i < n; i++)
  {
    int x, y, velo;
    cin >> x >> y >> velo;
 
    auto dist = [=]() {
      return hypot(0 - x, 0 - y) / velo;
    }();
    v.emplace_back(dist, i);
  }
 
  sort(v.begin(), v.end());
  for (auto &item : v)
  {
    cout << item.second + 1 << '\n';
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

PC 13412 서로소 쌍

주어지는 N마다 1부터 $\sqrt{N}$까지 반복문을 돌면서 $lcm(i, N) = N$인지 확인하면 된다. 왜냐하면 $\sqrt{N}$보다 큰 수와의 최소 공배수는 절대 N이 될 수 없기 때문. 이유가 궁금하면 gcd가 1일 때 어떤 일이 일어나는지 생각해보라.

 

시간 복잡도: T를 무시하고 $O(\sqrt{N})$

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
void solve()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n;
    cin >> n;
    int ans = 0;
 
    for (ll i = 1; i * i <= n; i++)
    {
      if (n % i) continue;
      auto dv = n / i;
      if (lcm(dv, i) == n) ++ans;
    }
    cout << ans << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

A 13413 오셀로 재배치

각 상태의 W의 개수와 B의 개수를 센다. 두 상태의 색깔 개수가 서로 일치하지 않으면 일치하지 않는 만큼의 오셀로를 뒤집어야 함을 의미한다.

 

정답을 ans로 두고 일치하지 않은 횟수를 저장하는 half, 그리고 뒤집어야 하는 개수를 diff에 저장한 뒤 오셀로에 대해 순회를 도는데 두 상태가 동일하지 않으면서 아직 뒤집어야 한다면(diff >= 1) diff -= 1, ans += 1을 해준다.

 

만약 diff가 0인데 상태가 일치하지 않으면 다 뒤집고 나서 몇 개가 일치하지 않는지 구해야 하므로 half += 1로 세준다.

 

그러면 half는 x쌍만큼의 값, 즉 짝수임이 자명하므로 두 위치를 바꿔주는 연산 횟수는 half / 2, 즉 ans + half / 2이 정답이 된다.

 

시간 복잡도: $O(|S|)$

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
 
using namespace std;
 
int t;
 
void solve()
{
  cin >> t;
 
  while (t--)
  {
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0;
 
    int ar1[2] {}, ar2[2] {};
    for (int i = 0; i < n; i++)
    {
      if (s1[i] == 'W') ++ar1[0];
      else ++ar1[1];
 
      if (s2[i] == 'W') ++ar2[0];
      else ++ar2[1];
    }
 
    int diff = abs(ar1[0] - ar2[0]);
    int half = 0;
    for (int i = 0; i < n; i++)
    {
      if (s1[i] != s2[i] && diff)
      {
        ++ans;
        s1[i] = s2[i];
        diff--;
      }
      else if (s1[i] != s2[i])
      {
        ++half;
      }
    }
    cout << ans + half / 2 << '\n';
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

B 13414 수강신청

먼저 주어지는 입력은 0부터 시작할 수 있음에 주의하라. 즉, 데이터를 수가 아닌 문자열로 다뤄야 한다. 그리고 각 수강신청 로그를 순회하면서 다음 과정을 따른다.

 

1. 최초로 나타났을 경우 집합 자료구조에 해당 학번을 넣어준다.

2. 최초가 아닐 경우 map, dictionary 자료구조로 해당 키의 카운트를 1 증가한다.

 

그리고 다시 로그를 순회하면서 다음 과정을 따른다.

 

1. 해당 학번의 카운트가 0보다 크면 1 감소시키고 아무것도 하지 않는다.

2. 카운트가 0이면 출력한다.

 

이 과정을 잘 구현하면 정답을 받을 수 있다.

 

시간 복잡도: 해시맵을 쓰면 $O(N)$

 

전체 코드 - CPP 커스텀 fastio 코드를 사용해서 가독성에 유의

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
inline namespace Input {
  const int BUF_SZ = 1 << 17;
  char buf[BUF_SZ];
  int pos;
  int len;
  char next_char() {
    if (pos == len) {
      pos = 0;
      len = (int)fread(buf, 1, BUF_SZ, stdin);
      if (!len) {
        return EOF;
      }
    }
    return buf[pos++];
  }
 
  long long read_int() {
    long long x;
    char ch;
    int sgn = 1;
    while (!isdigit(ch = next_char())) {
      if (ch == '-') {
        sgn *= -1;
      }
    }
    x = ch - '0';
    while (isdigit(ch = next_char())) {
      x = x * 10 + (ch - '0');
    }
    return x * sgn;
  }
 
  string read_string() {
    string ret;
    char ch;
    while (isspace(ch = next_char())) {}
    ret.push_back(ch);
    while (not isspace(ch = next_char()))
      ret.push_back(ch);
    return ret;
  }
} // namespace Input
 
inline namespace Output {
  const int BUF_SZ = 1 << 17;
  char buf[BUF_SZ];
  int pos;
 
  void flush_out() {
    fwrite(buf, 1, pos, stdout);
    pos = 0;
  }
 
  void write_char(char c) {
    if (pos == BUF_SZ) {
      flush_out();
    }
    buf[pos++] = c;
  }
 
  void write_int(long long x, char delim = '\n') {
    static char num_buf[100];
    if (x < 0) {
      write_char('-');
      x *= -1;
    }
    int len = 0;
    for (; x >= 10; x /= 10) {
      num_buf[len++] = (char)('0' + (x % 10));
    }
    write_char((char)('0' + x));
    while (len) {
      write_char(num_buf[--len]);
    }
    write_char(delim);
  }
 
  // auto-flush output when program exits
  void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output
 
unordered_set<string> in;
unordered_map<string, int> cnt;
vector<string> v;
int idx;
 
void solve()
{
  init_output();
  int k, l;
  k = read_int();
  l = read_int();
 
  for (int i = 0; i < l; i++)
  {
    string x;
    x = read_string();
    v.push_back(x);
    if (!in.count(x))
    {
      in.insert(x);
    }
    else
    {
      cnt[x]++;
    }
  }
 
  int joined = 0;
  idx = v.size();
  for (int i = 0; i < idx; i++)
  {
    if (cnt[v[i]] > 0)
    {
      --cnt[v[i]];
    }
    else
    {
      for (char c : v[i]) write_char(c);
      write_char('\n');
      ++joined;
    }
    if (joined == k) return;
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

C 13415 정렬 게임

주어진 연산을 우직하게 수행하면 시간 복잡도 $O(N^{2} \log N)$으로 높은 확률로 TLE를 받는다. 우선 다음을 관찰할 수 있다.

 

주어진 쿼리를 통틀어 정렬되지 않은 범위는 건드릴 필요가 없다.

 

일단 쿼리들을 입력받은 뒤 가장 큰 범위를 찾자. 그러면 정렬되지 않는 원소들은 그래도 나올 것이므로 정답 배열의 맨 뒤에 넣도록 한다. 그리고 다음을 관찰한다.

 

어차피 이전에 있던 작은 범위의 쿼리는 뒤에 나오는 큰 범위의 쿼리에 의해 의미 없는 행동이 된다.

 

따라서 의미 없는 쿼리를 지워주도록 하자. 지울 때는 덱을 쓰는데 각 쿼리를 덱에 집어넣는다. 이때 오름차순/내림차순의 구분을 위해 내림차순은 음수로 만든다. 덱에 넣기 전 자기보다 작은 범위의 쿼리들을 모조리 제거한 후 뒤에 삽입하면 된다.

 

그래도 주어지는 범위가 내림차순으로 주어지는 tc에 대해 제거되는 쿼리가 없으므로 바로 정렬을 할 수 없다. 다시 관찰을 한다.

 

정렬은 오름차순 -> 내림차순의 순서대로 진행한다. 이 둘 사이의 구간 차를 x라고 하자. 그러면 오름차순 순서일 때 정렬된 x개의 원소만 뽑아오는 것을 알 수 있다. 그러면 이 두 개의 차이를 구해서 x개의 원소를 정답 배열의 뒤에서부터 내림차순, 나머지 원소를 정답 배열의 오름차순으로 배치하면 된다.

 

그런데 이전에 우리는 필요 없는 쿼리를 제거했으므로 오름차순 -> 오름차순 같이 같은 종류가 있을 수 있다. 관찰을 정리하자.

 

현재 쿼리를 봤을 때 바로 뒤 쿼리와 구간 차 x를 구한다. 그러면 현재 쿼리가 오름차순이면 x개만큼 오름차순으로 배치, 내림차순이면 x개 만큼 내림차순으로 배치한다. 이를 반복하면 정확한 답을 구할 수 있다.

 

이 아이디어를 따르면 배열을 딱 한 번만 채우면 되기 때문에 시간 복잡도는 $O(N)$이 된다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int ar[100000];
int ans[100000];
int n, q;
deque<int> dq;
 
void solve()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i];
  }
  cin >> q;
  int mx = 0;
 
  for (int i = 0; i < q; i++)
  {
    int a, b;
    cin >> a >> b;
    mx = max(a, max(b, mx));
 
    while (dq.size() and abs(dq.back()) <= a) dq.pop_back();
    dq.push_back(a);
    while (dq.size() and abs(dq.back()) <= b) dq.pop_back();
    dq.push_back(-b);
  }
  dq.push_back(0);
 
  sort(ar, ar + mx);
  for (int i = mx; i < n; i++)
  {
    ans[i] = ar[i];
  }
 
  int cur = dq.front();
  dq.pop_front();
  int l = 0, r = mx - 1;
  int ptr = mx - 1;
 
  while (dq.size())
  {
    int nxt = dq.front();
    dq.pop_front();
 
    int diff;
    if (cur > 0)
    {
      diff = cur - abs(nxt);
      while (diff)
      {
        ans[ptr] = ar[r];
        --r;
        --ptr;
        --diff;
      }
    }
    else
    {
      diff = -cur - abs(nxt);
      while (diff)
      {
        ans[ptr] = ar[l];
        ++l;
        --ptr;
        --diff;
      }
    }
 
    cur = nxt;
  }
 
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

D 13416 주식 투자

이익표가 그대로 주어졌으므로 각 날마다 0을 초과하는 이익 중 최대 이익만 취하면 된다.

 

전체 코드 - CPP fastio 코드를 써서 가독성에 유의

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
 
inline namespace Input {
  const int BUF_SZ = 1 << 16;
  char buf[BUF_SZ];
  int pos;
  int len;
  char next_char() {
    if (pos == len) {
      pos = 0;
      len = (int)fread(buf, 1, BUF_SZ, stdin);
      if (!len) {
        return EOF;
      }
    }
    return buf[pos++];
  }
 
  long long read_int() {
    int x;
    char ch;
    int sgn = 1;
    while (!isdigit(ch = next_char())) {
      if (ch == '-') {
        sgn *= -1;
      }
    }
    x = ch - '0';
    while (isdigit(ch = next_char())) {
      x = x * 10 + (ch - '0');
    }
    return x * sgn;
  }
  
  string read_string() {
    string ret;
    char ch;
    while (isspace(ch = next_char())) {}
    ret.push_back(ch);
    while (not isspace(ch = next_char()))
      ret.push_back(ch);
    return ret;
  }
} // namespace Input
 
inline namespace Output {
  const int BUF_SZ = 1 << 16;
  char buf[BUF_SZ];
  int pos;
 
  void flush_out() {
    fwrite(buf, 1, pos, stdout);
    pos = 0;
  }
 
  void write_char(char c) {
    if (pos == BUF_SZ) {
      flush_out();
    }
    buf[pos++] = c;
  }
 
  void write_int(long long x, char delim = '\n') {
    static char num_buf[100];
    if (x < 0) {
      write_char('-');
      x *= -1;
    }
    int len = 0;
    for (; x >= 10; x /= 10) {
      num_buf[len++] = (char)('0' + (x % 10));
    }
    write_char((char)('0' + x));
    while (len) {
      write_char(num_buf[--len]);
    }
    write_char(delim);
  }
 
  // auto-flush output when program exits
  void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output
 
int t;
 
void solve()
{
    init_output();
    t = read_int();
    while (t--)
    {
        int n = read_int();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int a = read_int();
            int b = read_int();
            int c = read_int();
            ans += max(0, max(max(a, b), c));
        }
 
        write_int(ans);
    }
}
 
int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
 
    solve();
}

E 13417 카드 문자열

각 입력마다 앞으로 놓은 경우 vs 뒤로 놓은 경우를 비교해서 더 사전 순으로 작은 방향으로 문자열을 완성하면 된다. 더 효율적으로 하는 방법은 현재 문자열의 첫 번째 글자만 비교해도 충분하다.

 

시간 복잡도: 제공하는 구현은 $O(N^{2})$ 덱을 쓰면 $O(N)$도 가능하다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int t;
 
void solve()
{
  cin >> t;
  while (t--)
  {
    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; i++)
    {
      char c;
      cin >> c;
      if (s.empty())
      {
        s.push_back(c);
      }
      else
      {
        if (s[0] >= c)
        {
          s.insert(s.begin(), c);
        }
        else
        {
          s.push_back(c);
        }
      }
    }
    cout << s << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

F 13418 학교 탐방하기

문제를 잘 보면 최소/최대 스패닝 트리를 원하고 있음을 발견할 수 있다. 간선의 우선순위를 잘 계산하여 최소 스패닝 트리와 최대 스패닝 트리의 가중치 차를 구하면 된다. 스패닝 트리를 만드는 방법으로는 크루스칼 알고리즘이 대표적이다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, m;
using tp = tuple<int, int, int>;
priority_queue<tp, vector<tp>, greater<>> pq1;
priority_queue<tp> pq2;
 
struct ufind
{
  vector<int> parent, rank;
  ufind(int n) : parent(n), rank(n)
  {
    for (int i = 0; i < n; i++)
    {
      parent[i] = i;
    }
  }
 
  int find(int u)
  {
    if (u == parent[u]) return u;
    return parent[u] = find(parent[u]);
  }
 
  bool vnion(int u, int v)
  {
    u = find(u), v = find(v);
    if (u == v) return false;
    if (rank[u] > rank[v]) swap(u, v);
    parent[u] = v;
    if (rank[u] == rank[v]) ++rank[v];
    return 1;
  }
};
 
void solve()
{
  cin >> n >> m;
  for (int i = 0; i <= m; i++)
  {
    int go, to, fee;
    cin >> go >> to >> fee;
    if (go > to) swap(go, to);
    pq1.push({fee ^ 1, go, to});
    pq2.push({fee ^ 1, go, to});
  }
 
  ufind u1(n + 1), u2(n + 1);
 
  ll ans1 = 0, ans2 = 0;
  int cnt = 0;
  while (cnt < n)
  {
    auto [val, a, b] = pq1.top();
    pq1.pop();
    if (u1.vnion(a, b))
    {
      ans1 += val;
      ++cnt;
    }
  }
 
  cnt = 0;
  while (cnt < n)
  {
    auto [val, a, b] = pq2.top();
    pq2.pop();
    if (u2.vnion(a, b))
    {
      ans2 += val;
      ++cnt;
    }
  }
 
  cout << ans2 * ans2 - ans1 * ans1;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

G 13419 탕수육

주어진 대로 구현하면 될 거 같지만 한 바퀴를 돌고 난 다음이 문제이다. 이럴 땐 중복하는 테크닉으로 가볍게 해결할 수 있다. 우선 첫 번째 TC를 보자.

 

ABC

 

이를 한 번 중복하면 ABCABC가 된다. 그러면 다음과 같이 지지 않는 문자열을 취할 수 있다.

 

ABCABC

 

이런 방법으로 지지 않는 문자열을 구하면 된다.

 

다른 방법은 중복하지 않고 나머지 연산과 방문 배열을 보관하는 방법으로 진행할 수 있다. 어차피 중복 문자는 건드리지 않으므로 인덱스를 2씩 전진하면서 이미 방문한 인덱스를 만나기 전까지 문자를 기록해도 지지 않는 문자열을 만들 수 있다.

 

전체 코드 - CPP 방문 배열 방법 사용

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
bool visit1[33];
bool visit2[33];
 
void solve()
{
  int t;
  cin >> t;
  while (t--)
  {
    string s;
    cin >> s;
    memset(visit1, 0, sizeof visit1);
    memset(visit2, 0, sizeof visit2);
 
    if (s.size() == 1)
    {
      cout << s << '\n' << s << '\n';
      continue;
    }
 
    int idx = 0;
    string a, b;
    while (!visit1[idx])
    {
      a.push_back(s[idx]);
      visit1[idx] = true;
      idx += 2;
      idx %= s.size();
    }
    idx = 1;
    while (!visit2[idx])
    {
      b.push_back(s[idx]);
      visit2[idx] = true;
      idx += 2;
      idx %= s.size();
    }
    cout << a << '\n' << b << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

H 13420 사칙연산

그냥 주어진 입력을 받아 잘 비교하면 된다.

I 13421 국민 랜드

먼저 주의 사항을 짚고 넘어가자.

 

정답이 1인 경우가 있고 문제에는 답이 정수만 될 수 있다고 했지 맨해튼 좌표계라는 표현은 없었다. 우리는 문제를 유클리드 좌표계라 가정하고 풀어야 한다.

 

다 좋은데 맨하탄 좌표계에서는 정답이 1인 경우를 제대로 계산할 수 없다. 따라서 우리는 이 문제를 개선하기 위해 2배 축척을 시행할 것이다. 주어지는 모든 입력에 대해 두 배를 해주자. 그리고 우리는 다음을 삼분 탐색으로 구할 것이다.

 

한 변의 길이가 최소가 되도록 원점에서 한 방향으로 뻗는 선분의 길이

 

원점을 기준으로 정사각형의 크기를 늘리고 줄이면 각 원래 점과 다음 점 사이의 거리는 최솟값을 가지는 유니모달 함수로 표현이 됨을 발견할 수 있다. 따라서 우리는 삼분 탐색을 실시하여 원점에서 뻗어나가는 선분의 최솟값을 구하면 된다.

 

 

그런데 주어진 네 점이 어느 위치에 있고 어떤 점에 대응시켜야 할지 잘 모른다. 이는 점을 대응시키는 모든 경우의 수 4!을 전부 계산하면 된다. CPP에서는 편하게 std::next_permutation으로 모든 경우를 계산할 수 있다. 최솟값을 구하면 다시 축척을 줄일 필요 없다. 우리가 원하는 건 한 변의 길이인데 구한 것은 한 변의 길이의 반의 두배를 구한 것이므로 그대로 출력하면 된다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
using pll = pair<ll, ll>;
pll ar[4];
pll dest[4];
ll ans;
ll mv;
 
inline ll manhattan(pll &l, pll &r)
{
  return abs(l.first - r.first) + abs(l.second - r.second);
}
 
void fill_dest(ll val)
{
  dest[0] = {val, val};
  dest[1] = {-val, val};
  dest[2] = {val, -val};
  dest[3] = {-val, -val};
}
 
ll func(ll val)
{
  fill_dest(val);
  sort(dest, dest+4);
  ll ret = 1e18 * 8;
  do {
    ll tmp = 0;
    for (int i = 0; i < 4; i++) tmp += manhattan(ar[i], dest[i]);
    ret = min(ret, tmp);
  } while (next_permutation(dest, dest + 4));
 
  return ret;
}
 
void solve()
{
  mv = 1e18 * 8;
  for (int i = 0; i < 4; i++)
  {
    cin >> ar[i].first >> ar[i].second;
    ar[i].first <<= 1;
    ar[i].second <<= 1;
  }
  sort(ar, ar + 4);
 
  ll l = 1, r = 1e18;
  while (l <= r)
  {
    auto diff = (r - l) / 3;
    auto p1 = l + diff;
    auto p2 = r - diff;
 
    auto val1 = func(p1);
    auto val2 = func(p2);
 
    if (val1 < val2)
    {
      if (mv > val1)
      {
        mv = val1;
        ans = p1;
      }
      else if (mv == val1)
      {
        ans = max(ans, p1);
      }
      r = p2 - 1;
    }
    else
    {
      if (mv > val2)
      {
        mv = val2;
        ans = p2;
      }
      else if (mv == val2)
      {
        ans = max(ans, p2);
      }
      l = p1 + 1;
    }
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

J 13422 도둑

어차피 연속된 집을 가져가는 경우를 구하는 것이므로 어렵게 생각할 거 없이 길이 m만큼 합을 기록하면서 k를 벗어나지 않는 횟수를 구하면 된다. 이는 덱을 활용한 슬라이딩 윈도우로 간단하게 구현할 수 있다. 다만 집의 배치가 원형이고 뒤에서부터 한 바퀴 돌아 터는 경우가 최대인 경우가 있다. 이를 처리하기 위해 G - 탕수육에서 언급했던 중복 시키는 테크닉을 사용하면 한바퀴 도는 경우를 쉽게 처리할 수 있다. 다만 다음 예외가 생긴다.

 

n과 m이 같은 경우

 

그러면 다음 케이스에서 잘못된 답이 나온다.

1
2 2 10
4 5

 

왜냐면 4 5 말고 한바퀴 돌아 5 4도 정답인 걸로 인식되기 때문이다. 이 경우를 피하기 위해 n == m인 경우 수열을 중복시키지 않도록 하면 된다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, m, k;
int ar[200000];
ll ans = 0;
 
void solve()
{
  int t;
  cin >> t;
  while (t--)
  {
    ans = 0;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
      cin >> ar[i];
      if (i < m)
      {
        ar[i+n] = ar[i];
      }
    }
 
    deque<int> dq;
    ll sum = 0;
    int minus = m - 1;
    if (n == m) minus = 0;
    for (int i = 0; i < n + minus; i++)
    {
      dq.push_back(ar[i]);
      sum += ar[i];
 
      if (dq.size() > m)
      {
        sum -= dq.front();
        dq.pop_front();
      }
 
      if (dq.size() == m)
      {
        if (sum >= k) continue;
        ++ans;
      }
    }
    cout << ans << "\n";
  }
 
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

K 13423 Three Dots

어떤 점을 ar[i], 왼쪽에 있는 점을 l, 오른쪽에 있는 점을 r이라 하자. 우리는 여기서 ar[i] - l == r - ar[i]가 같은 경우를 세줄 것이다.

 

l의 초기값을 ar[i - 1], r의 초기값을 ar[i + 1]이라 하자. 그리고 다음을 따라 전체 구간을 탐색한다.

 

ar[i] - l == r - ar[i]이면 카운트를 하나 센다. 그리고 l또는 r을 한 칸 움직인다.

ar[i] - l > r - ar[i]이면 r을 한 칸 움직인다.

ar[i] - l < r - ar[i]이면 l을 한 칸 움직인다.

 

이는 투 포인터라는 기법이며 조건에 반응하여 구간을 움직일 때 효과적으로 쓸 수 있는 알고리즘이다.

 

이렇게 하면 어떤 점을 중심점이라 했을 때 거리가 같은 경우를 구할 수 있다. 이를 확장하여 모든 인덱스에 대해 계산하면 모든 경우의 수를 구할 수 있다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int t;
int ar[1000];
int n;
 
void solve()
{
  cin >> t;
  while (t--)
  {
    cin >> n;
    for (int i = 0; i < n; i++)
    {
      cin >> ar[i];
    }
    sort(ar, ar + n);
 
    int cnt = 0;
    for (int i = 1; i < n - 1; i++)
    {
      int l = i - 1;
      int r = i + 1;
      while (l >= 0 and r < n)
      {
        int dl = ar[i] - ar[l];
        int dr = ar[r] - ar[i];
        if (dl > dr)
        {
          ++r;
        }
        else
        {
          if (dl == dr) ++cnt;
          --l;
        }
      }
    }
 
    cout << cnt << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

L 13424 비밀 모임

N의 제한이 작으므로 플로이드 워셜 알고리즘을 쓸 수 있다. 플로이드 워셜 알고리즘으로 모든 쌍의 최소 경로를 구한 후 최소가 되는 거리 합과 그중에서도 가장 작은 방의 번호를 계산하면 된다.

 

전체 코드 - CPP

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int t;
int n, m;
int dp[101][101];
int ar[100];
 
void solve()
{
  cin >> t;
 
  while (t--)
  {
    fill(&dp[0][0], &dp[0][0] + 101 * 101, 1e9);
    for (int i = 1; i <= 100; i++) dp[i][i] = 0;
 
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
      int go, to, fee;
      cin >> go >> to >> fee;
 
      dp[go][to] = min(dp[go][to], fee);
      dp[to][go] = min(dp[to][go], fee);
    }
 
    for (int c = 1; c <= n; c++)
    {
      for (int i = 1; i <= n; i++)
      {
        for (int j = 1; j <= n; j++)
        {
          dp[i][j] = min(dp[i][j], dp[i][c] + dp[c][j]);
        }
      }
    }
 
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
      cin >> ar[i];
    }
 
    int val = 1e9;
    int ans = 9999;
 
    for (int i = 1; i <= n; i++)
    {
      int tmp = 0;
      for (int j = 0; j < q; j++)
      {
        tmp += dp[i][ar[j]];
      }
 
      if (tmp < val or (tmp == val and ans > i))
      {
        ans = i;
        val = tmp;
      }
    }
 
    cout << ans << '\n';
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}