개요
전반적으로 난이도가 쉬웠다고 생각한다. E번 마저도 입맛대로 결과를 출력해도 돼서 큰 어려움은 없었다.
A번
A번 문제: 그리디
$n$개의 원소를 가진 배열이 주어지고, 각 배열의 원소를 $0$이 아닌 $[-1000..1000]$사이의 정수 $d$로 나누었을 때 양수(꼭 정수가 아니어도 됨.)의 개수가 $\lceil \frac{n}{2} \rceil$개가 되는 $d$ 중 아무거나 출력하면 된다.
만약 그런 $d$가 없다면 $0$을 출력한다.
풀이 보기
만약 해당되는 $d$가 존재한다면 $d$는 $-1$ 혹은 $1$일 것이다.
즉, 배열에 양수가 $\lceil \frac{n}{2} \rceil$보다 많다면 $d = 1$이고, 음수가 많다면 $d = -1$이다.
만약 두 경우 모두 존재하지 않으면 $0$이다.
소스코드 보기
#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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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 = 100;
int n, ar[MAXN];
void input() {
cin >> n;
FOR(i, 0, n) cin >> ar[i];
}
int solve() {
int h = n/2 + n%2, cnt = 0, cc = 0;;
FOR(i, 0, n) {
if(ar[i] > 0) {
++cnt;
}
if(ar[i] < 0) {
++cc;
}
}
if(cnt >= h) cout << 1 << ENDL;
else if(cc >= h) cout << -1 << ENDL;
else cout << 0 << 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$가 음수도 될 수 있는지 몰라서 양수만 체크했다가 틀렸다.
다시 음수도 체크했는데, 실수로 두 가지 경우 모두 $1$로 출력해서 또 틀렸다.
이것 때문에 많은 시간과 점수를 날려먹었다.
B번
B번 문제: DP 그리디
두 사람이 각각 $n$층의 케이크를 만들려고 하고 있다.
각 케이크는 점점 아래층이 커지는 구조로 쌓여야 한다. (어찌 됐던 결국 $[1..n]$순서로 층을 쌓아야 한다.)
$2 \cdot n$개의 케이크 가게가 있는데, 각 케이크 가게는 $[1..n]$층 중 하나를 팔고 있으며, 모든 케이크 가게에서 각 케이크 층은 딱 2번씩 등장한다.
두 사람은 모두 가장 왼쪽에서 재료 모으기를 시작하고, 케이크 가게 사이의 거리는 $1$일 때, 두 사람 모두 케이크를 완성하기 위해 움직여야 하는 움직임의 수의 합의 최소값을 구해야 한다.
풀이 보기
DP 풀이
$dp[i][j]$ = 두 사람이 케이크의 $i$층까지 완성했고, 그 중 첫 번째 사람이 두 케이크 집 중 $j$에 방문중인 상태일 때 최소값
이 때 $j \oplus 1$의 의미는 $j$와 다른 것을 의미한다.
그리디 풀이
위의 DP풀이를 자세히 보면, 결국 이전 상태에서 그리디한 선택만을 가져간다는 것을 알 수 있다.
즉, 이전 상태의 두 케이크 집에서 갈 현재 상태의 두 케이크 집을 거리의 합이 작은 쪽으로 골라서 간다는 것이다.
어찌됐든 두 명 모두 $n$층의 케이크를 완성해야 하고, 현재 있는 집의 위치는 어차피 각각 둘 중 하나이니까 이렇게 그리디하게 생각해도 된다.
소스코드 보기 (DP)
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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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, ar[MAXN*2];
vi pos[MAXN];
i64 dp[MAXN][2];
void input() {
cin >> n;
FOR(i, 0, 2*n) cin >> ar[i], --ar[i], pos[ar[i]].pb(i);
}
int solve() {
dp[0][0] = dp[0][1] = pos[0][0] + pos[0][1];
FOR(i, 1, n) {
FOR(j, 0, 2) {
dp[i][j] = 0x7fffffffffffffff;
FOR(k, 0, 2) {
dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(pos[i-1][k] - pos[i][j]) + abs(pos[i-1][k^1] - pos[i][j^1]));
}
}
}
FOR(i, 0, n) debug(dp[i][0], dp[i][1]);
cout << min(dp[n-1][0], dp[n-1][1]) << 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번부터 DP스러운게 나와서 상당히 당황스러웠다.
뭔가 그리디한 방법이 있을 것 같다는 생각이 들었지만, 그걸 생각하는 것보다 DP식을 구현하는게 더 빠르다고 판단했다.
DP식을 짜다 보니 결국 전이 상태에서 그리디한 방법이 있다는 것을 알았지만, 이미 DP를 짜버려서 그냥 제출했다.
C번
C번 문제: 그래프 BruteForce
$n \cdot m$크기의 갈 수 있는 곳과 갈 수 없는 곳으로 이루어진 맵이 주어진다.
임의의 두 갈 수 있는 곳을 터널을 뚫어 연결 할 수 있다고 할 때, 시작점에서 출발해 끝 점에 도착하기 위해 필요한 터널의 최소 cost를 구해야 한다.
단, 터널은 단 1번만 뚫을 수 있으며, 그냥 움직일 때는 상하좌우로 움직일 수 있고, cost가 필요하지 않다
두 지점 $(y_s, x_s)$, $(y_e, x_e)$를 잇는 터널을 뚫는 비용은 $(y_s-y_e)^2 + (x_s-x_e)^2$이다.
풀이 보기
맵의 크기가 크지 않기 때문에 단순하게 생각하면 편하다.
시작 점이 속한 컴포넌트와 끝 점이 속한 컴포넌트를 구한다.
만약 두 컴포넌트가 같다면 터널이 필요하지 않아서 답은 0이다.
서로 다른 컴포넌트라면 모든 정점 쌍에 대해 터널을 뚫어보는 방식으로 최소값을 구하면 된다.
소스코드 보기
#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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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 = 50;
const int dy[4] = { 0, 0, -1, 1 }, dx[4] = { -1, 1, 0, 0 };
int n, vis[MAXN][MAXN];
ii str, fin;
vii ar, br;
string g[MAXN];
void input() {
cin >> n >> str.first >> str.second >> fin.first >> fin.second;
FOR(i, 0, n) cin >> g[i];
}
void f(int y, int x, vii& lis) {
lis.pb({ y, x });
vis[y][x] = 1;
FOR(dir, 0, 4) {
int ny = y + dy[dir], nx = x + dx[dir];
if(0 <= ny && ny < n && 0 <= nx && nx < n && g[ny][nx] == '0' && !vis[ny][nx]) {
f(ny, nx, lis);
}
}
}
i64 dis(ii& s, ii& e) {
i64 a = s.first, b = s.second, c = e.first, d = e.second;
return (a-c)*(a-c) + (b-d)*(b-d);
}
int solve() {
--str.first, --str.second, --fin.first, --fin.second;
f(str.first, str.second, ar);
if(vis[fin.first][fin.second]) {
cout << 0 << ENDL;
return 0;
}
i64 ans = 0x7fffffffffffffff;
f(fin.first, fin.se, br);
FOR(i, 0, ar.size()) {
FOR(j, 0, br.size()) {
ans = min(ans, dis(ar[i], br[j]));
}
}
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;
}
// ......................................... //
D1번
D1번 문제: BruteForce 그리디
$n$개의 기차역이 원형으로 이어져있다. (즉, $1 \rightarrow 2 \rightarrow … \rightarrow n \rightarrow 1$)
$m$개의 화물을 운반해야 하는데, 각 화물은 시작역과 끝 역으로 이루어져 있으며, 시작역에서 화물을 싣고 끝 역에서 화물을 내려야 한다.
이 때, 기차의 적재량은 무한대이지만, 한 역에서는 1개의 화물 밖에 싣지 못한다.
$n$개의 역 각각에서 기차가 출발했을 때 모든 화물을 나르기 위한 최소 시간을 구해야 한다.
풀이 보기
이 문제는 $n$과 $m$값이 작기 때문에 단순하게 생각해보자.
일단 화물을 내리는 것은 기차에 있는걸 해당 역이 되면 그냥 내려버리면 되기 때문에 신경 쓸 필요가 없는데, 현재 역에 여러 화물이 있을 때 그 중 어떤 화물을 먼저 실을지가 문제다.
직관적으로 생각하면 먼 거리를 가는 화물을 우선적으로 싣는 것이 무조건 이득이라는 것을 알 수 있다.
짧은 거리를 가는 화물을 먼저 실어버리면 어차피 먼 거리를 가는 화물을 실으러 다시 이 역에 와야 하고, 그렇게 되면 먼 거리를 가는 화물이 남는 것이 손해이기 때문이다.
따라서 각 역마다 존재하는 화물들을 거리 역순으로 정렬해두고 시뮬레이팅 하면 된다.
소스코드 보기
#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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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 = 101, MAXM = 201;
int n, m, cur[MAXN];
vi to[MAXN];
void input() {
cin >> n >> m;
FOR(i, 0, m) {
int u, v; cin >> u >> v; --u, --v;
to[u].pb((v+n - u) % n);
}
}
int solve() {
FOR(i, 0, n) sort(ALL(to[i]), greater<int>()), debug(to[i]);
FOR(s, 0, n) {
memset(cur, 0, sizeof(cur));
i64 ans = 0;
int p = s, cnt = 0, rem = 0;
while(cnt != m || rem > 0) {
//FOR(i, 0, n) cout << cur[i] << ' '; cout << ENDL;
--rem;
if(cur[p] < to[p].size()) rem = max(rem, to[p][cur[p]]), ++cnt, ++cur[p]; // 현재에서 태울 수 있는거 태움
++ans;
p = (p+1)%n;
}
cout << ans -1 << ' ';
}
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;
}
// ......................................... //
D2번
D2번 문제: 그리디
D1번 문제에서 $n$, $m$이 증가했다.
풀이 보기
D1의 풀이에서 조금 더 관찰할 수 있는 것이 있다.
왜 하나의 역에서 먼 거리의 화물을 우선적으로 실을까?
바로 화물이 남아 있는 한, 해당 역으로 다시 되돌아와야 하기 때문이다.
이왕 되돌아와야 할 거, 먼 거 먼저 보내버리자는 심보이다.
그렇다면 어차피 다시 역으로 돌아와야 하는데, 이걸 시뮬레이팅 하는 것은 바보짓이 아닌가?
화물이 남아 있는 한 $n$초를 추가하면 될 것을 시뮬레이팅 하는 것은 계산 낭비이다.
이것을 일반화하면 다음과 같다.
각 역에서 열차가 출발 할 때 해당 역의 화물을 모두 배송하는 최소 시간은 $n \cdot (num-1) + shortest$ 이다.
이 때, $num$ = 해당 역의 화물 수, $shortest$ = 해당 역에서 가장 가까운 배송거리
그렇다면 해당 역에서 열차가 출발하지 않는 경우는 어떨까?
출발역에서 해당역까지의 거리를 더해주면 끝이라는 것을 쉽게 알 수 있다.
완전히 식을 일반화 해서 $s$역에서 출발할 때의 최소값을 구하려면 다음을 구하면 된다.
$max(dist(s, i) + n \cdot (num[i]-1) + shortest[i])\ \ \ for\ i = [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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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 = 5001, MAXM = 20001;
i64 n, m, cc[MAXN], to[MAXN]; // cc: i의 총 캔디 수
void input() {
cin >> n >> m;
FOR(i, 0, m) {
int u, v; cin >> u >> v; --u, --v;
if(to[u] == 0) to[u] = (v+n - u) % n;
else to[u] = min(to[u], (v+n - u) % n);
++cc[u];
}
}
int solve() {
//FOR(i, 0, n) debug(cc[i], to[i]);
FOR(s, 0, n) {
i64 ans = 0;
FOR(i, 0, n) {
if(cc[i]) {
//debug(s, i, (i+n-s)%n, (cc[i]-1)*n + to[i]);
ans = max(ans, (i64)(i+n-s)%n + (cc[i]-1)*n + to[i]);;
}
}
cout << ans << ' ';
}
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;
}
// ......................................... //
후기
실수로 D1번의 소스코드를 사용하다가 $n$, $m$범위를 바꾸지 않아 1번의 WA를 받았다.
이렇게 범위만 다른 류의 문제를 풀면 꼭 이런 실수를 하게 되는데, 조심해야겠다.
E번
E번 문제: 그리디 ConstructiveAlgorithms Math
$n$개의 원소를 가진 배열 중, 연속한 원소들에 대해 $\max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i$ 를 찾는 문제가 있다.
(단, $1 \leq n \leq 2,000$ 이고 $abs(a_i) \leq 10^6$)
이 문제를 아래와 같은 코드로 구현했는데, 사실 이 코드는 예외가 존재하는 코드이다.
function find_answer(n, a)
# Assumes n is an integer between 1 and 2000, inclusive
# Assumes a is a list containing n integers: a[0], a[1], ..., a[n-1]
res = 0
cur = 0
k = -1
for i = 0 to i = n-1
cur = cur + a[i]
if cur < 0
cur = 0
k = i
res = max(res, (i-k)*cur)
return res
$1 \leq k \leq 10^9$인 $k$가 주어질 때, 원래의 답과 이 코드의 답의 차이가 $k$가 되도록 하는 테스트케이스를 만들어야 한다.
(단, 테스트 케이스는 위에 명시된 $n$, $a_i$의 기준을 만족해야 한다.)
풀이 보기
우선 소스코드를 분석해보자.
이 코드는 $i = [0..n)$을 순회하며, sum의 시작 구간 $j$를 유지하며 만약 $\sum\limits_{j \leq idx \leq i} a_{idx}$가 음수가 된다면 시작 구간을 $i$로 옮겨버리고, 각 $i$마다 위의 식대로 값을 구한 뒤 그 중 최대값을 취하는 방법을 사용한다.
이 방법은 여러가지 문제점이 있지만, 나는 위의 코드가 선택한 구간 앞의 음수를 포함한 경우가 결과 값이 더 클 수 있다는 것에 주목했다.
즉, $\lbrace -1, 100 \rbrace$이 있을 때 위의 코드는 $100$을 반환하는데, 사실은 답이 $99 \cdot 2 = 198$이라는 것이다.
이것을 이용하면 위의 코드와 정답의 차이를 정확히 $k$로 만들 수 있을 것 같다.
우선 위와 같이 $\lbrace -1, a \rbrace$ 처럼 배열을 구성한다고 생각하면,
코드: $a$
정답: $2 \cdot (a-1)$
$\therefore k = 2 \cdot (a-1) - a = a - 2$
위와 같이 깔끔하게 해당되는 $a$값을 구할 수 있다.
하지만 한 가지 문제점은, $abs(a_i) \leq 10^6$를 만족시키는 배열을 만들어야 한다는 것이다.
따라서 $a$가 너무 커질 경우, 앞에 있는 $-1$을 점점 늘려가는 식으로 생각해보자.
즉, $\lbrace …, -1, -1, a \rbrace$처럼 배열을 구성하는 것이다.
또한 굳이 앞을 $-1$만 쓸 것이 아니라, $0$을 써도 상관 없다는 것을 유념하자.
이것을 통해 식을 세우면
$a$ 앞의 숫자의 개수 = $y$, -($a$ 앞의 숫자의 합) = $x$
코드: $a$
정답: $(y+1) \cdot (a-x) = a \cdot y - x \cdot y + a - x$
$k = (y+1) \cdot (a-x) = a \cdot y - x \cdot y + a - x - a = a \cdot y - x \cdot y - x$
$\therefore a = \frac{k + x}{y} + x$
이 때, $0 \leq x \leq y$를 만족하면서 $(k + x) \equiv 0 \pmod y$이 되는 $x$를 찾으면 되는데, 그것에 해당되는 것이 $x = y - (k \bmod y)$ 이다.
이제 $y = [1..2000)$을 순회하며 $a$가 조건 범위 내로 들어오는 경우에 대해서 출력해주면 된다.
이 방법이 반드시 답을 찾을 수 있는 이유는, 우선 $k$가 어떤 수이든 해당되는 $x$는 반드시 존재하게 된다.
또한 $y$가 점점 늘어감에 따라 단계별로 답과 코드의 차이가 $O(a)$만큼 벌어지게 되므로, $a$는 최대 $10^6$이고 $y$는 최대 $1,999$이므로 $10^9$이하인 $k$에 대해서 항상 조건에 맞는 $a$를 찾을 수 있다.
소스코드 보기
#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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
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 RANGE = 1e6+1;
i64 k;
void input() {
cin >> k;
}
int solve() {
for(i64 y = 1; y < 2000; ++y) {
i64 x = y - (k % y);
i64 res = (k + x*y + x) / y;
debug(y, x, res);
if(res < RANGE) {
cout << y+1 << ENDL;
i64 ans = res;
int p = 0;
while(x < y-p) cout << 0 << ' ', p++;
for(; p < y; ++p) {
cout << -1 << ' ';
}
cout << ans << ENDL;
return 0;
}
}
assert(false);
cout << -1 << 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;
}
// ......................................... //
후기
처음에는 위와 같은 방식으로 접근했다가, 항상 맨 앞부분에 $-1$만을 넣어야 한다고 생각했었다.
(즉, $x = y$라고 생각함.)
따라서 $k \neq 0 \pmod y$인 경우에는 다음 $y$로 넘어가버리게 되서 $k$의 모든 소인수가 $2,000$이 넘어가버리는 경우 답이 존재함에도 불구하고 모든 $y$루프를 돌고 $-1$을 출력해버렸다.
하지만 생각해보니 $-1$뿐 아니라 $0$도 출력할 수 있다는 것을 깨닫고, 이것을 활용하면 $k$의 소인수가 어떻게 됐든 무조건 $y$로 나누어 떨어지게 할 수 있는 방법이 있다는 것을 깨달았다.
이 문제까지 푼 덕분에 꽤 많은 점수가 오를 수 있었다.
후기
컨테스트 시작은 별로 좋지 못했다.
A번에서 문제를 이해하는데 너무 오래걸렸고, 그나마도 조건을 잘못 읽어 2번이나 삽질해버렸다.
B번도 잘 생각했다면 그리디로 빠르게 풀고 넘어갈 수 있었는데, DP로 접근하는 바람에 “B번 문제인데 정말로 DP로 푸는거 맞나?”라는 생각과 DP 검증 때문에 솔브가 늦어졌다.
C번 역시 문제를 제대로 읽지 않고 일반 이동에는 코스트가 없다는 것을 읽지 못해 이상한 코드를 짜다가 늦어버렸다.
D번 부터는 꽤나 잘 풀린 편인데, 우선 D1은 시뮬레이팅 하면서 빠르고 확실하게 풀자고 생각했고, D2같은 경우는 실수로 수의 범위를 바꾸지 않고 제출해서 1번 틀린게 아까웠다.
E번 같은 경우는 처음 생각했던 방법이 방향성이 옳아서 쉽게 풀 수 있었던 것 같다.
다른 방법으로 접근했다면 푸는데 꽤 오래걸렸을텐데, 이걸 생각하면 운이 좋았던 것 같다.
아무튼 결과가 좋고 퍼플을 가게 되어서 상당히 기분 좋은 컨테스트였다.
