ABC 401E (업솔빙)

• 해당 문서 참조.

BOJ 1504 : 특정한 최단 경로 (Gold 4)

• 과 의 경로 중 최솟값을 내보내면 된다.
• 다익스트라를 3번 사용하면 되므로 시간복잡도는 이다.

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;

using vi = vector<int>;
using pi = pair<int, int>;

constexpr int INF = numeric_limits<int>::max() / 4;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, e;
  cin >> n >> e;
  vector<vector<pi>> G(n+1);
  while (e--) {
    int a, b, c; cin >> a >> b >> c;
    G[a].emplace_back(c, b);
    G[b].emplace_back(c, a);
  }

  int v1, v2; cin >> v1 >> v2;

  auto dijkstra = [&G, n](int src) {
    vi dist(n+1, INF);
    dist[src]=0;
    priority_queue<pi, vector<pi>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
      auto [w, u] = pq.top(); pq.pop();
      if (dist[u] < w) continue;
      for (auto [w2, v] : G[u]) {
        if (dist[v] > w+w2) {
          dist[v] = w+w2;
          pq.push({w+w2, v});
        }
      }
    }
    return dist;
  };

  vi d_1 = dijkstra(1);
  vi d_v1 = dijkstra(v1);
  vi d_v2 = dijkstra(v2);

  int ans=min(d_1[v1] + d_v1[v2] + d_v2[n], d_1[v2] + d_v2[v1] + d_v1[n]);
  if (ans >= INF)
    cout << "-1";
  else
    cout << ans;

  return 0;
}

BOJ 27172 : 수 나누기 게임 (Gold 4)

• 나이브하게는 가 떠오른다. 더 나은 방법이 없을까?
• 처음에는 배수들의 카운트를 미리 깎아주는 식으로 처리하려고 했으나, TLE가 떴다. 뜨고 나니 , , 의 worst case가 떠올랐다.
• 약수를 카운트를 올려주면 된다.

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi arr(n);
  unordered_map<int, int> cnt_map;

  for (int i=0;i<n;i++) {
    cin >> arr[i];
    cnt_map[arr[i]]=0;
  }

  for (int i=0;i<n;i++) {
    int x=arr[i];
    for (int j=1;j*j<=x;j++) {
      if (x%j!=0) continue;

      if (cnt_map.count(j))
        cnt_map[j]++; cnt_map[x]--;
      if (j*j!=x && cnt_map.count(x/j))
        cnt_map[x/j]++; cnt_map[x]--;
    }
  }

  for (int i=0;i<n;i++)
    cout << cnt_map[arr[i]] << ' ';

  return 0;
}

BOJ 12015 : 가장 긴 증가하는 부분 수열 2 (Gold 2)

• LIS 문서를 참고하자.

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;

using vi = vector<int>;

constexpr int INF = numeric_limits<int>::max();

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi d(n+1, INF);
  d[0]=-INF;

  int ans=0;
  for (int i=0;i<n;i++) {
    int x; cin >> x;
    auto l=lower_bound(d.begin(), d.end(), x);
    *l=min(*l, x);
    ans=max(ans, (int) (l-d.begin()));
  }

  cout << ans;

  return 0;
}

BOJ 12738 : 가장 긴 증가하는 부분 수열 3 (Gold 2)

• 바로 위 문제와 크게 다르지 않다.

BOJ 14003 : 가장 긴 증가하는 부분 수열 5 (Platinum 5)

• 우선 으로 LIS를 구한다.
• 원래 LIS를 복원하는 것이 빡세다. 내가 생각해낸 알고리즘은 다음과 같다.
  • 우선 LIS를 구할 때, 를 변화시키는 각 에 대해 와 을 에 저장시킨다.
  • 그런 뒤, 다음 과정을 통해 LIS를 복원한다.

    for l=(LIS 길이) to 1 do
      S에서 l에 대해 i<=i_prev이면서 최대인 i를 찾는다.
      lcs[l] <- (위에서 찾은 i에 대해 a_i)
    

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using pi = pair<int, int>;

constexpr int INF = numeric_limits<int>::max();

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi d(n+1, INF);
  d[0]=-INF;

  unordered_map<int, vector<pi>> lis;
  int m=0;
  for (int i=0;i<n;i++) {
    int x; cin >> x;
    auto l=lower_bound(d.begin(), d.end(), x);
    int l_idx = l-d.begin();
    if (*l > x) {
      *l=x;
      lis[l_idx].emplace_back(i, *l);
    }
    m=max(m, l_idx);
  }

  cout << m << '\n';
  int i_prev=n;
  vi ans(m);
  for (int l=m;l>=1;l--) {
    auto x = upper_bound(lis[l].begin(), lis[l].end(), i_prev, [](int i, const pi& a) {
      return i < a.first;
    });
    x--;
    ans[l-1]=(*x).second;
    i_prev = (*x).first;
  }

  for (int x : ans)
    cout << x << ' ';

  return 0;
}

BOJ 14002 : 가장 긴 증가하는 부분 수열 4 (Gold 4)

• 위 문제의 널널한 버전이다.

BOJ 11779 : 최소비용 구하기 2 (Gold 3)

• 다익스트라 + 복원 문제다.

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;

using vi = vector<int>;
using pi = pair<int, int>;

constexpr int INF = numeric_limits<int>::max()/2;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector<vector<pi>> G(n+1);
  while (m--) {
    int a, b, c; cin >> a >> b >> c;
    G[a].emplace_back(c, b);
  }
  int src, dst; cin >> src >> dst;

  priority_queue<pi, vector<pi>, greater<>> pq;
  pq.emplace(0, src);
  vi d(n+1, INF);
  vi pred(n+1, -1);
  d[src]=0;
  while (!pq.empty()) {
    auto [w, u] = pq.top(); pq.pop();
    if (d[u]<w) continue;
    for (auto [w2, v] : G[u]) {
      if (d[v]>w+w2) {
        d[v]=w+w2;
        pred[v]=u;
        pq.emplace(w+w2, v);
      }
    }
  }

  cout << d[dst] << '\n';
  vi ans;
  int prev=dst;
  while (prev != -1) {
    ans.insert(ans.begin(), prev);
    prev = pred[prev];
  }
  cout << sz(ans) << '\n';
  for (int x : ans)
    cout << x << ' ';

  return 0;
}

BOJ 2143 : 두 배열의 합 (Gold 3)

• 해시맵과 누적합을 사용해서 해결하면 된다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  int n; cin >> n;
  vi A_sum(n+1);
  A_sum[0]=0;
  for (int i=1;i<=n;i++) {
    int x; cin >> x;
    A_sum[i]=A_sum[i-1]+x;
  }
  int m; cin >> m;
  vi B_sum(m+1);
  B_sum[0]=0;
  for (int i=1;i<=m;i++) {
    int x; cin >> x;
    B_sum[i]=B_sum[i-1]+x;
  }

  unordered_map<int, int> cnt;
  for (int i=0;i<=n;i++)
    for (int j=i+1;j<=n;j++)
      cnt[A_sum[j]-A_sum[i]]++;

  ll ans=0;
  for (int i=0;i<=m;i++) {
    for (int j=i+1;j<=m;j++) {
      int x = T-(B_sum[j]-B_sum[i]);
      if (cnt.count(x)) {
        ans += cnt[x];
      }
    }
  }

  cout << ans;

  return 0;
}

AtCoder Beginner Contest 402

• 언레로 참가했다. 해당 문서 참조.

Codeforces Round 1018 (Div. 1+2)

• 두 문제 풀었다. 해당 문서 참조.

BOJ 18110 : solved.ac (Silver 4)

• 몰랐는데 파이썬의 round는 오사오입으로 반올림이 구현되었나보다. int(x + 0.5)로 고쳐 해결할 수 있었다.

n = int(input())
if n == 0:
    print(0)
else:
    l = []
    for _ in range(n):
        l.append(int(input()))
    l.sort()
    k = int(n * 15 / 100 + 0.5)
    # [k, n-k)
    print(int(sum(l[k:n-k])/(n-2*k)+0.5))