Welcome to booknu's Blog!

• 코드포스 Educational Codeforces #58(Div.2)(Virtual) 리뷰 - 모닝코포

  2019-02-03

  booknu

  PS_Codeforces

  PS  Codeforces  구현  그리디  sorting  Math  트리  DP  GCD  소인수  Convex_Hull_Trick
  • 개요
  • A번
  • B번
  • C번
  • D번
  • E번
  • F번

  개요

  E번이 거의 쉬운 C급으로 쉬운 이상한 라운드이다.

  풀다가 대쉬보드에서 맞은 사람 수를 확인하지 않았다면 상당히 낭패를 볼 뻔 했다.

  A번

  A번 문제: 구현

  $[s, e]$구간이 쿼리로 주어지는데, 여기서 $d$의 배수인 것 중 $[s, e]$에 포함되지 않는 최소값을 찾는 문제이다.

  풀이 보기

  두 가지 경우로 나누면 간단하다.

  $d < s$인 경우 그냥 $d$ 자체가 답이다.

  아닌 경우 $e < i \cdot d$ 중 가장 $i \cdot d$를 찾으면 된다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  i64 s, e, x;
  void input() {
  	cin >> s >> e >> x;
  }
  
  int solve() {
  	if(x < s) {
  		cout << x << ENDL;
  		return 0;
  	}
  	i64 d = e/x;
  	if(x*d <= e) {
  		cout << x*(d+1) << ENDL;
  	} else {
  		cout << x*d << ENDL;
  	}
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	int TT; cin >> TT;
  	while(TT--)
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  B번

  B번 문제: 구현 그리디

  아코디언은 [:||||:] 형태이다.

  즉, [:과 :] 사이에 |이 0개 이상 들어가있는 구조이다.

  문자열이 하나 주어지는데, 여기서 원하는 만큼 문자를 지울 때 만들 수 있는 아코디언의 최대 길이를 구하면 된다.

  풀이 보기

  B번 문제 치고 조금 생각을 해야 하고 구현도 고려해야 할 점이 많은 문제이다.

  하지만 천천히 생각해보면, [, ]이 여러개 등장한다고 했을 때 가장 외곽의 [ ]를 남겨두는게 무조건 이득이라는 것을 알 수 있다.

  ::의 경우에도 위에서 구한 [ ]내에서 가장 외곽에 있는 것을 남겨두는게 무조건 이득이다.

  이렇게 되면 구한 ::안에 있는 |의 개수를 세서 가장 긴 아코디언을 만들면 된다.

  구현할 때 조심해야 할 점은 아코디언을 만들 수 없는 경우를 따로 처리해야 한다는 것이다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 5e5+10;
  string st;
  void input() {
  	cin >> st;
  }
  
  int solve() {
  	int s = -1, e = -1;
  	FOR(i, 0, st.size()) {
  		if(s == -1 && st[i] == '[') s = i;
  	}
  	RFOR(i, st.size()-1, 0) {
  		if(e == -1 && st[i] == ']') e = i;
  	}
  	if(s == -1 || e == -1 || s >= e) {
  		cout << -1 << ENDL;
  		return 0;
  	}
  	int cnt = 0;
  	int ss = -1, ee = -1;
  	FOR(i, s, e+1) {
  		if(ss == -1 && st[i] == ':') ss = i;
  	}
  	RFOR(i, e, s) {
  		if(ee == -1 && st[i] == ':') ee = i;
  	}
  	if(ss == ee) {
  		cout << -1 << ENDL;
  		return 0;
  	}
  	int ans = 4;
  	FOR(i, ss, ee+1) {
  		if(st[i] == '|') ++ans;
  	}
  	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  C번

  C번 문제: 구현 그리디

  $n$개의 $[s_i, e_i]$ 세그먼트가 주어지고, 우리는 이것들을 두 개의 비어있지 않은 그룹으로 분류해야 한다.

  단, 서로 다른 그룹에 속한 두 세그먼트의 교차점이 없어야 한다.

  풀이 보기

  어떤 세그먼트 $a$와 겹쳐지는 세그먼트들의 집합을 $A$라고 할 때, $A$는 무조건 같은 그룹에 속해야 한다.

  또한 $A$와 겹쳐지는 세그먼트 또한 $a$와 같은 그룹에 속해야 하고, 이것은 겹쳐지는 세그먼트가 없을 때까지 반복된다.

  그 외의 세그먼트들은 같은 그룹에 속하든, 다른 그룹에 속하든 문제가 되지 않는다.

  이것을 가장 쉽게 구현할 수 있는 방법은 구간을 $s_i$순으로 정렬 후 순서대로 순회하며 앞의 구간과 겹쳐지면 무조건 같은 그룹에, 겹쳐지지 않으면 다른 그룹에 넣는 것이다.

  또한 두 그룹은 비어있지 않은 상태여야 하기 때문에 이것에 대한 처리도 해야하는 것에 주의해야 한다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e5+10, RANGE = 2e5+10;
  int n, ord[MAXN], ans[MAXN];
  ii seg[MAXN];
  vi g[2];
  void input() {
  	cin >> n;
  	FOR(i, 0, n) cin >> seg[i].first >> seg[i].se;
  }
  
  int solve() {
  	FOR(i, 0, n) ord[i] = i;
  	sort(ord, ord + n, [](int u, int v) { return seg[u] < seg[v]; });
  	int me = -1;
  	FOR(i, 0, 2) g[i].clear();
  	int cur = 0;
  	FOR(j, 0, n) {
  		int i = ord[j];
  		if(me < seg[i].fi) {
  			cur ^= 1;
  		}
  		me = max(seg[i].se, me);
  		g[cur].pb(ord[j]);
  		ans[ord[j]] = cur;
  	}
  	if(g[0].size() && g[1].size()) {
  		FOR(i, 0, n) cout << ans[i]+1 << ' '; cout << ENDL;
  	} else {
  		cout << -1 << ENDL;
  	}
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	int TT; cin >> TT;
  	while(TT--)
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  이번에도 문제를 잘못 읽어 무려 2번이나 삽질하고 시간도 많이 날려먹었다.

  같은 그룹에 겹쳐지는 세그먼트가 들어가면 안 되는 건줄 알고 fenwick도 사용하며 열심히 구현했는데 너무 허무했다.

  특히 예제가 잘못 읽은 문제나 원래 문제나 똑같은 출력이 나오기 때문에 잘못을 알기까지 꽤 많은 시간이 걸렸다.

  매 코포 컨테스트마다 이런 실수가 나오는데 앞으로는 좀 더 문제를 자세히 읽어야겠다.

  D번

  D번 문제: Math GCD 트리 DP 소인수

  어떻게 된게 D번이 E번보다 어렵다.

  $n$개의 정점으로 이루어진 트리가 주어지고, 각 정점마다 $[1..2 \cdot 10^5]$의 가중치가 부여되어 있다.

  $g(u, v)$는 $u$정점에서 $v$정점까지의 단순 경로에 있는 정점들의 gcd값을 의미한다.

  $dist(u, v)$는 $u$정점에서 $v$정점까지의 단순 경로에 있는 정점들의 수를 의미한다.

  이 때, $g(u, v) > 1$ 인 경로들 중 $dist(u, v)$의 최대값을 구해야 한다.

  풀이 보기

  여러 수의 gcd가 $2$이상이라는 소리는 그들의 공통된 소인수가 하나라도 존재한다는 것이다.

  즉, 공통된 소인수가 단 하나라도 있는 경로 중 최장 경로의 길이를 구해야 한다..

  일단 공통 소인수라는 조건 없이 최장 경로를 구하는 것은 간단한 Tree DP로 해결이 가능하다.

  $dp[u] = max(path({sub}_u, u))$

  DP값을 채울 때는 Bottom-Up 방식으로 $dp[u] = 1 + max(dp[{child}_u])$로 채워나가면 된다.

  또한 실제 최장 경로를 구할 때는 모든 정점 $u$에서 $dp[{child}_u]$값 중 가장 큰 $2$개를 골라 더한 것들 중 최대값을 찾으면 된다.

  (사실 DP까지도 필요 없지만, 다음 문제 해결을 위해 이렇게 적었다.)

  하지만, 이 문제에서는 그런 경로 중 공통된 소인수가 단 하나라도 있어야하므로, DP를 살짝 재정의 해야할 것 같다.

  $dp[u][x]$ = $path({sub}_u, u)$ 중 $x$를 공통 소인수로 하는 최대 길이

  이렇게 하면 아까와 마찬가지로 Bottom-Up 방식으로 자식 정점들에 dp값을 미리 채워두고, 현재 $u$에서 $weight[u]$의 소인수 $x$들에 대해 $dp[u][x] = max(1 + dp[{child}_u][x])$로 dp값을 점점 채워나가면 된다.

  실제 최장 경로를 구할 때에도 이전과 마찬가지로 구하면 된다.

  그런데 이렇게 하면 각 정점마다 해당 소인수의 개수만큼 저장할 공간이 늘어나니까 MLE가 발생하지는 않을까?

  $2 \cdot 10^5$이내의 수는 $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = 510,510$이기 때문에 소인수가 최대 6개 밖에 없기 때문에 문제가 되지 않는다.

  또한 $2 \cdot 10^5$개의 $2 \cdot 10^5$이내의 자연수를 빠르게 소인수분해를 할 수 있는 수단이 필요한데, 이것은 이전에 소개했던 오일러의 체를 활용하면 쉽게 구현할 수 있다.

  마지막으로 $dp[u][x]$를 정직하게 배열로 구현해버리면 당연히 MLE가 발생하기 때문에, map으로 구현을 해줘야 한다.

  소스코드 보기

  
  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T> ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T> ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 2e5+10, RANGE = 2e5+10;
  int n, ar[MAXN], pn, spf[RANGE], pr[RANGE], par[MAXN], ans;
  map<int, int> dp[MAXN];
  vi g[MAXN], pf[RANGE];
  void input() {
  	cin >> n;
  	FOR(i, 0, n) cin >> ar[i];
  	FOR(i, 0, n-1) {
  		int u, v; cin >> u >> v; --u, --v;
  		g[u].pb(v);
  		g[v].pb(u);
  	}
  }
  
  void eulerSieve() {
  	FOR(x, 2, RANGE) {
  		if(!spf[x]) spf[x] = pr[pn++] = x;
  		for(int j = 0; x*pr[j] < RANGE; ++j) {
  			spf[x*pr[j]] = pr[j];
  			if(x % pr[j] == 0) break; 
  		}
  	}
  	FOR(i, 2, RANGE) {
  		int x = i;
  		while(spf[x]) {
  			int cur = spf[x];
  			pf[i].pb(cur);
  			while(x % cur == 0) x /= cur;
  		}
  	}
  }
  
  void f(int u) {
  	for(int v : g[u]) if(par[u] != v) par[v] = u, f(v);
  	for(int x : pf[ar[u]]) {
  		int fir = 0, sec = 0;
  		for(int v : g[u]) {
  			if(par[v] == u) {
  				sec = max(sec, dp[v][x]);
  				if(fir < sec) swap(fir, sec);;
  			}
  		}
  		dp[u][x] = 1+fir;
  		ans = max(ans, 1 + fir + sec);
  	}
  }
  
  int solve() {
  	eulerSieve();
  	memset(par, -1, sizeof(par));
  	par[0] = MAXN;
  	f(0);
   	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  
  

  후기

  C번에서 죽을 쒀서 쉬웠던 E번 솔브 속도가 느려졌다.

  따라서 이대로 라운드가 끝나버리면 700등이 돼 버리는데, 만약 D번을 늦게라도 풀면 200~400등까지는 노려볼만 했다.

  Tree DP문제라는 것을 감을 잡고 소인수를 이용하면 상태공간을 많이 줄일 수 있다는 것을 알고 열심히 구현했지만, 중간에 DP 업데이트를 실수해서 시간 내에 AC를 받지 못해 아쉬웠다.

  계속 코드를 보면서 “맞는데 왜 틀렸지?”라고 생각했는데, 코포를 끝내고 샤워를 하던 도중에 DP값 업데이트와 ans값 업데이트는 따로 해줬어야 한다는 것을 알고 너무 아쉬웠다.

  즉, 내가 처음에 짰던 코드는 아래와 같은데

  ...
  ans = max(ans, dp[u][x] = 1 + fir + sec);
  

  이렇게 해버리면 $dp[u][x]$는 “$u$를 지나고, 공통 소인수가 $x$인 경로의 최장길이”가 되어버린다.

  따라서 아래와 같이 $u$에서는 아래 1개의 경로 값만을 받아와야만 했다.

  ...
  dp[u][x] = 1+fir;
  ans = max(ans, 1+fir+sec);
  

  E번

  E번 문제: 구현 그리디

  쉬울 때의 C번과 비슷한 수준의 문제여서 당황스러웠던 문제이다.

  지폐가 여러 장 주어지고, 모든 지폐가 지갑에 들어갈 수 있는지 구해야한다.

  지폐와 지갑은 모두 직사각형 모양으로 가로, 세로 길이가 주어진다.

  지폐는 지갑에 회전시켜서 넣을 수 있고, 겹쳐지는 부분이 있어도 상관 없다.

  $5 \cdot 10^5$개의 쿼리가 주어지는데, 쿼리는 두 종류이다.

  1. $+\ x\ y$ : $x \times y$크기의 지폐를 추가한다.
  2. $?\ h\ w$ : $w \times h$크기의 지갑에 현재까지의 지폐가 모두 들어갈 수 있는지 출력한다.

  풀이 보기

  지폐를 회전시키지 않는다고 생각하면 단순히 현재까지의 지폐 중 $max(x_{i..n})$, $max(y_{i..n})$이 지갑에 들어가는지를 알아보면 된다.

  하지만 회전시켜야 하는 경우를 고려해야 하는데, 이것은 지폐던 지갑이던 놓는 방향을 무조건 $w \leq h$인 방향으로 놓도록 강제하면 위와 같은 방법으로 해결 할 수 있다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  int QQ;
  void input() {
  	cin >> QQ;
  }
  
  int solve() {
  	int mx = 0, my = 0;
  	while(QQ--) {
  		char typ; cin >> typ;
  		if(typ == '+') {
  			int x, y; cin >> x >> y;
  			if(x > y) swap(x, y);
  			mx = max(x, mx), my = max(y, my);
  		} else {
  			int x, y; cin >> x >> y;
  			if(x > y) swap(x, y);
  			if(x >= mx && y >= my) cout << "YES" << ENDL;
  			else cout << "NO" << ENDL;
  		}
  	}
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  C번에서 삽질하느라 이 문제를 읽는 시간이 느려졌지만, 문제가 너무 쉬워 6분만에 풀었다.

  코드를 짜면서도 “정말 이게 답인가? 뭔가 함정이 있는게 아닌가?” 싶을 정도였다.

  개인적으로 이렇게 난이도가 뒤죽박죽인 문제는 안 나왔으면 좋겠다.

  F번

  F번 문제: DP Convex Hull Trick

  라운드가 끝나고 손도 대지 않았던 F번을 봤는데, “최대값을 최소화” 하라는 단서를 보고 Binary Search인줄 알았다.

  그래서 탱크 크기가 $x$일 때 모든 트럭이 목적지에 도착할 수 있나? 라는 판단 함수만 만들어내면 답이 나오는데, 그 판단을 내가 생각한 것은 $O(n \cdot m)$에 내려버리기 때문에 TLE가 날 것 같았다.

  더 좋은 방법이 생각나지 않아 아예 처음부터 다시 시작하여 탱크의 크기는 우리가 결정하지만, 각 트럭의 운행 구간 $[s, e]$와 연비 $c$, 충전 횟수 $r$은 탱크의 크기와 독립적으로 항상 고정 된다는 정보를 이용하기로 했다.

  또한 트럭들은 항상 한 쪽 방향(index가 증가하는 방향)으로만 운행을 하고, 겹치는 운행구간이 많다는 점도 이용해볼만 했다.

  그러나 여기서 발목을 잡는게 연비 $c$가 트럭마다 다르다는 것인데, 나는 애초에 탱크의 용량 $V$에 집중하지 않기로 했다.

  그 대신, 트럭이 $[s, e]$를 이동 할 때 최대 $r$번 끊어서 이동할 수 있다는 점을 이용하고 싶었는데, 이것으로 dp 식을 만들 수 있을 것 같았다.

  $dp[s][e][x] = [s..e]$구간을 총 $x$번 쪼개어 운행한다고 했을 때, 길이가 최대인 구간이 최소인 값

  이것을 구해놓으면 각 트럭마다 $c_i \cdot dp[s_i][e_i][r_i+1]$이 필요한 최소 탱크 용량이므로 $V$는 이것들의 $max$값을 취하면 쉽게 구할 수 있을 것이다.

  그러나 문제되는 점이 dp를 실제로 계산할 때인데,

  $dp[s][e][x] = min(max(dp[s][j][x-1], dist[i..j]))\ \ \ \ for\ j = [s..e)$

  이와 같이 점화식이 나온다.

  그러나 점화식 자체에서 $O(n)$이 걸리므로, 총 시간복잡도는 $O(n^4)$가 돼 버린다.

  한창 백준에서 USACO문제들을 풀 때 저런 점화식을 유도했는데 시간복잡도가 너무 큰 경우가 있었는데, 그 때 시간복잡도를 줄이는 트릭이 Convex Hull Trick이었다.

  그러나 나는 아직 기하를 공부하지 않았고 Convex Hull이라는 단어만 나와도 치가 떨리는 수준이기 때문에 제대로 공부를 하지 않고 넘어갔었는데, 이번 문제도 혹시 그런가하고 살짝 튜토리얼에서 Convex를 검색해봤다.

  역시나 Convex Hull Trick을 사용한 문제였고, 조만간 그것에 대해서 제대로 공부해야겠다는 생각이 들었다..

  튜토리얼을 보니 이것 외에도 다른 방법이 있는 것 같았는데 설명이 제대로 나와있지 않아 그 방법에 대해서는 모르겠다. (아마 Binary Search를 사용한 방법인 것 같다.)

  Read All

  ---

• 코드포스 Codeforces #532(Div.2)(Virtual) 리뷰

  2019-02-02

  booknu

  PS_Codeforces

  PS  Codeforces  구현  기하  Interactive  그리디
  • 개요
  • A번
  • B번
  • C번
  • D번
  • 후기

  개요

  이번 라운드는 전형적인 C번까지는 쉽고, D번에서 갑자기 어려워지는 라운드였다.

  C번까지 느리게 풀거나 패널티를 좀 받으면 1400등 정도가 되고, 거기서 D, E, F 중 한 개를 풀면 200등권으로 들어올 수 있었다.

  A번

  A번 문제: 구현

  단순한 구현 문제다.

  $n$개의 원소를 가진 배열이 주어지며, 각 원소는 -1 혹은 1이다.

  또한 입력으로 $k$가 주어지며, 여기서 적절한 $b$를 선택해 $b+i \cdot k$에 해당되는 원소들을 모두 지웠을 때 남은 1과 -1의 개수의 차이가 가장 크게 만드는 경우를 찾아야 한다.

  이 때 $i$는 정수이다 (음수, 양수, 0 가능)

  풀이 보기

  문제 조건을 잘 봐야 하는데, $i$는 음, 양, 0 모두가 가능한 정수이다.

  즉, b가 아무리 크더라도 b를 포함한 그 이전, 이후 모두가 지워져야 한다는 것이다.

  이것만 조심하면 문제에서 설명 된 그대로 시뮬레이팅 하며 답을 찾으면 된다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e2;
  int n, k, a, b, ar[MAXN];
  void input() {
  	cin >> n >> k;
  	FOR(i, 0, n) {
  		cin >> ar[i];
  		if(ar[i] == 1) ++a;
  		else ++b;
  	}
  }
  
  int solve() {
  	int ans = 0;
  	FOR(i, 0, k) {
  		int ca = a, cb = b;
  		for(int j = i; j < n; j += k) {
  			if(ar[j] == 1) --ca;
  			else --cb;
  		}
  		ans = max(ans, abs(ca-cb));
  	}
  	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  B번

  B번 문제: 구현

  $m$개의 $[1..n]$들로 이루어진 배열이 주어진다.

  $[1..n]$원소들을 하나의 그룹으로 묶을 수 있을 때 총 몇 개의 그룹이 나오는지 구해야 한다.

  풀이 보기

  그냥 크기 $n$짜리 배열을 0으로 초기화 한 후 각 수가 몇 번씩 등장하는 지를 센 다음 $min(cnt[1..n])$을 구하면 된다.

  그런데 나는 처음에 문제를 잘못 보고 잘못된 코드를 바탕으로 코드를 짰기 때문에 이상하게 구현이 됐다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e5+10;
  int n, m, ar[MAXN], vis[MAXN], cc[MAXN];
  void input() {
  	cin >> n >> m;
  	FOR(i, 0, m) cin >> ar[i];
  }
  
  int solve() {
  	int sta = 0;
  	string ans;
  	FOR(i, 0, m) {
  		++cc[++vis[ar[i]]];
  		if(cc[sta+1] == n) {
  			++sta;
  			ans.pb('1');
  		} else ans.pb('0');
  	}
  	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  C번

  C번 문제: 기하

  

  다음과 같이 $n$개의 반지름이 같은 원들로 둘러쌓인 안쪽에 원이 하나 더 있는 형태의 그림이 있다.

  이 때 안쪽의 원의 반지름 $r$이 주어졌을 때 바깥쪽의 원의 반지름을 구해야한다.

  풀이 보기

  

  위 그림을 보면 바깥쪽 원의 중심을 이으면 정$n$각형이 나온다는 것을 알 수 있다.

  또한 정$n$각형은 $n$개의 안쪽 이등변삼각형으로 이루어진다는 것을 이용하면 삼각함수를 이용해 안쪽 원의 반지름을 구할 수 있다.

  위 그림에서 반으로 쪼개진 직각삼각형 쪽을 보면 파란색 변은 우리가 구해야 할 $x$, 연두색 변은 $x+r$이다.

  따라서 $(x+r)\cos\theta = x$이고, 식을 전개하면 $x = \frac{r\cdot\cos\theta}{1-\cos\theta}$가 된다.

  $\theta$는 정다각형의 한 내각의 반이므로 문제 없이 구할 수 있다.

  소스코드 보기

  #define _USE_MATH_DEFINES
  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  double n, r;
  void input() {
  	cin >> n >> r;
  }
  
  int solve() {
  	double st = 1.0*(n-2)/n/2.0;
  	double coss = cos(M_PI * st);
  	cout.precision(10);
  	cout << r*coss / (1-coss) << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  처음에 주어진 반지름 $r$이 바깥 원의 반지름인줄 알고 구현을 했다가 예제가 이상하게 나와서 당황했다.

  또한 $\cos(x)$에 $x$를 라디안 형태($x\pi$)로 줘야 했지만, 실수로 $\pi$를 곱하지 않은 각도를 줘버려서 이상한 결과가 나와서 시간을 많이 버렸다.

  D번

  D번 문제: Interactive 그리디

  문제가 장황하게 길지만, 살펴보면 별거 없다.

  $999\times999$ 크기의 판이 주어지고, $1$개의 킹, $666$개의 룩의 현재 위치가 주어진다.

  킹과 룩은 기존 체스와는 약간 다르게 움직인다.

  킹의 경우는 플레이어가 움직이며, 플레이어가 게임이 시작하면 선을 잡는다.

  1. 룩이 있는 곳으로 가지 못한다.
  2. 움직일 수 있는 범위는 일반 킹의 경우와 같다. (상하좌우 대각선 범위 1 이내)
  3. 룩과 같은 행, 열로 갈 수 있다. (이런 경우가 우리의 최종 목적(체크 당하기)이다.)
  4. 킹이 룩에 의해 체크를 당한 경우 플레이어가 이긴 것으로 판단한다.

  즉, 다른점이라고 한다면 룩을 먹지 못하고, 스스로 체크 당하러 갈 수 있다는 것이다.

  룩을 살펴보면

  룩의 경우는 시스템이 움직이며, 항상 킹이 움직인 뒤에 움직인다.

  1. 현재 룩의 좌표가 어떻든, 킹과 룩이 없는 아무 빈 곳으로나 움직일 수 있다. (아예 안 움직일 수도 있다.)
  2. 킹과 같은 행, 열로 가지 못한다. (즉, 킹이 체크당하면 플레이어가 이기는데, 스스로 체크를 하러 가지 못한다.)

  이 때, $2000$턴 이내에 킹이 체크당하도록 움직이는 것이 우리의 목표이다.

  인터랙티브 방식은 우리가 킹을 다음 좌표 $(x, y)$로 움직이면, 시스템이 $k$번째 룩을 $(x, y)$로 움직였다는 정보를 준다.

  풀이 보기

  룩의 2번 조건 때문에 킹이 스스로 룩의 범위로 들어가지 않는 한 운 좋게 룩이 와줘서 이기는 경우는 없다.

  또한 룩의 공격범위에 들어간다고 생각하지 말고, 룩은 아무 기능도 안 하고 움직이기만 하는데 킹이 룩의 공격범위를 갖고 룩을 잡으러 다닌다고 생각해보자.

  시스템이 영리하게 플레이한다고 가정했을 때 룩에게 점점 다가갈 때 도망을 갈 수단이 없어야 이길 수 있다.

  이것을 위해 룩은 아무 좌표로나 이동할 수 있다는 사기성을 지니고 있지만, 한 턴에 한 개의 룩 밖에 움직이지 못한다는 약점을 이용해야 한다.

  그러려면 킹이 점점 룩들을 몰아넣어 놓고 조여가는 것이 가장 이상적일 것이다.

  그 중에서도 가장 좋은 방법은 킹이 맵의 정중앙$(500, 500)$에서 시작하는 것이고, 아래와 같이 한 쪽 대각선으로 움직이며 조여가게 하는 것이다.

  

  일단 한 쪽 대각선으로 쭉 움직이는 것은 알겠는데, 네 대각선 방향 중 어느 곳으로 움직여야 할까?

  해당 대각선으로 움직이고 있다고 가정할 경우, 최악의 경우는 시스템이 조여지는 범위 내의 룩들을 모두 대각선의 반대방향으로 이동시켜버리는 것이다.

  즉, 그림에서 파란색 부분을 대각선 반대 방향의 흰색으로 움직이는 경우이다.

  이런 최악의 경우를 생각하면, 플레이어는 킹을 최대한 조여지는 대상 룩이 많은 대각선 방향으로 움직여야 한다.

  즉, 파란색 부분에 룩들이 가장 많이 포함되는 방향으로 이동해야 한다는 것이다.

  이런 방법으로 반드시 킹은 체크 당할 기회가 있다는 것은 아래와 같이 쉽게 증명할 수 있다.

  [ 증명 ]

  룩은 총 $666$개인데, 킹을 정중앙으로 놓았을 때 정말 운이 좋지 않은 경우는 4방향 모두 고르게 룩이 분포되는 것일 것이다.

  그렇게 되면 어떤 방향으로 조이든 총 룩의 $\frac{3}{4}$밖에 조이는 대상이 되지 않지만, $666 \cdot \frac{3}{4} = 499.5$이므로 킹이 대각선 끝까지 갈 동안 499번의 움직임을 소모한다는 것을 감안하면 무조건 킹은 체크 당할 기회가 있는 것이다.

  이동할 대각선을 구하는 것에 대한 구현은 약간 트릭을 사용해서 구현했는데 봐두면 좋을 것 같다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e3;
  const int dy[4] = { 1, 1, -1, -1 }, dx[4] = { 1, -1, 1, -1 };
  int ky, kx, cc[4], ry[MAXN], rx[MAXN], m[MAXN][MAXN];
  void input() {
  	cin >> kx >> ky;
  	m[ky][kx] = -1;
  	FOR(i, 1, 667) cin >> rx[i] >> ry[i], m[ry[i]][rx[i]] = i;
  }
  
  bool moverock() {
  	int k, y, x; cin >> k >> x >> y;
  	if(k == -1 && y == -1 && x == -1) return true;
  	m[ry[k]][rx[k]] = 0;
  	m[y][x] = k;
  	ry[k] = y, rx[k] = x;
  	return false;
  }
  
  bool moveking(int y, int x) {
  	if(m[y][x] != 0) return false;
  	m[ky][kx] = 0;
  	m[y][x] = -1;
  	ky = y, kx = x;
  	cout << kx << ' ' << ky << ENDL;
  	return true;
  }
  
  int solve() {
  	// 일단 king 중앙으로 옮기기
  	while(ky != 500 || kx != 500) {
  		int ny = ky == 500 ? ky : ky + (500-ky)/abs(500-ky), nx = kx == 500 ? kx : kx + (500-kx)/abs(500-kx);
  		if(!moveking(ny, nx)) assert(moveking(ky, nx));
  		if(moverock()) return 0;
  	}
  	// 반대방향 구하기
  	FOR(i, 0, 1000) FOR(j, 0, 1000) if(m[i][j] > 0) ++cc[(i < 500 ? 0 : 2) + (j < 500 ? 0 : 1)];
  	int md = min_element(cc, cc+4) - cc;
  	// 대각선으로 이동
  	while(1) {
  		int ny = ky + dy[md], nx = kx + dx[md];
  		if(!moveking(ny, nx)) assert(moveking(ky, nx));
  		if(moverock()) return 0;
  	}
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  처음에는 아래와 같이 실수로 $1,000$을 $100$으로 적는 바람에 런타임 에러가 발생해서 첫 번째로 멘탈이 깨졌고,

  FOR(i, 501, 100)
  ...
  

  두 번째 제출 때는 dy, dx를 잘못 적어서 엉뚱한 대각선으로 이동하는 바람에 WA가 발생해서 두 번째로 멘탈이 깨졌다.

  const int dy[4] = { 1, -1, 1, -1 }, dx[4] = { 1, 1, -1, -1 };
  

  다행히 라운드가 끝나기 12분 전에 실수를 찾아 고쳐서 AC를 받았지만, 딱히 테스트 할 방법이 없는 인터랙티브 문제에서 AC가 안 뜨면 너무 답답한 것 같다.

  후기

  B 잘못 읽어서 삽질하고, C 잘못 읽고 삼각함수에 익숙하지 않아 삽질하는 바람에 C까지 풀었을 때 등수가 $1200$등이어서 상당히 멘탈이 깨졌었다.

  D를 풀면서 보니 C까지 푼 사람들은 많았지만, D, E, F를 푼 사람은 두 자리수 단위였다.

  따라서 D를 풀면 $200$등, 못 풀면 $1400$등이라는 끔찍한 갭이 생기는데, 하필이면 D가 인터랙티브 문제고 문제도 뭔가 복잡해보여서 절망했었다.

  하지만 차근차근 생각하다보니 결국은 풀었고 끝까지 포기하지 말고 푸는게 중요하다는 것을 다시 한 번 느꼈다.

  코드포스 결과

  

  Read All

  ---

• 코드포스 Codeforces #536(Div.2) 리뷰

  2019-02-01

  booknu

  PS_Codeforces

  PS  Codeforces  구현  그리디  그래프  MST  DP  Math
  • 개요
  • A번
  • B번
  • C번
  • D번
  • E번
  • 후기

  개요

  이번 코포는 시작하기 전 부터 서버가 불안불안 하더니만 결국 채점 큐에 들어간 문제가 40분 가까이 채점되지 않아 Unrated가 돼 버리고 말았다..;

  

  문제 자체들은 쉬운 편이었고, F번 또한 오래 생각해보면 풀릴 것 같았지만, Unrated 라는 소식에 도전은 안 해봤다.

  A번

  A번 문제: 구현

  언제나 그렇듯 A, B번 문제는 풀만하다.

  단순한 구현 문제로, .과 X로 이루어진 맵이 주어지는데, 여기서 다음과 같은 형태가 몇 번이나 나오는지 구하는 문제이다.

  X.X
  .X.
  X.X
  

  풀이 보기

  흔하게 나오는 맵에서의 상하좌우 4방향 방문과 같이 dy, dx를 정의해놓고 구현을 하면 편하다.

  단, 이 문제의 경우에는 모양이 다르기 때문에 dy = { -1, -1, 1, 1 }, dx = { -1, 1, -1, 1 }로 정의하면 된다.

  그러고 난 후 X가 등장하는 곳마다 4방향 모두가 X이면 카운트를 해가면 된다.

  시간복잡도: $O(n^2)$

  소스코드 보기

  include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 500;
  const int dy[4] = { -1, -1, 1, 1 }, dx[4] = { -1, 1, -1, 1 };
  int n;
  string g[MAXN];
  void input() {
  	cin >> n;
  	FOR(i, 0, n) cin >> g[i];
  }
  
  int solve() {
  	int cc = 0;
  	FOR(i, 0, n) {
  		FOR(j, 0, n) {
  			if(g[i][j] == 'X') {
  				bool ok = true;
  				FOR(dir, 0, 4) {
  					int y = i + dy[dir], x = j + dx[dir];
  					if(!(0 <= y && y < n && 0 <= x && x < n && g[y][x] == 'X')) { ok = false; break; }
  				}
  				if(ok) ++cc;
  			}
  		}
  	}
  	cout << cc << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  B번

  B번 문제: 구현 map

  문제가 장황하게 길어 해석하는게 문제인 문제이다.

  게다가 자세하게 읽지 않으면 지나칠 수 있는 문장도 있으니 주의해야 한다.

  레스토랑이 있는데, 거기에는 $n$종류의 음식이 있고 $m$명의 손님이 음식을 먹으려고 일렬로 대기중이다.

  음식은 각각 $a_{1..n}$개 만큼 있고, $c_{1..n}$원의 가격에 판매하고 있다.

  손님들은 온 순서대로 차례로 음식을 먹는데, 다음 과정에 따라 음식을 가져가게 된다.

  현재 손님 $i$는 처음으로 먹을 음식 $t_i$와 먹을 음식들의 개수 $d_i$ 정보를 가지고 있다.

  이 손님이 현재 먹을 음식이 $j$라고 할 때 다음의 과정에 따라 총 $d_i$개의 음식을 먹으려고 한다.

  1. 음식 $j$가 남아있는 경우 해당 음식을 먹는다.
  2. 음식 $j$가 남아있지 않은 경우, 남아있는 음식들 중 가장 싼 음식을 고르고, 가격이 같은 것이 있을 경우 index가 가장 작은 것을 고른다.
  3. 손님이 $d_i$개의 음식을 다 먹지 못했는데 모든 음식이 다 떨어졌을 경우, 손님은 화가 나기 때문에 해당 손님에게서는 돈을 아예 받을 수 없다 (0원)

  위 과정을 반복할 때 각 손님에게서 얼마의 돈을 받을 수 있을지 계산하는 문제이다.

  풀이 보기

  고려해야 할 것이 조금 있는 구현문제이다.

  음식 $j$를 다 먹은 뒤 2번 조건에 맞는 다음 음식을 빠르게 구하는 것이 문제인데, 이것은 map<ii, int>를 사용하면 key값에 따라 정렬된 결과가 유지되기 때문에 쉽게 해결할 수 있다.

  여기서 map에는 mp[{cost, index}] = remain과 같은 정보를 저장하면 된다.

  또 한가지 주의해야 할 점은 3번 조건에서 해당 손님이 음식을 먹기는 먹었지만 원하는 만큼 못 먹어 돈을 못 받는 경우에 대한 예외처리를 해야한다는 것이다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e5;
  int n, q, r[MAXN], c[MAXN];
  map<ii, int> mp;
  void input() {
  	cin >> n >> q;
  	FOR(i, 0, n) cin >> r[i];
  	FOR(i, 0, n) cin >> c[i], mp[{c[i], i}] = r[i];
  }
  
  int useitem(int idx, int val) {
  	int us = min(val, r[idx]);
  	r[idx] -= us;
  	if(r[idx] == 0) mp.erase({ c[idx], idx });
  	else mp[{c[idx], idx}] -= us;
  	return us;
  }
  
  int solve() {
  	while(q--) {
  		int cur, rem;
  		cin >> cur >> rem;
  		--cur;
  		i64 tot = 0;
  		while(rem) {
  			int us = useitem(cur, rem);
  			rem = rem - us;
  			tot += 1ll * us * c[cur];
  			if(mp.size()) {
  				cur = mp.begin()->first.second;
  			} else if(rem != 0) {
  				tot = 0;
  				break;
  			}
  		}
  		cout << tot << ENDL;
  	}
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  C번

  C번 문제: 그리디 math

  짝수 개의 원소를 가진 배열이 주어지는데, 이 배열에서 원소들을 2개 이상의 원소를 가진 그룹들로 그루핑해서 각 그룹 원소의 합의 제곱의 합이 가장 작아지는 경우를 찾는 문제이다.

  즉, $m$개의 그룹으로 그루핑을 했다고 가정하고, 그룹 $j$의 원소 합을 $s_j$라고 할 때 다음을 최소화 하면 된다.

  $$\sum_{j=1}^{m}s_j^2$$

  풀이 보기

  우선 다음을 생각해보자.

  $a$, $b$, $c$ 세 개의 양의 정수가 있는데 $a^2 + b^2 + c^2$이 더 작을까 아니면 $(a+b)^2 + c^2$이 더 작을까?

  당연하게도 식을 전개해보면 전자가 작을 수 밖에 없다는 것을 알 수 있다.

  이것을 통해 우리는 최대한 그룹의 크기를 작게 해서 그루핑 하는게 무조건 이득이라는 것을 알 수 있다.

  이 문제에서는 각 그룹의 원소의 수가 최소 2개는 되어야 하고, 배열의 원소는 짝수개이니까 무조건 2개씩 그루핑을 하면 된다.

  그렇다면 어떤 수끼리 짝을 지어줘야 할까?

  $(a + b)^2 = a^2 + b^2 + 2ab$ 이므로, $a^2 + b^2$부분은 어떻게 짝을 짓던 결국 최종 합은 똑같은 값이 나올 것이고 문제는 $ab$의 값을 최소화 하는 것이다.

  간단하게 생각해보면 배열에서 남은 수들 중 가장 작은 수와 가장 큰 수를 매칭해나가는 것을 반복하면 그것이 최소값이라는 것을 알 수 있다.

  정확한 증명은 $a < b < c < d$ 네 수가 있는데 $a \cdot d + b \cdot c > a \cdot b + c \cdot d$ 혹은 $a \cdot d + b \cdot c > a \cdot c + b \cdot d$ 인 경우가 있을까에 대해 생각해보면 된다.

  소스코드 보기

  생각 없이 multiset을 써버렸는데, 사실 그냥 sort해서 푸는게 편하다.

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 3e5;
  int n, ar[MAXN];
  multiset<int> ms;
  void input() {
  	cin >> n;
  	FOR(i, 0, n) cin >> ar[i];
  }
  
  int solve() {
  	FOR(i, 0, n) ms.insert(ar[i]);
  	i64 ans = 0;
  	FOR(i, 0, n/2) {
  		int ss = (*ms.begin()) + (*(--ms.end()));
  		debug(ss);
  		ms.erase(ms.begin());
  		ms.erase(--ms.end());
  		ans += 1ll * ss * ss;
  	}
  	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  D번

  D번 문제: 그래프 MST

  정점이 $10^5$개 정도 되는 연결 무향 그래프가 주어지고, 각 정점은 $1..n$의 index를 가지고 있다.

  이 때, 1번 정점에서 출발하여 그래프의 모든 정점들을 방문할 때, 새로 방문한 정점들의 수열이 사전순으로 가장 앞서는 경우를 찾는 문제이다.

  즉, 방문했던 정점을 또 방문할 수 있고, 새로운 정점을 만날 때만 수열에 기록할 때 사전순으로 가장 작은 수열을 찾는 것이다.

  풀이 보기

  Prim MST문제라는 것을 빨리 알아차리는게 중요한데, 방문의 형태가 “지금까지 방문한 정점들 (연결된 트리)”에 연결된 정점들 중 index가 가장 작은 것을 찾아 해당 정점을 트리에 넣는 식이라는 것을 보면 MST 문제라는 것을 쉽게 알 수 있다.

  prim과 비슷한 형태로 구현하면 된다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const int MAXN = 1e5+10;
  int n, m, vis[MAXN];
  vi g[MAXN];
  set<int> rem;
  void input() {
  	cin >> n >> m;
  	while(m--) {
  		int u, v; cin >> u >> v;
  		g[u].pb(v), g[v].pb(u);
  	}
  }
  
  int solve() {
  	rem.insert(1);
  	while(rem.size()) {
  		int u = *rem.begin();
  		rem.erase(u);
  		vis[u] = 1;
  		cout << u << ' ';
  		for(int v : g[u]) {
  			if(!vis[v]) rem.insert(v);
  		}
  	}
  	cout << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  처음에는 별 생각 없이 일반적으로 dfs하며 현재 정점에 연결된 새로운 정점 중 index가 가장 작은 것으로 가보는 방식으로 구현했는데, 나중에 보니 3-1-2-4의 경우 예외가 있다는걸 알았다.

  사실 제출 할 때부터 뭔가 예외가 있을 것 같은 불안감이 있었지만 무시하고 제출했었는데, 이 덕분에 틀린 패널티 + 채점 될 때까지의 시간 40분 패널티를 받아버려 등수가 많이 내려갔다..

  틀린걸 알고 AC를 받을 때까지 시간은 별로 안 걸렸지만 여러모로 아쉬운 문제였다.

  E번

  E번 문제: DP multiset

  $[1..n]$의 각 좌표가 정수화 된 시간 속에서 주어진 루틴에 따라 $k$개의 동전을 주워가는데, 최대 $m$번의 방해를 할 수 있을 때 최적으로 방해할 경우 얻을 수 있는 최소 동전 가치를 구하는 문제이다.

  각 동전 $i$는 주울 수 있는 시간의 구간 $[s_i..e_i]$이 존재하고, 이 동전을 주울 경우 $d_i$까지는 아무런 행동도 하지 못하며, $c_i$의 가치를 가지고 있다.

  동전을 주울 때는 현재 주울 수 있는 동전 중 다음과 같은 우선순위에 따라 줍게 된다.

  1. 동전의 가치 c_i가 큰 순으로 줍는다.
  2. c_i가 같을 경우 d_i가 큰 순으로 줍는다.
  3. 나머지 경우는 랜던하게 줍는다.

  이 때 방해라는 개념은 현재 시간 $t$에 방해를 할 경우 $t$에는 아무런 행동도 하지 못하며 $[t+1..]$에서부터 행동을 할 수 있다.

  또한 $e_i \leq d_i$라는 조건이 항상 성립한다.

  풀이 보기

  먼저 인지해야 할 점은, 시간의 범위가 $[1..10^5]$이고, 방해 횟수도 $[1..200]$으로 상당히 작다는 것이다.

  이것만 봐서는 DP의 냄새가 나는데, 좀 더 생각해봐야 한다.

  만약 DP로 해결할 경우 상태공간은 어떻게 되는걸까?

  현재 시간 $t$와 현재까지 방해한 횟수 $m$에 대한 정보는 당연히 필요할 것이다.

  하지만, 이전 시간에 방해를 어떻게 했느냐에 따라서 현재 주울 수 있는 동전들이 달라질텐데 이 정보를 모두 상태공간에 넣어버리면 $2^{200}$이 되어버리는데 과연 이 정보가 필요할까?

  조금만 생각해보면 아니라는 것을 알 수 있다.

  각 시간 $t$에서 주울 수 있는 동전들은 현재 방해 횟수 $m$이나 이전 방해 정보에 영향을 받지 않는다!

  $s_i \leq t \leq e_i$인 동전들은 무조건 $t$ 시간에 주울 수 있다.

  이것이 가능한 이유는, 만약 동전 $i$를 줍는 행동을 할 경우 다음 행동 할 수 있는 시간은 $d_i+1$부터일 것이며, $e_i \leq d_i$라는 조건 덕분에 $e_j$가 $d_i$보다 작은 동전들 $j$는 어차피 $[d_i+1..]$부터는 줍지 못할 것이다.

  또한 주울 수 있는 동전이 있는데 줍지 않는 경우는 방해를 받았을 때 뿐인데, 그 경우는 단순히 $t$가 $t+1$이 될 뿐이므로 주울 수 있는 동전에 대한 정보는 변하지 않는다.

  이것을 이용해 DP식을 세우면 현재 시간을 $t$, 현재 사용한 방해 횟수를 $m$이라 할 때

  현재 주울 수 있는 동전이 없을 때

  $$dp[t+1][m] = min(dp[t+1][m], dp[t][m])$$

  방해를 할 때

  $$dp[t+1][m+1] = min(dp[t+1][m+1], dp[t][m])$$

  방해하지 않고 동전을 주울 때 ($i$ = 현재 주울 동전)

  $$dp[d_i+1][m] = min(dp[d_i+1][m], dp[t][m] + c_i)$$

  현재 $t$에서 주울 수 있는 동전은 multiset을 통해 구현하면 편하다.

  소스코드 보기

  #include <bits/stdc++.h>
  using namespace std;
  
  #ifdef LOCAL_BOOKNU
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #else
  #define debug(...) 42
  #endif
  
  // ........................macro.......................... //
  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  #define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
  #define pb push_back
  #define emb emplace_back
  #define fi first
  #define se second
  #define ENDL '\n'
  #define sz(A) (int)(A).size()
  #define ALL(A) A.begin(), A.end()
  #define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
  #define next next9876
  #define prev prev1234
  typedef pair<int, int> ii;
  typedef pair<int, ii> iii;
  typedef vector<int> vi;
  typedef vector<vi> vvi;
  typedef vector<ii> vii;
  typedef vector<vii> vvii;
  typedef long long i64;
  typedef unsigned long long ui64;
  // inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
  inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
  inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
  inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
  inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
  inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
  inline i64 POW(i64 a, i64 n) {
  	assert(0 <= n);
  	i64 ret;
  	for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
  	return ret;
  }
  template <class T>
  ostream& operator<<(ostream& os, vector<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class T>
  ostream& operator<<(ostream& os, set<T> v) {
  	os << "[";
  	int cnt = 0;
  	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
  	return os << "]";
  }
  template <class L, class R>
  ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
  void debug_out() { cerr << endl; }
  template <typename Head, typename... Tail>
  void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
  // ....................................................... //
  
  const i64 INF = 0x3fffffffffffffff;
  const int MAXN = 1e5+10, MAXM = 2e2+10;
  int n, m, k;
  i64 dp[MAXN][MAXM]; // dp[시간][방해수]
  vii str[MAXN], fin[MAXN]; // edg[s] = e, cost, d;
  multiset<ii> ms;
  void input() {
  	cin >> n >> m >> k;
  	FOR(i, 0, k) {
  		int s, e, d, c; cin >> s >> e >> d >> c; ++d;
  		str[s].pb({ -c, -d });
  		fin[e+1].pb({ -c, -d });
  	}
  }
  
  int solve() {
  	FOR(i, 0, MAXN) FOR(j, 0, m+1) dp[i][j] = INF;
  	dp[0][0] = 0;
  	FOR(t, 0, n+1) {
  		for(ii e : str[t]) ms.insert(e);
  		for(ii e : fin[t]) ms.erase(ms.find(e));
  		FOR(us, 0, m+1) {
  			if(ms.size()) {
  				// 방해 없이 가보기
  				ii sel = *ms.begin();
  				dp[-sel.se][us] = min(dp[-sel.se][us], dp[t][us] + ((i64)-sel.fi));
  				// 방해 하고 가보기
  				if(us < m) dp[t+1][us+1] = min(dp[t+1][us+1], dp[t][us]);
  			} else dp[t+1][us] = min(dp[t+1][us], dp[t][us]);// 아예 먹을게 없어 방해 생각x
  		}
  	}
  	i64 ans = INF;
  	FOR(i, 0, m+1) {
  		ans = min(ans, dp[n+1][i]);
  	}
  	cout << ans << ENDL;
  	return 0;
  }
  
  // ................. main .................. //
  void execute() {
  	input(), solve();
  }
  
  int main(void) {
  #ifdef LOCAL_BOOKNU
  	freopen("input.txt", "r", stdin);
  	// freopen("out.txt", "w", stdout);
  #endif
  	cin.tie(0), ios_base::sync_with_stdio(false);
  	execute();
  	return 0;
  }
  // ......................................... //
  

  후기

  분명 DP식도 잘 세웠고, 범위에 대한 실수도 없었는데 WA가 뜨길래 상당히 당황스러웠다.

  아무리 봐도 맞왜틀이어서 혹시나 multiset의 erase에 문제가 있나 찾아봤더니 erase(x);가 원소 하나만을 지우는 것이 아닌 해당되는 모든 원소를 지우는 것이었다.

  erase(multi_set.find(x));로 바꾸었더니 AC가 뜨긴 떴는데 앞으로 multiset을 쓸 때는 조심해야 할 것 같다.

  

  나와 같은 실수를 한 사람들이 꽤 있었다.

  후기

  D에서 한 번 삽질으로 40분 패널티 받은게 너무 억울했다.

  E번이야 내가 multiset에 대해서 잘 몰라서 시간을 많이 낭비했지만, D번은 순수히 채점 큐가 제대로 돌아가지 않아서 시간을 날린 것이니…

  하지만 무엇보다 억울한 것은 이번에는 꽤나 문제를 잘 풀었는데 Unrated가 된 것이다.

  코포 결과

  Read All

  ---

• 깃 플로우(Git Flow) - 효율적인 GitHub 브랜칭 전략

  2019-01-25

  booknu

  깃허브

  깃허브  버전관리
  • GitHub
  • 개요
  • Git Flow
  • 사용법
    • 시작하기 (init)
    • feature브랜치 사용하기
    • release브랜치 사용하기
    • 기타
  • 링크

  우아한 형제들 기술 블로그, Huns.me 등을 참조하여 작성된 글입니다.

  또한 Git과 GitFlow에 대해 알아가는 와중에 쓴 글이기 때문에 틀린 부분이 있을 수 있습니다.

  GitHub

  GitHub는 오픈소스와 여러가지 프로젝트를 위한 협업, 코드 관리를 도와주는 편리한 플랫폼이다.

  현재 공동으로 진행하는 프로젝트는 없지만, 예전에 GitHub를 사용하지 않았을 때 랩탑과 PC에서 번갈아가며 수정하던 프로젝트를 관리하기가 힘들었던 기억이 있다.

  하지만 GitHub를 사용하기 시작하면서 push와 pull만 제대로 해주면 이런 문제점들이 없어졌다.

  또한 진행하다가 버린 프로젝트나 오랫동안 쓰지 않던 프로젝트를 찾을 때도 GitHub로 프로젝트를 관리한다면 쉽게 찾을 수 있다는 것이 마음에 들었다.

  개요

  GitFlow는 Git에서 소프트웨어의 소스코드와 버전을 효율적으로 관리하기 위한 브랜칭 관리 전략이다.

  이것은 꽤나 오래된 전략이며, 현재까지 발견된 단점을 극복하기 위해 Github Flow와 Gitlab Flow 전략이 나왔다.

  결국에 이름은 거창하지만, Git에서 제공하는 브랜칭 기능을 어떻게 효율적으로 사용할지에 대한 지침도라고 볼 수 있다.

  Git Flow

  GitFlow에는 아래 5가지의 브랜치가 존재한다.

  이 브랜치들은 크게 2개로 나뉘는데, 항상 유지되는 메인 브랜치(master, develop)와 일정 기간에만 유지되는 보조 브랜치(feature, release, hotfix)가 있다.

  • master : 실제 제품으로 출시 가능
  • develop : 다음 출시 버전 개발
  • feature : 기능 개발
  • release : 이번 출시 버전 QA
  • hotfix : 출시 버전에서 발생한 버그를 수정

  

  이 그림을 위에서부터 천천히 살펴보면, 일단 처음에는 master와 develop 브랜치가 존재한다.

  develop에는 hotfix에서 상시로 버그를 픽스한 커밋이 추가된다.

  feature에서는 새로운 기능을 개발할 경우 develop에서 브랜치를 생성한다.

  따라서 feature은 언제나 develop에서 시작하게 된다.

  feature에서 개발되던 기능이 완성되었다면 develop으로 다시 merge 되게 된다.

  develop에 이번 버전에 필요한 모든 기능이 merge 되었다면 오류를 검증하기 위해 release를 생성하고 검증이 완료되었다면 정식 버전으로 출시하기 위해 develop과 master에 merge를 한다.

  즉, master은 실제 출시된 버전이고, develop에서는 다음 버전을 위한 개발이 진행되고, 그것에 필요한 각각의 기능은 feature에서 개발되며, hotfix는 이미 출시된 버전에서 발생한 버그를 픽스하여 현재 개발중인 develop과 현재 출시된 master에 제출하는 역할이고, release는 다음 버전에 대한 기능이 모두 추가되었을 때 실제로 출시하기 전 QA를 위한 브랜치인 것이다.

  사용법

  GitFlow설치법은 이 링크에 나와있다.

  Window의 경우 Git Bash를 사용한다는 가정 하에 아래 명령어를 통해 gitflow를 clone해오면 된다.

  git clone –recursive git://github.com/nvie/gitflow.git

  시작하기 (init)

  GitFlow를 적용할 repo에서 다음 명령어를 입력하면 위에서 말한 5개의 브랜치와 거기에 추가적으로 support라는 브랜치를 사용할 수 있는데, 이것은 버전 호환성 문제 처리를 위한 브랜치이다.

  git flow init

  명령어를 입력하면 메인 브랜치의 이름을 입력하라는 메세지와 보조 브랜치들의 이름을 입력하라는 메세지가 나오는데 아무것도 입력하지 않고 엔터를 누르면 기본값으로 정해진다.

  만약 모두 기본값으로 설정하고 싶다면 -d 옵션을 붙이면 된다.

  git flow init -d

  

  초기화를 완료하면 master 외에 develop가 생긴다.

  

  feature브랜치 사용하기

  기본적으로 생성된 브랜치는 master, develop 두 개 뿐이고 새로운 기능 개발을 위해 feature이 필요하면 다음 명령어를 통해 만들어야 한다.

  그리고 이 feature브랜치는 위에서 설명했듯이 항상 현재 develop을 기반으로 생성된다.

  git flow feature start <“branch name”>

  

  이 feature에서 새로운 기능 개발을 완료했다고 가정하고 이것을 GitFlow에 알려주면 GitFlow는 다음과 같은 행동을 한다.

  • develop로 checkout 한 후,
  • feature을 develop로 merge하고,
  • 작업이 끝난 feature을 삭제한다.

  git flow feature finish <“branch name”>

  

  release브랜치 사용하기

  release역시 비슷하다.

  단, release는 이번 출시될 버전을 위한 QA가 목적일 뿐이다.

  release브랜치 역시 현재 develop를 기반으로 생성된다.

  git flow release start <“branch name”>

  QA가 끝난 후 실제로 출시를 하기 위해 release finish를 요청하면 다음과 같은 작업을 한다.

  • release를 master에 merge
  • release 이름으로 태그 등록
  • release를 develop에 back-merge(재병합)
  • release 삭제

  이렇게 하면 모든 release 준비가 끝났으므로 pull 요청으로 remote repo에 코드를 제출하면 된다.

  기타

  이 밖에도 hotfix, feature/release 별로 pull/push를 할 수 있다.

  git flow hotfix git flow hotfix start <release>[<base>] git flow gotfix finish <release> git flow feature publish <name> git flow feature pull <remote> <name>

  링크

  git-flow cheatsheet

  우아한 형제들 기술 블로그

  Huns.me

  Read All

  ---

• 오일러의 체 - 빠른 소인수분해, 소수 찾기

  2019-01-17

  booknu

  알고리즘_Math

  알고리즘  Math  PS  소수  소인수  에라토스테네스
  • 에라토스테네스의 체
  • 오일러의 체의 경우는?
  • 어떻게 줄여야 할까?
  • spf는 어떻게 구해야 할까?
  • 코드
  • 시간복잡도 분석
  • spf를 이용한 소인수분해
  • 관련 문제

  에라토스테네스의 체

  일정 범위 내의 소수를 찾는 가장 보편적인 방법은 에라토스테네스의 체이다.

  에라토스테네스의 체에 대해 간략히 설명하자면, 기본적으로 2는 소수로 처리해놓고 [2..Range)를 순회하며 소수인 것들의 배수들에 대해 not prime으로 만들며 반복하는 알고리즘이다.

  const int RANGE = 1e7;
  int np[RANGE]; // np[x] = x가 not prime인지?
  void getEratosthenes() {
      for(int i = 2; i*i < RANGE; ++i) {
          if(!np[i]) {
              for(int j = i*i; j < RANGE; j += i) {
                  np[j] = 1;
              }
          }
      }
  }
  

  소수들의 배수들에 대해 not prime으로 처리 할 때 i*i에서부터 시작한다는 최적화를 했지만, 결국 중복되는 수에 대해 not prime으로 처리하는 경우가 생긴다.

  그 예로 $30=2\cdot3\cdot5$에서 $i=2$일 때 $2\cdot15$에서 $30$을 not prime 처리하고, $i=3$일 때 $30$을 중복으로 not prime 처리하게 된다.

  이로 인해 총 시간복잡도는 $O(n\log{\log{n}})$이 된다. 증명

  오일러의 체의 경우는?

  에라토스테네스의 체도 충분히 빠르고 간편한데 이보다 더 최적화를 할 수 있을까?

  놀랍게도 오일러의 체를 사용하면 $O(n)$만에 소수들을 구할 수 있다.

  또한 이 알고리즘은 구현을 위해 각 수의 minimum prime factor(최소 소인수 = spf)를 구하기 때문에 $O(\log{n})$만에 범위 내의 수를 소인수분해 할 수 있다.

  어떻게 줄여야 할까?

  에라토스테네스의 체에서 중복이 나오는 경우를 잘 살펴보면 소수의 배수들에 대해 not prime 처리를 하는 부분에서 소수 * 합성수형태인 경우 중복된다는 것을 알 수 있다.

  이것을 뒤집어서 생각해 “그냥 수 * 소수에 대해 not prime 처리를 하면 안 될까?” 라는 발상을 해볼 수 있다.

  그냥 소수를 곱해버리면 소인수가 3개 이상인 경우에는 또 중복이 나올 게 뻔하니까 모든 수는 $x = spf * number$와 같은 구조로 되어 있음을 이용해 수 * spf인 경우에만 not prime을 처리하면 중복을 피할 수 있다는 아이디어가 나온다.

  spf는 어떻게 구해야 할까?

  $x = number * spf(x)$인 x들에 대해 not prime을 처리하는 것은 에라토스테네스의 체와 비슷한 로직으로 생각하면 편하다.

  대략적인 알고리즘은 다음과 같다.

  일단 수들을 에라토스테네스의 체와 비슷하게 [2..RANGE)를 순회하며 그들의 spf배들에 대해 not prime을 칠한다.

  순회 중 현재 not prime이 칠해지지 않은 수들은 소수임이 자명하다.

  not prime을 칠할 때는 boolean 배열을 통해 칠하지 말고 해당 수의 spf를 저장하는 식으로 구현해 각 수의 spf를 저장해준다.

  이 때 문제가 현재 순회중인 수가 $x$라고 했을 때 $y = x*spf(y)$를 not prime으로 칠할 때 $spf(y)$가 어떻게 $y$의 $spf$인지 알고 칠하냐는 것이다.

  상식적으로 생각하면 쉬운 문제인데, 현재 $x$에 대해 $y$가 될 수 있는 $spf(y)$를 고르는 조건은 아래 두 가지를 만족시키면 된다.

  1. 소수여야한다.
  2. $spf(y) \leq spf(x)$

  즉, 현재까지 구해진 소수들을 $x$에 곱해가며 $y$를 칠해가는데, 소수가 $x$보다 커지면 루프를 끊는 식으로 구현하면 된다.

  코드

  #define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
  const int RANGE = 1e7;
  int pn, spf[RANGE], pr[RANGE];
  void eulerSieve() {
  	FOR(x, 2, RANGE) {
          if(!spf[x]) spf[x] = pr[pn++] = x;	// 현재 x에 대해 spf가 정해지지 않았다는 것은 spf[x] = x라는 의미이고, x가 소수라는 의미이다.
          for(int j = 0; x*pr[j] < RANGE; ++j) { 
              spf[x*pr[j]] = pr[j]; // 수 * spf들에 대해 spf[x*spf] = spf로 칠해준다.
              if(x % pr[j] == 0) break; // spf[x] == pr[j]이면 그만 둔다. (이 이상 pr이 늘어나면 x * pr에 대해 더 이상 spf가 pr이 아닌 x의 spf이니까)
          }
      }
  }
  

  시간복잡도 분석

  분석이라고 할 것도 없이 어떤 합성수 $y = x * spf(y)$를 not prime이라고 칠할 때 가능한 x는 딱 한 가지이므로 무조건 한 번 밖에 칠해지지 않는다.

  실제로 $Range = 10^8$에 대해서 not prime이 칠해지는 경우를 세어보면 다음과 같다.

  Euler’s Sieve: 94,238,543회

  Eratosthenes’s Sieve: 242,570,202회

  spf를 이용한 소인수분해

  spf[x]자체가 x의 소인수를 담고 있기 때문에 단순히 구현만 하면 된다.

  x의 소인수개수 만큼 순회하기 때문에 시간복잡도는 $O(n)$이다.

  const int RANGE = 1e7;
  int spf[RANGE];
  void f(int x) {
      assert(x > 0);
      while(x > 1) {
          cout << spf[x] << ' ';
          x /= spf[x];
      }
  }
  

  관련 문제

  CF-1047C

  코드포스 Div2-C 문제이다.

  이 문제를 통해서 오일러의 체에 대해서 알게 되었는데, 일반적인 에라토스테네스의 체나 소인수 분해를 사용하면 시간초과가 나는 문제이다.

  $n$개의 숫자들이 주어지는데, 이 중 몇 개를 지워야 원래 숫자들의 $gcd$보다 남은 숫자들의 $gcd$가 커질까?

  $(2 \leq n \leq 3 \cdot 10^5)$, $(1 \leq {a_i} \leq 1.5 \cdot 10^7)$

  $gcd$란 모든 숫자들의 공통 인수 중 가장 큰 것이다.

  따라서 모든 수들을 $gcd$로 나누고 난 나머지 수들의 공통 소인수는 없을 것이고, 몇 개의 수를 지워 공통 소인수를 만드는 순간 $gcd$가 증가하게 될 것이다.

  즉, 모든 수들을 소인수분해해서 cnt[x]배열에 각 소인수가 몇 번 등장했는지를 세고, $n - max(cnt[x])$를 구해주면 된다.

  이 때 소인수분해를 일반적인 방법으로 해서는 $n = 3 \cdot 10^5$이고, 수의 범위 ${a_i} = 1.5 \cdot 10^7$이기 때문에 시간 초과가 난다.

  실제로 $x$를 소인수분해 할 때 $\sqrt{x}$까지의 소수들로 나눠보는 방법을 사용해봤지만 시간초과가 났다.

  하지만 위에서 설명한 오일러의 체를 사용하면 $O(A + n \cdot \log{A})$ 만에 문제를 해결 할 수 있다.

  Read All

  ---