hckim

문제링크

https://www.acmicpc.net/problem/25315

풀이

• ccw 이용해서 선분 교차 판정 해준다
• w 가 낮은거 부터 처리하는게 최적이다

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE
  
  auto ccw = [&](pld& p1, pld& p2, pld& p3) {
    ld s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
    s -= (p1.second * p2.first + p2.second * p3.first + p3.second * p1.first);
    if (s > 0) return 1;
    else if (s == 0) return 0;
    else return -1; 
  };

  auto f = [&](pld& p1, pld& p2, pld& p3, pld& p4) {
    auto p1p2 = ccw(p1, p2, p3) * ccw(p1, p2, p4); 
    auto p3p4 = ccw(p3, p4, p1) * ccw(p3, p4, p2); 

    // one line
    if (p1p2 == 0 && p3p4 == 0) {
      if (p1 > p2) swap(p1, p2);
      if (p3 > p4) swap(p3, p4);
      return p3 <= p2 && p1 <= p4; // intersect?
    }
    return p1p2 <= 0 && p3p4 <= 0;
  };

  int n;
  cin >> n;

  vector<tuple<ll, pld, pld> > line(n);

  for (int i = 0;  i < n; ++i) {
    auto& [a,b,c] = line[i];
    cin >> b.first >> b.second >> c.first >> c.second >> a;
  }
  sort(all(line));

  ll ans = 0;
  FOR(i, 0, n) {
    auto [w1, a, b] = line[i];
    ans += w1;
    FOR(j, i + 1, n) {
      auto [w2, c, d] = line[j];
      if (f(a, b, c, d)) ans += w1;
    }
  }
  cout << ans;
}

문제링크

https://www.acmicpc.net/problem/1441

풀이

f(x) 를 x 이하의 a 원소들로 나누어지는 자연수의 수 라고 하자

답은 f(r) - f(l - 1) 이 되겠다

f(x) 는 포함배제의 원리로

+ {원소 하나로 나누어지는 경우의 수}  - {원소 두개로 모두 나누어지는 경우의 수} ... 

이므로 고려한 수 가 홀수면 + 짝수면 - 를 곱해준다

시간복잡도는

$O(2^N + Nlog(1e9))$ 정도가 되겠다 

( 원소 선택 경우의수 + euclidean algorithm )

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE

  ll n, l, r;
  cin >> n >> l >> r;
  vl v(n);
  each(e, v) cin >> e;

  ll ansR = 0;
  ll ansL = 0;
  function<void(int, ll, int)> f = [&] (int cur, ll tmp, int cnt) {
    if (tmp > r) return;

    if (cur == n) {
      if (cnt > 0) {
        ll flag = (cnt % 2 ? 1 : -1);
        ansR += flag * (r / tmp);
        ansL += flag * ((l - 1) / tmp);
      }
      return;
    }

    f(cur + 1, tmp, cnt);
    f(cur + 1, tmp / gcd(tmp, v[cur]) * v[cur], cnt + 1);
  };

  f(0, 1, 0);
  cout << ansR - ansL;
}

문제링크

https://www.acmicpc.net/problem/16933

풀이

• 벽 부순 횟수 k, 행 r, 열 c 에 대해 BFS 돌린다
• 낮/밤 판별은 이동횟수 % 2 로 할 수 있다
• 이동 안할 때 큐 터지는 것에 주의
• (낮/밤 , k, r, c 로 BFS 돌려도 풀 수 있긴 하다)

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE

  int n, m, k;
  cin >> n >> m >> k;

  vs v(n);
  each(e, v) cin >> e;

  queue<tuple<int, int, int> > q;
  
  // k, r, c
  vector<vvi> vis(k + 1, vvi(n, vi(m)));

  q.push({0, 0, 0});
  vis[0][0][0] = true;
  int ans = 0;
  while (q.size()) {
    ++ans;
    int tmp = q.size();
    while (tmp--) {
      auto [fk, fr, fc] = q.front();
      int isDay = ans % 2;
      q.pop();
      if (fr == n - 1 && fc == m - 1) {
        cout << ans;
        return 0;
      }

      for (int dir = 0; dir < 4; ++dir) {
        int nr = fr + dr[dir];
        int nc = fc + dc[dir];
        int nk = fk;

        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
        if (vis[nk][nr][nc]) continue;
        if (v[nr][nc] == '1') {
          if (!isDay || fk == k) continue;
          nk++;
        }
        vis[nk][nr][nc] = true;
        q.push({nk, nr, nc});
      }

      // not move
      if (!isDay && vis[fk][fr][fc] != 2) {
        vis[fk][fr][fc] = 2;
        q.push({fk, fr, fc});
      }
    }
  }

  cout << -1;
}