행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자.

i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정한다.

문제의 특성상 만약 윗 행의 전구가 켜져 있다면 누르지 않고서는 얘를 꺼줄 방법이 없기 때문이다.

따라서, 첫 행만 전 탐색해주고 나머지 행은 그리디로 진행해주면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Bulbs
{
private:
  size_t num_of_on_bulbs_;
  vector<string> bulbs_;

public:
  Bulbs(const vector<string>& bulbs) : num_of_on_bulbs_(0), bulbs_(bulbs)
  {
    for (int r = 0; r < 10; ++r)
    {
      for (int c = 0; c < 10; ++c)
      {
        if (bulbs[r][c] == 'O')
        {
          ++num_of_on_bulbs_;
        }
      }
    }
  }

  vector<string>& bulbs()
  {
    return bulbs_;
  }

  size_t num_of_on_bulbs() const
  {
    return num_of_on_bulbs_;
  }

  void Push(const int r, const int c)
  {
    const int dr[5] = { 0, -1, 0, 1, 0 };
    const int dc[5] = { 0, 0, 1, 0, -1 };

    for (int d = 0; d < 5; ++d)
    {
      int nr = r + dr[d];
      int nc = c + dc[d];

      if (0 <= nr && nr < 10 && 0 <= nc && nc < 10)
      {
        switch (bulbs_[nr][nc])
        {
          case 'O':
            bulbs_[nr][nc] = '#';
            --num_of_on_bulbs_;
            break;
          case '#':
            bulbs_[nr][nc] = 'O';
            ++num_of_on_bulbs_;
            break;
        }
      }
    }
  }
};

vector<string> BULBS(10, "");

int Solve()
{
  int answer = 10 * 10 + 1;

  for (int first_row_mask = 0; first_row_mask < (1 << 10); ++first_row_mask)
  {
    Bulbs bulbs(BULBS);

    int num_of_pushes = 0;

    // Process first row
    for (int col = 0; col < 10; ++col)
    {
      if (first_row_mask & (1 << col))
      {
        bulbs.Push(0, col);
        ++num_of_pushes;
      }
    }

    // Process remaining rows
    for (int row = 1; row < 10; ++row)
    {
      for (int col = 0; col < 10; ++col)
      {
        if (bulbs.bulbs()[row - 1][col] == 'O')
        {
          bulbs.Push(row, col);
          ++num_of_pushes;
        }
      }
    }

    if (bulbs.num_of_on_bulbs() == 0)
    {
      answer = min(answer, num_of_pushes);
    }
  }

  return answer > 100 ? -1 : answer;
}

int main(void)
{
  // Read input
  for (int row = 0; row < 10; ++row)
  {
    cin >> BULBS[row];
  }

  // Sovle
  cout << Solve() << endl;

  return 0;
}

별로 특별할 것 없이 lower_bound를 사용해서 풀어주면 LIS의 길이까지는 무리 없이 구해줄 수 있다.

여기서 실제 LIS를 재구성해내는데 조금 어려움을 겪었는데, 결과적으로는 아래의 방법을 사용하였다.

LIS를 풀면서 아래의 정보를 유지해준다.

• P[i]: A[i]가 LIS의 몇 번째 수로서 포함될 수 있었는가?

LIS의 길이를 구한 뒤에 P[i]를 뒤에서부터 보면서 답을 재구성해주면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 1000000;

int N;
int A[kMaxN];
int P[kMaxN];

vector<int> CACHE;
vector<int> LIS;

int main(void)
{
  // Read input
  scanf(" %d", &N);
  for (int i = 0; i < N; ++i)
  {
    scanf(" %d", &A[i]);
  }

  // Get length
  for (int i = 0; i < N; ++i)
  {
    auto it = lower_bound(CACHE.begin(), CACHE.end(), A[i]);
    if (it == CACHE.end())
    {
      CACHE.emplace_back(A[i]);
      P[i] = (int)CACHE.size() - 1;
    }
    else
    {
      *it = A[i];
      P[i] = (int)(it - CACHE.begin());
    }
  }

  // Print answer
  printf("%d\n", (int)CACHE.size());

  int target = (int)CACHE.size() - 1;
  for (int i = N - 1; i >= 0 && target >= 0; --i)
  {
    if (P[i] == target)
    {
      LIS.emplace_back(A[i]);
      --target;
    }
  }

  for (auto r = LIS.rbegin(); r != LIS.rend(); ++r)
  {
    printf("%d ", *r);
  }
  printf("\n");

  return 0;
}

포인트 냠냠을 위한 BFS 문제이다.

숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N;
int V[1000000 + 1];
int P[1000000 + 1];

void Bfs(const int start)
{
  V[start] = 1;
  P[start] = -1;

  queue<int> q;
  q.emplace(start);

  while (!q.empty())
  {
    int here = q.front();
    q.pop();

    if (here == 1)
    {
      break;
    }

    if (here % 3 == 0 && !V[here / 3])
    {
      V[here / 3] = 1;
      P[here / 3] = here;
      q.emplace(here / 3);
    }

    if (here % 2 == 0 && !V[here / 2])
    {
      V[here / 2] = 1;
      P[here / 2] = here;
      q.emplace(here / 2);
    }

    if (here - 1 > 0 && !V[here - 1])
    {
      V[here - 1] = 1;
      P[here - 1] = here;
      q.emplace(here - 1);
    }
  }
}

vector<int> path;

int main(void)
{
  scanf(" %d", &N);
  Bfs(N);

  int n = 1;
  while (P[n] != -1)
  {
    path.emplace_back(n);
    n = P[n];
  }

  printf("%d\n%d ", (int)path.size(), N);
  for (auto r = path.rbegin(); r != path.rend(); ++r)
  {
    printf("%d ", *r);
  }
  printf("\n");

  return 0;
}

Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자.

이때, M[i][j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자.

이렇게하면, M^k[i][j]은 자연스럽게, k분 만에 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다.

거듭제곱할 행렬의 크기가 꽤 크니까, 여기서는 분할 정복 방법을 이용해주자.

#include <cstdio>
#include <cstdint>

const int64_t kMod = 1000000007;

int64_t D;
int64_t M[8][8] = { { 0, 1, 1, 0, 0, 0, 0, 0 }, { 1, 0, 1, 1, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1, 0, 0, 0 },
                    { 0, 1, 1, 0, 1, 1, 0, 0 }, { 0, 0, 1, 1, 0, 1, 1, 0 }, { 0, 0, 0, 1, 1, 0, 0, 1 },
                    { 0, 0, 0, 0, 1, 0, 0, 1 }, { 0, 0, 0, 0, 0, 1, 1, 0 } };

void Power(int64_t m[][8], const int64_t k)
{
  if (k == 1)
  {
    for (int64_t i = 0; i < 8; ++i)
    {
      for (int64_t j = 0; j < 8; ++j)
      {
        m[i][j] = M[i][j];
      }
    }

    return;
  }

  int64_t half[8][8];
  int64_t full[8][8];
  Power(half, k / 2);

  for (int64_t r = 0; r < 8; ++r)
  {
    for (int64_t c = 0; c < 8; ++c)
    {
      full[r][c] = 0;
      for (int64_t k = 0; k < 8; ++k)
      {
        full[r][c] += half[r][k] * half[k][c];
        full[r][c] %= kMod;
      }
    }
  }

  if (k % 2)
  {
    for (int64_t r = 0; r < 8; ++r)
    {
      for (int64_t c = 0; c < 8; ++c)
      {
        m[r][c] = 0;
        for (int64_t k = 0; k < 8; ++k)
        {
          m[r][c] += full[r][k] * M[k][c];
          m[r][c] %= kMod;
        }
      }
    }
  }
  else
  {
    for (int64_t r = 0; r < 8; ++r)
    {
      for (int64_t c = 0; c < 8; ++c)
      {
        m[r][c] = full[r][c];
      }
    }
  }

  return;
}

int main(void)
{
  scanf(" %ld", &D);

  int64_t ret[8][8];
  Power(ret, D);

  /*
  int64_t answer = 0;
  for (int64_t k = 0; k < 8; ++k)
  {
    answer += ret[k][0];
    answer %= kMod;
  }
  */

  printf("%ld\n", ret[0][0]);

  return 0;
}

사람마다 푸는 방법은 여러가지가 있을텐데, 나는 그중에 가장 무지성으로 풀 수 있는(물론 복잡도는 다른 알고리즘에 뒤지지 않는다) lower_bound 풀이를 사용했다.

이 풀이는 배열을 처음부터 끝 원소까지 순차적으로 훑어가면서 아래의 벡터(배열이 아니다, 동적으로 변하는 벡터다)를 유지한다.

• CACHE[len]: 길이가 len인 LIS중 끝 원소가 가장 작은 LIS의 끝 원소

저 배열을 유지하는 방법은 아래와 같다.

i번째 원소를 보고 있다고 하자.

CACHE에서 A[i]의 lower_bound를 찾았고, 이 원소, lb,가 존재했다고 하자(즉, end를 리턴하지 않음).

그 이야기인 즉슨 lb를 A[i]로 바꿔치기 해도 여전히 lb로 끝났던 LIS만큼은 그대로 만들 수 있다는 이야기이다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> CACHE;

int main(void)
{
  scanf(" %d", &N);
  for (int it = 0; it < N; ++it)
  {
    int number;
    scanf(" %d", &number);

    auto l = lower_bound(CACHE.begin(), CACHE.end(), number);
    if (l == CACHE.end())
    {
      CACHE.emplace_back(number);
    }
    else
    {
      *l = number;
    }
  }

  printf("%d\n", (int)CACHE.size());

  return 0;
}

그닥 어려울 것 없는 DP 문제로 쉽게 쉽게 풀어줄 수 있다.

아래와 같이 CACHE를 정의하자.

• CACHE[s][e]: Matrix[s]부터 Matrix[e]까지 곱할 때 최소의 연산횟수

그럼 점화식은 아래와 같이 유도할 수 있다.

• CACHE[s][e] = min(CACHE[s][m] + CACHE[m+1][e] + Matrix[s].row * Matrix[s].col * Matrix[e].col)

결국 Matrix[s..e]를 m을 기준으로 두 파트로 나누어 보며 접근한다는 이야기이다.

굳이 주의할 점을 꼽아보자면 Bottom-up DP로 풀려면 루프 순서를 주의해주어야 한다는 점 정도가 있다.

#include <cstdio>
#include <limits>
#include <utility>
#include <algorithm>

using namespace std;

const int kMaxN = 500;

int N;
pair<int, int> M[kMaxN];

int CACHE[kMaxN][kMaxN];

int main(void)
{
  // Read input
  scanf(" %d", &N);
  for (int it = 0; it < N; ++it)
  {
    scanf(" %d %d", &M[it].first, &M[it].second);
  }

  // Solve
  for (int s = N - 1; s >= 0; --s)
  {
    for (int e = s + 1; e < N; ++e)
    {
      CACHE[s][e] = numeric_limits<int>::max();
      for (int m = s; m < e; ++m)
      {
        CACHE[s][e] = min(CACHE[s][e], CACHE[s][m] + CACHE[m + 1][e] + M[s].first * M[m].second * M[e].second);
      }
    }
  }

  // Print answer
  printf("%d\n", CACHE[0][N - 1]);

  return 0;
}

문제 설명이 조금 부족한데, 숫자 하나를 문자 하나로 취급해야 한다.

여튼 노말하게 DP를 써주면 풀리는 문제이다.

아래와 같이 CACHE를 정의하자.

• CACHE[s][e] = s ... e 번째 수가 palindrome인가?

점화식은 아래와 같다.

• CACHE[s][e] = (CACHE[s+1][e-1] && N[s] == N[e]) ? 1 : 0

#include <iostream>

using namespace std;

int32_t N, M;
int32_t NUMBER[2000];
uint8_t CACHE[2000][2000];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N;
  for (int it = 0; it < N; ++it)
  {
    cin >> NUMBER[it];
  }

  // DP
  for (int s = 0; s < N; ++s)
  {
    CACHE[s][s] = 1;
  }

  for (int s = N - 2; s >= 0; --s)
  {
    for (int e = s + 1; e < N; ++e)
    {
      if (s + 1 <= e - 1)
      {
        CACHE[s][e] = (CACHE[s + 1][e - 1] && NUMBER[s] == NUMBER[e]) ? 1 : 0;
      }
      else
      {
        CACHE[s][e] = (NUMBER[s] == NUMBER[e]) ? 1 : 0;
      }
    }
  }

  // Solve
  cin >> M;
  for (int it = 0; it < M; ++it)
  {
    int s, e;
    cin >> s >> e;
    cout << (int)CACHE[s - 1][e - 1] << '\n';
  }

  return 0;
}

이진 트리(i.e. std::set)을 활용해서 풀어주었다.

쉽게 풀고나서 혹시나 하는 마음에 문제 분류를 보니 Disjoint Set을 활용해서도 풀어줄 수 있는 모양이다.

시간복잡도 측면서에 내 풀이와 별반 다르지 않다는 생각이 들어서 다시 풀지는 않았다.

내 아이디어는 아래와 같다.

• 1번 게이트, 2번 게이트 ..., G번 게이트를 내림차순으로 std::set에 저장한다.
• 1 ~ g_i게이트에 도킹을 희망하는 비행기의 도킹 게이트는 위의 std::set에서 lower_bound로 찾아준다(역시 내림차순).
• 도킹을 못하면 더 이상 도킹 불가이니 그만 두고 답을 출력한다.
• 도킹을 할 수 있다면, lower_bound를 std::set에서 삭제해준다.

#include <set>
#include <cstdio>

using namespace std;

int G;
int P;
int PLANES[100000];

int main(void)
{
  scanf(" %d", &G);
  set<int> gates;
  for (int g = 1; g <= G; ++g)
  {
    gates.insert(-g);
  }

  scanf(" %d", &P);
  for (int it = 0; it < P; ++it)
  {
    scanf(" %d", &PLANES[it]);
  }

  int answer;
  for (answer = 0; answer < P; ++answer)
  {
    auto it = gates.lower_bound(-PLANES[answer]);
    if (it == gates.end())
    {
      break;
    }
    else
    {
      gates.erase(it);
    }
  }

  printf("%d\n", answer);

  return 0;
}

빡 구현 문제이다.

아래의 순서로 풀어주면 된다.

• 더 이상 새로운 열쇠도 발견하지 못하고, 문서도 발견하지 못할 때까지
  • 있는 열쇠로 열 수 있는 모든 문을 열어버린다(그 문까지 갈 수 있는지는 중요치 않음)
  • BFS를 돌면서 열쇠와 문서를 줍는다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

const int kMaxH = 100;
const int kMaxW = 100;

int H;
int W;
vector<string> BOARD;
vector<bool> KEYS;

void OpenDoors()
{
  for (int r = 0; r < H; ++r)
  {
    for (int c = 0; c < W; ++c)
    {
      if ('A' <= BOARD[r][c] && BOARD[r][c] <= 'Z' && KEYS[BOARD[r][c] - 'A'])
      {
        BOARD[r][c] = '.';
      }
    }
  }
}

inline bool IsVisitable(const int r, const int c)
{
  return (BOARD[r][c] == '.' || BOARD[r][c] == '$' || ('a' <= BOARD[r][c] && BOARD[r][c] <= 'z'));
}

pair<int, int> BfsOnce()
{
  OpenDoors();

  vector<vector<bool> > visited(H, vector<bool>(W, false));
  queue<pair<int, int> > q;

  for (int r = 0; r < H; ++r)
  {
    if (IsVisitable(r, 0))
    {
      visited[r][0] = true;
      q.emplace(r, 0);
    }
    if (IsVisitable(r, W - 1))
    {
      visited[r][W - 1] = true;
      q.emplace(r, W - 1);
    }
  }

  for (int c = 0; c < W; ++c)
  {
    if (IsVisitable(0, c))
    {
      visited[0][c] = true;
      q.emplace(0, c);
    }
    if (IsVisitable(H - 1, c))
    {
      visited[H - 1][c] = true;
      q.emplace(H - 1, c);
    }
  }

  pair<int, int> ret(0, 0);

  while (!q.empty())
  {
    int r = q.front().first;
    int c = q.front().second;
    q.pop();

    if (BOARD[r][c] == '$')
    {
      ++ret.first;
      BOARD[r][c] = '.';
    }
    else if ('a' <= BOARD[r][c] && BOARD[r][c] <= 'z')
    {
      if (!KEYS[BOARD[r][c] - 'a'])
      {
        ++ret.second;
        KEYS[BOARD[r][c] - 'a'] = true;
        BOARD[r][c] = '.';
      }
    }

    const int dr[4] = { -1, 0, 1, 0 };
    const int dc[4] = { 0, 1, 0, -1 };

    for (int dir = 0; dir < 4; ++dir)
    {
      int nr = r + dr[dir];
      int nc = c + dc[dir];
      if (0 > nr || nr >= H || 0 > nc || nc >= W)
      {
        continue;
      }
      if (!visited[nr][nc] && IsVisitable(nr, nc))
      {
        visited[nr][nc] = true;
        q.emplace(nr, nc);
      }
    }
  }

  return ret;
}

int Solve()
{
  int answer = 0;
  while (true)
  {
    auto ret = BfsOnce();
    if (ret.first == 0 && ret.second == 0)
    {
      break;
    }

    answer += ret.first;
  }

  return answer;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  int testcase;
  cin >> testcase;

  while (testcase--)
  {
    // Read input
    cin >> H >> W;
    BOARD.assign(H, "");
    KEYS.assign(26, false);
    for (int r = 0; r < H; ++r)
    {
      cin >> BOARD[r];
    }

    string keys;
    cin >> keys;
    if (keys.compare("0") != 0)
    {
      for (auto ch : keys)
      {
        KEYS[ch - 'a'] = true;
      }
    }

    // Solve
    cout << Solve() << '\n';
  }

  return 0;
}

전형적인 DP문제이고, DP 완료 후 백트래킹 정도가 추가된 문제이다.

아래와 같이 CACHE를 정의하자.

• CACHE[i][j]: A[0...i], B[0...j]까지 고려할 때 LCS의 길이

그럼 점화식은 아래와 같다.

• CACHE[i][j] = max(CACHE[i-1][j-1] + 1, CACHE[i-1][j], CACHE[i][j-1]) (단, CACHE[i-1][j-1] + 1 항은 A[i] == B[j]일 때만 고려)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int kMaxN = 1000;

string A;
string B;
int CACHE[kMaxN][kMaxN];

int GetLcsLength(const int i, const int j)
{
  if (i < 0 || j < 0)
  {
    return 0;
  }

  int& ret = CACHE[i][j];

  if (ret != -1)
  {
    return ret;
  }

  if (A[i] == B[j])
  {
    ret = GetLcsLength(i - 1, j - 1) + 1;
  }
  else
  {
    ret = max(GetLcsLength(i - 1, j), GetLcsLength(i, j - 1));
  }

  return ret;
}

string GetLcs(const int i, const int j)
{
  if (i < 0 || j < 0)
  {
    return "";
  }
  else if (A[i] == B[j])
  {
    return GetLcs(i - 1, j - 1) + A[i];
  }
  else if (GetLcsLength(i - 1, j) >= GetLcsLength(i, j - 1))
  {
    return GetLcs(i - 1, j);
  }
  else
  {
    return GetLcs(i, j - 1);
  }
}

int main(void)
{
  // Initialize
  for (int i = 0; i < kMaxN; ++i)
  {
    for (int j = 0; j < kMaxN; ++j)
    {
      CACHE[i][j] = -1;
    }
  }

  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read inputs
  cin >> A >> B;

  // Solve
  cout << GetLcsLength(A.size() - 1, B.size() - 1) << '\n';
  if (GetLcsLength(A.size() - 1, B.size() - 1))
  {
    cout << GetLcs(A.size() - 1, B.size() - 1) << '\n';
  }

  return 0;
}

문제를 보는 순간 바로 MST문제로 분류할 수 있었다.

하지만, 입력이 사실상 fully connected graph이므로 Prim이건, Kruskal이건 바로는 사용하지 못하는 문제였다.

첨에는 이진 트리를 사용하는 Prim으로 접근했었는데, 좋은 결과를 얻지 못했고,

결국에는 웹 서칭을 해서 아이디어를 얻었다...ㅎㅎ

아리디어의 핵심은 모든 간선을 다 볼 필요 없이 축 별로 인접한 녀석들만 봐주자는 것이다.

아마 구글 검색어 노출도 안되는 내 블로그까지 흘러들어와서 내 글을 보고 있는 당신은 대체 그게 왜 되는데?에 대한 의문을 품고 있으리라.

나 역시 증명에 시간을 꽤 할애하였으므로 증명을 보다 자세히 적어보도록 하겠다.

claim: 모든 간선이 (x축 || y축 || z축)에서 인접한 두 정점으로 이루어진 MST가 존재한다.

proof:

• 귀류법으로 증명한다.
• MST M내에 존재하는 어떠한 간선 (p, q)가 x, y, z 축 어디에서도 인접하지 않았다고 가정하자.
• 일반성을 잃지 않고 w(p, q) == |p.x - q.x|였다고 가정하자.
• 가정에 의해 w(p, r) <= w(p, q)를 만족하는 r이 존재한다.
• M에서 (p, q)를 삭제하면 M은 2개의 트리로 분리된다.
• 역시 일반성을 잃지 않고, r이 q가 속한 트리에 속해있다고 하자.
• 간선 (r, p)를 추가하면 2개의 트리로 분리되었던 M은 다시 하나의 트리가 된다. 이를 M_new이라 하자.
• w(p, r) <= w(p, q)이므로 M_new의 가중치 합이 M보다 작거나 같다.
• 작다면 가정에 모순이고, 같다면 위와 같이 바꾸어 나가면 된다.

#include <iostream>
#include <algorithm>
#include <cstdint>
#include <vector>

using namespace std;

inline int abs(const int x)
{
  return x >= 0 ? x : -x;
}

struct Planet
{
  int id;
  int x, y, z;

  Planet(const int id, const int x, const int y, const int z) : id(id), x(x), y(y), z(z)
  {
  }
};

struct XComparator
{
  bool operator()(const Planet& a, const Planet& b)
  {
    return a.x < b.x;
  }
};

struct YComparator
{
  bool operator()(const Planet& a, const Planet& b)
  {
    return a.y < b.y;
  }
};

struct ZComparator
{
  bool operator()(const Planet& a, const Planet& b)
  {
    return a.z < b.z;
  }
};

struct Edge
{
  int src;
  int dst;
  int weight;
  Edge(const int src, const int dst, const int weight) : src(src), dst(dst), weight(weight)
  {
  }

  bool operator<(const Edge& rhs) const
  {
    return weight < rhs.weight;
  }
};

class DisjointSet
{
private:
  vector<int> parents_;

public:
  DisjointSet(const int size) : parents_(size, -1)
  {
  }

  int Find(const int elem)
  {
    if (parents_[elem] == -1)
    {
      return elem;
    }
    else
    {
      return (parents_[elem] = Find(parents_[elem]));
    }
  }

  void Union(const int a, const int b)
  {
    parents_[Find(a)] = Find(b);
  }
};

int N;
vector<Planet> PLANETS;
vector<Edge> EDGES;

int64_t Kruskal()
{
  int64_t answer = 0;

  DisjointSet dset((int)EDGES.size());
  sort(EDGES.begin(), EDGES.end());

  int num_of_planets = 1;

  for (const auto& edge : EDGES)
  {
    if (num_of_planets == N)
    {
      break;
    }

    if (dset.Find(edge.src) != dset.Find(edge.dst))
    {
      answer += edge.weight;
      dset.Union(edge.src, edge.dst);
      ++num_of_planets;
    }
  }

  return answer;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N;
  for (int id = 0; id < N; ++id)
  {
    int x, y, z;
    cin >> x >> y >> z;
    PLANETS.emplace_back(id, x, y, z);
  }

  // Extract meaningful edges
  sort(PLANETS.begin(), PLANETS.end(), XComparator());
  for (size_t it = 0; it + 1 < PLANETS.size(); ++it)
  {
    EDGES.emplace_back(PLANETS[it].id, PLANETS[it + 1].id, abs(PLANETS[it].x - PLANETS[it + 1].x));
  }

  sort(PLANETS.begin(), PLANETS.end(), YComparator());
  for (size_t it = 0; it + 1 < PLANETS.size(); ++it)
  {
    EDGES.emplace_back(PLANETS[it].id, PLANETS[it + 1].id, abs(PLANETS[it].y - PLANETS[it + 1].y));
  }

  sort(PLANETS.begin(), PLANETS.end(), ZComparator());
  for (size_t it = 0; it + 1 < PLANETS.size(); ++it)
  {
    EDGES.emplace_back(PLANETS[it].id, PLANETS[it + 1].id, abs(PLANETS[it].z - PLANETS[it + 1].z));
  }

  // Kruskal
  cout << Kruskal() << '\n';
}

간단한 위상정렬 문제로 볼 수 있다.

각 가수를 그래프의 정점으로, 인접한 두 순서를 간선으로 표현한다면 입력은 그래프로 표현될 수 있다.

그래프의 순서를 유지하는 위상정렬 결과를 아무거나 하나 출력해주면 된다.

주의할 점으로는 아래의 것들이 있을 수 있다.

• 입력이 꼭 하나의 그래프로 표현되지 않을 수도 있다(2개 이상의 세그먼트)
  • 사이클을 이루는지의 판단이 필요하다(불가능한 경우 판별을 위해)
• 방향성 그래프에서 사이클 유무는 아래와 같이 간단하게 알 수 있다.
• DFS를 수행하면서,
• 인접한 정점이 이미 방문상태인데,
• 그 정점의 DFS가 완료되지 않았다.

#include <cstdio>
#include <vector>

using namespace std;

int N;
int M;
vector<bool> V;
vector<bool> F;
vector<vector<int> > G;

bool DoDfs(int here, vector<int>& topology)
{
  V[here] = true;
  for (const auto& there : G[here])
  {
    if (!V[there])
    {
      if (!DoDfs(there, topology))
      {
        return false;
      }
    }
    else if (!F[there])
    {
      return false;
    }
  }

  topology.emplace_back(here);
  F[here] = true;
  return true;
}

void Solve()
{
  vector<int> answer;
  for (int singer = 1; singer <= N; ++singer)
  {
    if (!V[singer] && !DoDfs(singer, answer))
    {
      printf("%d\n", 0);
    }
  }

  for (auto it = answer.rbegin(); it != answer.rend(); ++it)
  {
    printf("%d\n", *it);
  }

  return;
}

int main(void)
{
  // Read input
  scanf(" %d %d", &N, &M);
  V.assign(N + 1, false);
  F.assign(N + 1, false);
  G.assign(N + 1, vector<int>());
  for (int pd = 0; pd < M; ++pd)
  {
    int num_of_singers;
    int predecessor;
    int successor;
    scanf(" %d %d", &num_of_singers, &predecessor);

    for (int singer = 1; singer < num_of_singers; ++singer)
    {
      scanf(" %d", &successor);
      G[predecessor].emplace_back(successor);
      predecessor = successor;
    }
  }

  // Solve
  Solve();

  return 0;
}

정렬된 배열에서 서로 다른 3개의 원소 a, b, c를 뽑아 a + b + c = 0이 되도록하는 경우를 헤아리는 문제와 비슷하다.

a <= b <= c가 되도록 순서를 강제해주고, 각 a에 대해서 투 포인터를 진행해준다.

#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <limits>

using namespace std;

inline int64_t ABS(const int64_t x)
{
  return x >= 0 ? x : -x;
}

const int kMaxN = 5000;
const int64_t kMaxAcidity = numeric_limits<int64_t>::max();

int N;
int64_t ACIDITY[kMaxN];

void Solve()
{
  sort(ACIDITY, ACIDITY + N);

  int64_t min_acidity = kMaxAcidity;
  int64_t l1, l2, l3;

  for (int a = 0; a < N; ++a)
  {
    int lo = a + 1;
    int hi = N - 1;

    while (lo < hi)
    {
      int64_t sum = ACIDITY[a] + ACIDITY[lo] + ACIDITY[hi];
      if (ABS(sum) < min_acidity)
      {
        min_acidity = ABS(sum);
        l1 = ACIDITY[a];
        l2 = ACIDITY[lo];
        l3 = ACIDITY[hi];
      }

      if (sum < 0)
      {
        ++lo;
      }
      else
      {
        --hi;
      }
    }
  }

  printf("%ld %ld %ld\n", l1, l2, l3);
}

int main(void)
{
  scanf(" %d", &N);
  for (int it = 0; it < N; ++it)
  {
    scanf(" %ld", &ACIDITY[it]);
  }

  Solve();

  return 0;
}

그닥 어렵지 않게 풀 수 있는 DP 문제이다.

아래와 같이 CACHE를 정의하였다.

• CACHE[i][l][r] = i번째 입력까지 밟고, 오른발이 r, 왼발이 l에 있을 때의 최소 비용

사실 i번째 입력을 밟았다는 사실이 l, r 중 하나가 i번째 입력에 있음을 의미한다.

따라서, 남은 한발만 저장하는 방식으로 조금 더 최적화를 할 수는 있지만 굳이 그럴 것 까지는 없어보여 진행하지 않았다.

점화식은 간단하게, 왼발로 온 경우, 오른 발로 온 경우를 나누어 구해주면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 100000;
const int kMaxCost = kMaxN * 5;

const int kCost[5][5] = { { 0, 2, 2, 2, 2 },
                          { kMaxCost, 1, 3, 4, 3 },
                          { kMaxCost, 3, 1, 3, 4 },
                          { kMaxCost, 4, 3, 1, 3 },
                          { kMaxCost, 3, 4, 3, 1 } };

vector<int> SEQUENCE;

int CACHE[kMaxN][5][5];

int Solve()
{
  CACHE[0][SEQUENCE[0]][0] = 2;
  CACHE[0][0][SEQUENCE[0]] = 2;

  for (size_t seq = 1; seq < SEQUENCE.size(); ++seq)
  {
    for (int lr = 0; lr < 25; ++lr)
    {
      const int l = lr / 5;
      const int r = lr % 5;

      if (SEQUENCE[seq] != l && SEQUENCE[seq] != r)
      {
        continue;
      }

      if (l == r)
      {
        continue;
      }

      for (int p = 0; p < 5; ++p)
      {
        if (SEQUENCE[seq] == l)
        {
          CACHE[seq][l][r] = min(CACHE[seq][l][r], CACHE[seq - 1][p][r] + kCost[p][l]);
        }
        else
        {
          CACHE[seq][l][r] = min(CACHE[seq][l][r], CACHE[seq - 1][l][p] + kCost[p][r]);
        }
      }
    }
  }

  int answer = kMaxCost;
  for (int left = 0; left < 5; ++left)
  {
    for (int right = 0; right < 5; ++right)
    {
      answer = min(answer, CACHE[SEQUENCE.size() - 1][left][right]);
    }
  }

  return answer;
}

int main(void)
{
  while (true)
  {
    int target;
    scanf(" %d", &target);

    if (target == 0)
    {
      break;
    }

    SEQUENCE.emplace_back(target);
  }

  for (int i = 0; i < kMaxN; ++i)
  {
    for (int j = 0; j < 5; ++j)
    {
      for (int k = 0; k < 5; ++k)
      {
        CACHE[i][j][k] = kMaxCost;
      }
    }
  }

  printf("%d\n", Solve());

  return 0;
}

별 볼일 없는 백 트래킹 문제였다.

포인트 냠냠

#include <cstdio>

using namespace std;

const int kSize = 9;

int board[kSize][kSize];

void PrintBoard()
{
  for (int r = 0; r < kSize; ++r)
  {
    for (int c = 0; c < kSize; ++c)
    {
      printf("%d", board[r][c]);
    }
    printf("\n");
  }
}

bool Solve(const int idx)
{
  if (idx >= kSize * kSize)
  {
    PrintBoard();
    return true;
  }

  int row = idx / kSize;
  int col = idx % kSize;

  if (board[row][col] != 0)
  {
    return Solve(idx + 1);
  }

  bool used[kSize + 1] = {
    false,
  };

  for (int c = 0; c < kSize; ++c)
  {
    used[board[row][c]] = true;
  }

  for (int r = 0; r < kSize; ++r)
  {
    used[board[r][col]] = true;
  }

  int offset_row = 3 * (row / 3);
  int offset_col = 3 * (col / 3);
  for (int r = 0; r < 3; ++r)
  {
    for (int c = 0; c < 3; ++c)
    {
      used[board[offset_row + r][offset_col + c]] = true;
    }
  }

  for (int number = 1; number <= kSize; ++number)
  {
    if (!used[number])
    {
      board[row][col] = number;
      if (Solve(idx + 1))
      {
        return true;
      }
    }
  }

  board[row][col] = 0;
  return false;
}

int main(void)
{
  for (int r = 0; r < 9; ++r)
  {
    for (int c = 0; c < 9; ++c)
    {
      scanf(" %1d", &board[r][c]);
    }
  }

  Solve(0);

  return 0;
}

노말한 투 포인터 문제로, 서로 반대 방향에서 출발하는 투 포인터 알고리즘을 사용해주자.

#include <cstdio>
#include <limits>
#include <algorithm>

using namespace std;

inline int abs(const int x)
{
    return x >= 0 ? x : -x;
}

const int kMaxN = 100000;

int N;
int LIQUID[kMaxN];

void Solve()
{
    int answer_thickness = numeric_limits<int>::max();
    int answer_lo;
    int answer_hi;

    int lo = 0;
    int hi = N - 1;
    while (lo < hi)
    {
        int sum = LIQUID[lo] + LIQUID[hi];
        if (abs(sum) < answer_thickness)
        {
            answer_thickness = abs(sum);
            answer_lo = lo;
            answer_hi = hi;
        }

        if (sum == 0)
        {
            break;
        }
        else if (sum < 0)
        {
            ++lo;
        }
        else
        {
            --hi;
        }
    }

    printf("%d %d\n", LIQUID[answer_lo], LIQUID[answer_hi]);
}


int main(void)
{
    // Read Input
    scanf(" %d", &N);
    for (int it = 0; it < N; ++it)
    {
        scanf(" %d", &LIQUID[it]);
    }

    // Solve
    Solve();

    return 0;
}

문제가 어렵다기 보다는 자료구조를 여러개 써줘야한다.

• CCW를 활용한 선분 교차여부 판단을 위해서 벡터, 라인 자료구조를 사용하였고,
• 그루핑을 위해 서로소 집합을 사용하였다.

CCW를 활용하는 교차여부 판단 시 둘 다 0인 경우에만 예외처리가 필요함을 잘 기억해두도록하자.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

int N;

class Vector
{
public:
  int64_t x, y;

  Vector()
  {
  }
  Vector(const int64_t x, const int64_t y) : x(x), y(y)
  {
  }

  int64_t operator*(const Vector& rhs) const
  {
    return x * rhs.y - y * rhs.x;
  }

  Vector operator-(const Vector& rhs) const
  {
    return Vector(x - rhs.x, y - rhs.y);
  }

  bool operator<(const Vector& rhs) const
  {
    if (x != rhs.x)
    {
      return x < rhs.x;
    }

    return y < rhs.y;
  }
};

class Line
{
public:
  Vector start, end;

  Line()
  {
  }
  Line(const Vector& start, const Vector& end) : start(start), end(end)
  {
    if (end < start)
    {
      swap<Vector>(this->start, this->end);
    }
  }
};

bool HasIntersect(const Line& l1, const Line& l2)
{
  int64_t l1_l2 = ((l1.end - l1.start) * (l2.start - l1.end)) * ((l1.end - l1.start) * (l2.end - l1.end));
  int64_t l2_l1 = ((l2.end - l2.start) * (l1.start - l2.end)) * ((l2.end - l2.start) * (l1.end - l2.end));

  if (l1_l2 == 0 && l2_l1 == 0)
  {
    return !(l1.end < l2.start || l2.end < l1.start);
  }

  return l1_l2 <= 0 && l2_l1 <= 0;
}

class Set
{
public:
  vector<int> parent;
  vector<int> number_of_elem;
  Set(const int size) : parent(size, -1), number_of_elem(size, 1)
  {
  }
  int Find(const int idx)
  {
    if (parent[idx] != -1)
    {
      parent[idx] = Find(parent[idx]);
      return parent[idx];
    }
    return idx;
  }
  void Union(const int a, const int b)
  {
    int root_a = Find(a);
    int root_b = Find(b);
    if (root_a == root_b)
    {
      return;
    }
    parent[root_a] = root_b;
    number_of_elem[root_b] += number_of_elem[root_a];
  }
};

void Solve(const vector<Line>& lines)
{
  Set dset(N);

  for (int i = 0; i < N; ++i)
  {
    for (int j = i + 1; j < N; ++j)
    {
      if (HasIntersect(lines[i], lines[j]))
      {
        dset.Union(i, j);
      }
    }
  }

  int number_of_group = 0;
  int max_group_size = -1;

  for (int i = 0; i < N; ++i)
  {
    if (dset.parent[i] == -1)
    {
      ++number_of_group;
      max_group_size = max(max_group_size, dset.number_of_elem[i]);
    }
  }

  printf("%d\n%d\n", number_of_group, max_group_size);
}

int main(void)
{
  // Read input
  scanf(" %d", &N);
  vector<Line> lines;
  for (int it = 0; it < N; ++it)
  {
    Vector start, end;
    scanf(" %ld %ld %ld %ld", &start.x, &start.y, &end.x, &end.y);
    lines.emplace_back(start, end);
  }

  // Solve
  Solve(lines);

  return 0;
}

각 배열의 모든 부분합들을 미리 구하여 저장해놓는다.

이렇게 구해진 두 개의 부분합 배열을 각각 CAND_A, CAND_B라고 하자.

두 부분합 배열을 정렬한 뒤에 서로 다른 방향에서 시작하는 투 포인터 아이디어를 적용해주면 답을 쉽게 구할 수 있다.

단, 주의할 점으로는 투 포인터 아이디어는 정렬한 배열이 같은 원소를 포함하게 되는 경우 제대로 카운팅을 하기 어려워지는 문제가 있다는 점이다.

예를 들어, CAND_A, CAND_B가 아래와 같이 주어지고 lo, hi가 아래와 같다고 해보자.

• CAND_A: ... 3(lo) 3 3 ...
• CAND_B: ... 3 3 3(hi) ...

이 경우 T=6이라면, lo 또는 hi를 이동시키는 아이디어로는 올바르게 경우의 수를 셀 수 없다.

따라서, 나는 중복을 허용하지 않도록 CAND_A, CAND_B를 값, 빈도의 map으로 관리하였다.

#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int T;
int N;
int M;
vector<int> PSUM_A;
vector<int> PSUM_B;
map<int, int> CAND_A;
map<int, int> CAND_B;

int main(void)
{
  scanf(" %d", &T);

  scanf(" %d", &N);
  PSUM_A.emplace_back(0);
  for (int it = 1; it <= N; ++it)
  {
    int a;
    scanf(" %d", &a);
    PSUM_A.emplace_back(a + PSUM_A[it - 1]);
  }

  scanf(" %d", &M);
  PSUM_B.emplace_back(0);
  for (int it = 1; it <= M; ++it)
  {
    int b;
    scanf(" %d", &b);
    PSUM_B.emplace_back(b + PSUM_B[it - 1]);
  }

  for (int i = 1; i <= N; ++i)
  {
    for (int j = i; j <= N; ++j)
    {
      ++CAND_A[PSUM_A[j] - PSUM_A[i - 1]];
    }
  }

  for (int i = 1; i <= M; ++i)
  {
    for (int j = i; j <= M; ++j)
    {
      ++CAND_B[PSUM_B[j] - PSUM_B[i - 1]];
    }
  }

  int64_t answer = 0;
  auto lo = CAND_A.begin();
  auto hi = CAND_B.rbegin();

  while (lo != CAND_A.end() && hi != CAND_B.rend())
  {
    int sum = lo->first + hi->first;
    if (sum == T)
    {
      answer += (int64_t)lo->second * (int64_t)hi->second;
      ++lo;
      ++hi;
    }
    else if (sum < T)
    {
      ++lo;
    }
    else
    {
      ++hi;
    }
  }

  printf("%ld\n", answer);

  return 0;
}

고전적인 문제이니만큼 DP를 잘 활용해서 풀어주면 무난하게 풀린다.

단, 한 가지가 가물가물해서 조금 시간을 버렸는데 아래 사실을 유념하도록 하자.

• 어느 도시에서 시작하는 순회를 구하건 답은 같다(사이클이므로)
• 따라서, 항상 0번 도시에서 시작하고 돌아오는 경우를 구해주자

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef pair<int, int> neighbor_t;

const int kMaxN = 16;
const int kMaxCost = 1000000;

int N;
vector<vector<neighbor_t> > ADJ;
int CACHE[kMaxN][1 << kMaxN];

int Solve(const int city, const int visit)
{
  if (visit + 1 == (1 << N))
  {
    if (city == 0)
    {
      return 0;
    }
    else
    {
      for (const auto& neighbor : ADJ[city])
      {
        if (neighbor.first == 0)
        {
          return neighbor.second;
        }
      }

      return kMaxN * kMaxCost + 1;
    }
  }

  int& ret = CACHE[city][visit];
  if (ret != -1)
  {
    return ret;
  }

  ret = kMaxN * kMaxCost + 1;

  for (const auto& neighbor : ADJ[city])
  {
    int there = neighbor.first;
    int cost = neighbor.second;

    if (visit & (1 << there))
    {
      continue;
    }

    ret = min(ret, cost + Solve(there, visit | (1 << there)));
  }

  return ret;
}

int main(void)
{
  // Read inputs
  scanf(" %d", &N);
  ADJ.assign(N, vector<neighbor_t>());

  for (int u = 0; u < N; ++u)
  {
    for (int v = 0; v < N; ++v)
    {
      int cost;
      scanf(" %d", &cost);
      if (cost != 0)
      {
        ADJ[u].emplace_back(v, cost);
      }
    }
  }

  // Initialize cache
  for (int city = 0; city < kMaxN; ++city)
  {
    for (int visit = 0; visit < (1 << kMaxN); ++visit)
    {
      CACHE[city][visit] = -1;
    }
  }

  // Solve
  printf("%d\n", Solve(0, 1));

  return 0;
}

같은 위치에서 출발하는 투 포인터를 써준다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

size_t N;
int64_t S;
vector<int64_t> PSUM;

size_t Solve()
{
  size_t answer = N * 2;

  size_t lo = 1;
  size_t hi = 1;

  while (lo <= hi && hi <= N)
  {
    int64_t sum = PSUM[hi] - PSUM[lo - 1];
    if (sum >= S)
    {
      answer = min(answer, hi - lo + 1);
      ++lo;
    }
    else
    {
      ++hi;
    }
  }

  return answer > N ? 0 : answer;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N >> S;
  PSUM.emplace_back(0);

  for (size_t it = 1; it <= N; ++it)
  {
    int64_t number;
    cin >> number;
    PSUM.emplace_back(number + PSUM[it - 1]);
  }

  // Solve
  cout << Solve() << '\n';

  return 0;
}