세종과학예술영재학교(세과영)에서 4시간 반동안 열리는 SASA 프로그래밍 오픈컨에 참여해보았다.
시간도 마침 괜찮았고, 오랜만에 대회 참여하면서 실력 점검 및 유지해보면 좋을 듯했기 때문이다.
그리고 2솔 이상하면 프로필 뱃지를 준다길래 참여해보았다 ㅎㅎ
대회 내에 풀 수 있는 문제들은 잘 푼 것 같다.
큰 실수로 인하여 풀 수 있는 문제를 놓치는 경우는 존재하지 않은 듯하고, C2번과 H번이 풀릴 듯 말 듯했다. (다행히 다음날에 업솔빙 성공)
문제들이 상당히 재밌었다.
오랜만에 대회를 참여해서 그런진 모르겠는데 정말 재밌게 푼 듯하다.
다만, B번 지문이 이해하기 꽤 어렵게 되어있었고,
2021년 12월 13일 기준, 에디토리얼이 없다는 점은 아쉬웠다.
에디토리얼도 없으니 포스팅에 코드 및 풀이를 간단하게 남겨보도록 하겠다.
다른 분들께 도움이 됐으면 좋겠다.
23825. A - SASA 모형을 만들어보자
SASA 1개의 모형을 만들기 위해서는 S 2개, A 2개가 필요하다.
따라서 S N개, A M개가 있다면, min(N/2, M/2)개의 SASA 모형을 만들 수 있다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
ll N, M;
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
cout << min(N / 2, M / 2);
}
솔직히 이 때 엄청 빨리 제출했어서 '어? 이거 퍼솔... 가능할지도?' 라 생각했었는데,
역시 괴수들은 달랐다... 0분컷했는데도 6등일줄은 몰랐다.
23826. B - 와이파이
사실 문제 이해가 정말 안됐었다.
요약하자면 두번째 줄에 소극장 X0, Y0, E0의 정보가 주어진다.
그리고 세번째 줄부터 방에 대한 정보가 주어진다.
소극장 wifi는 이득, 다른 방들의 wifi는 손해가 될 때, 1번 방부터 N번 방까지 중 가장 이득이 되는 방의 속도를 구하는 문제이다.
N이 1000이기 때문에 브루트포스로 이중for문을 돌아도 충분하다.
따라서 모든 방에서의 속도를 확인해주면 된다.
모든 방에서의 속도가 0 이하일 경우 IMPOSSIBLE을 출력해주자.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, sx, sy, se, ans;
vector<pii> v;
string s;
int dist(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> sx >> sy >> se;
for (int i = 0; i < N; i++) {
int x, y, e;
cin >> x >> y >> e;
v.push_back({ e,{x,y} });
}
for (int i = 0; i < N; i++) {
int x = v[i].second.first;
int y = v[i].second.second;
int d = dist(sx, sy, x, y);
int e = se - d;
for (int j = 0; j < N; j++) {
int nx = v[j].second.first;
int ny = v[j].second.second;
e -= max(0,v[j].first - dist(x, y, nx, ny));
}
ans = max(ans, e);
}
if (ans > 0)
cout << ans;
else
cout << "IMPOSSIBLE";
}당시에 문제가 잘 이해가 안됐어서 다른 문제들을 먼저 풀고 이문제를 해결하였다.
23827. C1 - 수열 (Easy)
N이 50만이기 때문에 이중for문으로 직접 돌리면 시간초과가 난다.
수열 a b c d가 있다고 할 때, 구하는 값은 ab+ac+ad+bc+bd+cd = a(b+c+d) + b(c+d) + c(d) 이므로 누적합을 이용해주면 된다.
따라서 누적합 배열을 p라 할 때, for문으로 현재값*(전체 합 - 현재까지의 합)를 답에 더해주고 1e9+7로 나눠주면 된다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 500011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
ll N, a[MAX], p[MAX], ans;
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
for (int i = 1; i <= N; i++) {
ans += a[i] * (p[N] - p[i]);
ans %= MOD;
}
cout << ans;
}23828. C2 - 수열 (Hard)
(업솔빙)
당시에 O(N*maxAi) 등 시간초과 방법 외에는 해결방법이 잘 안보였는데, 대회가 끝나고 다음날 생각해보니 특정 인덱스까지의 답에 현재 인덱스가 추가될 때
[1. 이전에 길이가 j인 수열들, 2. 이전에 길이가 j-1인 수열 * 현재 인덱스의 값]
두 갈래로 경우가 나뉘므로 점화식을 세워 dp를 이용하면 됐다. N이 1e3이기 때문에 O(N^2)으로 충분하다.
내가 좀 어렵게 푼 것 같기도 한데, 풀이를 적자면 아래와 같다.
dp[i][j]: i번째까지의 원소 중 길이 j 수열까지의 구하려는 값으로 식을 정의하자.
1. dp[i][j]에는 dp[i-1][j]: i-1번째까지의 원소에서 길이 j까지의 구하려는 값이 그대로 들어갈 것이다. 현재 인덱스가 추가됐다고 해서 현재값을 곱해버리면 길이가 j+1이 되기 때문이다.
2. 또한, dp[i][j]에는 dp[i-1][j-1] * 현재값이 들어갈 것이다. 길이 j-1일 때 현재값을 곱한 값이 dp[i][j]에 들어갈 것이기 때문이다.
그러나 이 문제에는 중복이 있다.
따라서 처음 주어지는 수열 A를 정렬한 다음, Ai != Aj (i<j)가 시작될 때의 인덱스 i를 저장해준 후 dp[i][j]에 dp[i-1][j-1]*현재값이 아닌, dp[k][j-1]을 곱해주자. 그래야 k번째 이후 원소값의 중복되는 원소들을 고려하지 않고 답을 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n,m,a[1003],d[1003][1003];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
d[i][1]=(d[i-1][1]+a[i])%mod;
}
for(int j=2;j<=m;j++){
int k=0;
for(int i=2;i<=n;i++){
d[i][j]+=d[i-1][j];
d[i][j]%=mod;
if(a[i]!=a[i-1])k=i-1;
d[i][j]+=(d[k][j-1]*a[i])%mod;
d[i][j]%=mod;
}
}
cout<<d[n][m]%mod;
}개인적으로는 골3 정도라 생각한다.
23829. D - 인문예술탐사주간
자주 봤던 유형의 문제.
이러한 유형을 응용하는 문제들이 꽤 있다. 문제 번호까진 기억이 안나지만 두세문제 정도 풀었던 기억이 있다.
예제 입력 1로 예시를 들어 설명하자면,
1 3 7 9 10 과 같이 나무들이 있고, 4의 위치에서 거리합을 구한다고 해보자.
4의 왼쪽에 있는 나무들은 1, 3 -> (4-1) + (4-3) = 2*(현재위치 - 나무위치)
4의 오른쪽에 있는 나무들은 7, 9, 10 -> (7-4) + (9-4) + (10-4) = 3*(나무위치 - 현재위치)
감이 오는가?
이 문제도 누적합 문제였던 것이다. (출제자 중에 누적합 덕후가 있는게 분명하다..!)
현재 나무가 몇 번째에 있는지 for문으로 확인해주기엔 시간초과날 것이 뻔하므로 lower_bound(이분탐색)로 구해주자.
이후에 (왼쪽에 있는 나무들의 개수 * 현재위치 - 왼쪽나무거리누적합)과, (오른쪽나무거리누적합 - 오른쪽에 있는 나무들의 개수 * 현재위치)를 더해주면 된다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
ll N, Q, a[MAX], p[MAX];
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> a[i];
}
sort(a + 1, a + N + 1);
for (int i = 1; i <= N; i++) {
p[i] = p[i - 1] + a[i];
}
while (Q--) {
ll x;
cin >> x;
ll idx = lower_bound(a + 1, a + N + 1, x) - a;
ll left = p[idx - 1];
ll right = p[N] - p[idx - 1];
cout << x * (idx - 1) - left + right - x * (N - idx + 1) << "\n";
}
}23830. E - 제기차기
K를 정해야 된다. 근데 가능한 최소 K를 구하는 문제다.
그렇다. 결정 문제다. 신나게 파라메트릭 서치를 돌려주면 된다.
근데 함정이 하나 있다.
정답률이 낮은 결정적 이유인데, 문제를 보면 기준이 되는 양의정수 K를 정한다고 돼있다...
0부터 이분탐색을 돌렸다면 96%에서 WA를 받아 맞왜틀을 수없이 많이 외치고 있는 자신을 발견하게 될 것이다... (내가 그랬음 ㅎㅎ)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
ll N, a[MAX], p, q, r, S;
ll solve(ll k) {
ll ret = 0;
for (int i = 0; i < N; i++) {
if (a[i] > k + r)
ret += a[i] - p;
else if (a[i] < k)
ret += a[i] + q;
else
ret += a[i];
}
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
cin >> p >> q >> r >> S;
ll s = 1, e = LNF, ans = -1;
while (s <= e) {
ll mid = (s + e) / 2;
ll sum = solve(mid);
if (sum < S) {
s = mid + 1;
}
else {
ans = mid;
e = mid - 1;
}
}
cout << ans;
}23831. F - 나 퇴사임?
처음에 우선순위큐를 이용한 그리디로 삽질하면서 시간을 날렸다.
일단 그리디가 아닌 이유는 망할 정독실과 소학습실 때문인데, 정독실과 소학습실에서 어떻게 시간을 채우느냐에 따라 답이 달라지기 때문이다. 정독실과 소학습실에서 최대를 뽑아낸다고 해도, 정독/소학습실 적정값 + 다른 방에서 적정값이 더 클 수도 있고, B일을 어떻게 채우느냐에 따라 답이 달라지므로 dp로 접근해야된다.
연속해서 휴게실을 이용할 수 없으므로 현재 어디 방에서 공부했는지의 정보가 필요하다.
또한, A일, B일 조건이 있기 때문에 현재 a일, b일의 정보도 필요하다.
따라서 무려 4차원 dp를 이용해야된다.
탑다운dp를 이용하면 좀 편해진다.
주의할 점은, -INF로 값을 초기화해주지 않으면 첫째날에 자습할 수 없는 곳에서 자습해버리는 값이 답으로 결정돼버린다는 점.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 107;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, A, B, v[MAX][4], d[MAX][MAX][MAX][4];
int dp(int cur, int a, int b, int room) {
if (cur >= N) {
if (a <= A && b >= B) return 0;
return -INF;
}
int& ret = d[cur][a][b][room];
if (ret != -1)
return ret;
ret = -INF;
for (int i = 0; i < 2; i++) {
ret = max(ret, dp(cur + 1, a, b + 1, i) + v[cur][i]);
}
if (room != 2)
ret = max(ret, dp(cur + 1, a, b, 2) + v[cur][2]);
if (a < A)
ret = max(ret, dp(cur + 1, a + 1, b, 3) + v[cur][3]);
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> A >> B;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 4; j++) {
cin >> v[i][j];
}
}
memset(d, -1, sizeof(d));
int ans = 0;
for (int i = 0; i < 4; i++) {
if (i <= 1)
ans = max(ans, dp(1, 0, 1, i)+v[0][i]);
else if (i == 3)
ans = max(ans, dp(1, 1, 0, i)+v[0][i]);
else
ans = max(ans, dp(1, 0, 0, i)+v[0][i]);
}
cout << ans;
}23832. G - 서로소 그래프
서로소를 이루는 순서쌍의 개수를 구하는 문제이다.
이는 오일러 피함수를 이용하면 된다.
오일러 피함수 정의를 알고 있었다면 접근하기 편했을 듯?
오일러 피함수가 아닌 포함배제의 원리를 이용하여 풀 수도 있다고 한다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M;
bool isPrime[MAX];
vector<int> v;
void sieve() {
fill(isPrime, isPrime + MAX, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < MAX; i++) {
if (!isPrime[i])
continue;
for (int j = i * 2; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
int solve(int N) {
int ret = N, n = N;
for (int i = 2; i * i <= N; i++) {
if (n == 1)
break;
if (isPrime[i] && !(n % i)) {
while (!(n % i))
n /= i;
ret /= i;
ret *= (i - 1);
}
}
if (n != 1) {
ret /= n;
ret *= (n - 1);
}
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
sieve();
ll ans = 0;
for (int i = 2; i <= N; i++) {
ans += 1LL * solve(i);
}
cout << ans;
}23833. H - F1ow3rC0n
(업솔빙)
update가 있기 때문에 세그먼트트리 필수!
근데 어떻게 할지 대회 당시에는 감이 안잡혔다.
좀 오래 고민해본 결과, 나무 번호를 세그먼트트리로 처리하지 않고,
본드를 사야 하는 때를 합세그로 처리하는 방법을 떠올렸다.
합세그를 이용하므로 펜윅트리로도 처리할 수 있다.
update를 어떻게 할지 case_work가 조금 있는 편인데,
Ai번째 나무에서 본드를 샀어야 됐었었을 때와 사지 않아도 됐었을 때로 나눠서 생각해야 한다.
그리고 Ai번째 나무가 바뀌면 Ai+1번째 나무에서 본드를 안사도 되는 경우도 존재하기 때문에 case_work를 열심히 해주자.
참고로, Ai가 1이거나 N일 경우에 잘못된 인덱스에 접근하지 않도록 주의하자.
3%에서 틀린다면, Ai번째 나무에선 무조건 본드를 사야한다는 사실을 놓치고 있을 확률이 높다. (내가 그랬음 ㅎㅎㅎ)
#include <bits/stdc++.h>
using namespace std;
int n,q,a[100003],tree[100003];
int query(int i){
int ret=0;
for(;i;i-=i&-i){
ret+=tree[i];
}
return ret;
}
void update(int i,int val){
for(;i<=n;i+=i&-i){
tree[i]+=val;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i==1)update(i,1);
else if(a[i]!=a[i-1])update(i,1);
}
while(q--){
int ch,A,B;
cin>>ch>>A>>B;
if(ch==1){
cout<<query(B)-query(A)+1<<"\n";
}
else{
a[A]=B;
int k=query(A)-query(A-1);
int k2=query(A+1)-query(A);
if(A>1){
if(a[A]==a[A-1]&&k){
update(A,-1);
}
else if(a[A]!=a[A-1]&&!k){
update(A,1);
}
}
if(A<n){
if(a[A]==a[A+1]&&k2){
update(A+1,-1);
}
else if(a[A]!=a[A+1]&&!k2){
update(A+1,1);
}
}
}
}
}23834. I - 커여운 키위
문제를 보지도 못했다.
23835. J1 - 어떤 우유의 배달목록 (Easy)
N과 Q가 작은 버전이라 O(NQ) 풀이도 가능하다.
따라서 전형적인 트리 탐색 DFS 문제.
방을 탐색할 때마다 우유 양이 늘어나므로 depth를 저장해주자.
탐색 가능한 방 중에서, v번 방으로 가는 길이 아닌 방에는 우유를 주면 안되므로, v번에 도착했을 때에만 정보를 따로 저장해주든지, 아니면 역으로 dfs를 돌리든지 해주자.
나는 전자의 방법을 이용하였다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, Q, A, B, a[MAX];
vector<int> v[MAX];
vector<pi> trace, tmp;
void dfs(int cur, int prev, int cnt) {
if (cur == B) {
trace = tmp;
return;
}
for (auto i : v[cur]) {
if (i == prev)
continue;
tmp.push_back({i, cnt+1});
dfs(i, cur, cnt + 1);
tmp.pop_back();
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N - 1; i++) {
int n1, n2;
cin >> n1 >> n2;
v[n1].push_back(n2);
v[n2].push_back(n1);
}
cin >> Q;
while (Q--) {
int ch;
cin >> ch >> A;
if (ch == 1) {
trace.clear();
cin >> B;
dfs(A, -1, 0);
for (auto i : trace) {
a[i.first] += i.second;
}
}
else {
cout << a[A] << "\n";
}
}
}23836. J2 - 어떤 우유의 배달목록 (Hard)
못풀었다...
문제를 읽고 HLD를 이용해야 한다는 걸 파악하자마자 좀 쫄았다.
시도를 해보긴 했는데, HLD 개념 자체도 가물가물한 상태였기 때문에 당연히 해결하지 못했다.
연습해야될듯 ㅎㅎ
개인적으로 꽤 재밌었다.
합세그에 펜윅트리를 처음 적용해봤는데 메모리 절약에 꽤 큰 도움이 되는 듯하다.
I번도 나중에 한번 보고 풀어봐야겠다.
J2번은 hld 좀 더 공부하고 나중에 도전해봐야겠다.
상당히 재밌었고, 오랜만에 스릴있게 ps해본 좋은 경험이었다.
'PS > My Diary (PS, 대회후기)' 카테고리의 다른 글
| [220220] ICPC Sinchon Winter Algorithm Camp Contest Open 후기 (4) | 2022.02.20 |
|---|---|
| [211231] Good Bye, BOJ 2021! 참여 후기 (0) | 2022.01.01 |
| [211204] 2021 서강대 프로그래밍 경진대회(SPC) Master를 풀어보았다. (0) | 2021.12.05 |
| [211106] 우아한테크코스 4기 1차 코딩테스트 후기 및 결과 (11) | 2021.11.06 |
| [211031] 백준에 잔디 기능이 생겼다 + 나의 백준일지 (0) | 2021.10.31 |