뜬금 없지만 갑자기 다시 PS에 대한 욕심이 생겼습니다. ICPC WF진행하는거 보니까 뭔가 다시 한번 제대로 해볼까 하는 생각도 들더라고요. 이 글에서는 이번 한 주 동안 풀었던 문제들을 정리하려고 합니다. 그 전에 최근에 세운 몇가지 목표들을 정리하겠습니다.
- solved.ac class 1~7 all solve
- Codeforces Purple (1900)
- Atcoder Blue (1600)
- BOJ 2000 solve
사실 뭔가 최종 목표라기 보단 어떤 목적을 이루는 과정에서 중간 체크포인트 느낌으로 세운 도전 과제라고 보는게 맞긴 하겠습니다. 결국 최종적인 목표는 대회에서 좋은 성적을 거두는거고 다른건 다 그걸 이루기 위한 연습이죠. 마침 이번에 UCPC에 같이 나가게 될 팀원들도 다 실력이 너무 뛰어난 분들이라 같이 잘해서 후회 없이 마치고 싶네요.
아래 정리된 문제들은 특정 순서로 정렬되어 있지 않습니다.
BOJ
/<20303> 할로윈의 양아치
한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다는 조건은 친구 관계인 모든 아이를 하나의 집합으로 묶어주면 된다는 뜻입니다. 따라서 유니온 파인드를 사용해 아이들을 묶어서 집합들의 크기와 사탕수의 합을 구한 후 $K$명 이상의 아이들이 울면 안된다는 조건을 만족하게 집합들을 고르는건 배낭 용량이 $K$인 냅색으로 해결 가능합니다.
int n, m, k;
int arr[30005]; int par[30005]; int sz[30005];
int fnd(int node){
if(par[node] == node) return node;
else return par[node] = fnd(par[node]);
}
bool uni(int node1, int node2){
// 2 -> 1
int p1 = fnd(node1), p2 = fnd(node2);
if(p1 == p2) return false;
else{
par[p2] = p1; sz[p1] += sz[p2];
arr[p1] += arr[p2];
return true;
}
}
vector<pii>v; int dp[30005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
par[i] = i; sz[i] = 1;
cin >> arr[i];
}
while(m--){
int u, v;
cin >> u >> v;
uni(u, v);
}
for(int i=1; i<=n; i++){
if(par[i] == i){
v.push_back({sz[i], arr[i]});
}
}
int ss = v.size();
for(int i=0; i<ss; i++){
for(int j=k-1; j>=1; j--){
if(j-v[i].fr >= 0){
dp[j] = max(dp[j], dp[j-v[i].fr]+v[i].sc);
}
}
}
cout << dp[k-1];
}
/<27172> 수 나누기 게임
최근에 알게된 사실이 있는데 $ \frac{N}{1} + \frac{N}{2} + \dots + \frac{N}{N-1} + \frac{N}{N} $ 은 $\mathcal{O}(N log N)$ 정도라고 합니다. 출처 : Harmonic series - Wikipedia
Harmonic series (mathematics) - Wikipedia
From Wikipedia, the free encyclopedia Divergent sum of all positive unit fractions In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions: ∑ n = 1 ∞ 1 n = 1 + 1 2 + 1 3 + 1 4 + 1 5 + ⋯ . {\displaystyl
en.wikipedia.org
이 점을 사용해 수열의 원소들의 100만 이하인 배수를 전부 확인해주면서 답을 계산해도 시간안에 충분히 해결 가능합니다.
bool occur[1000005];
int ans[1000005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n; cin >> n; vector<int>v(n);
for(int i=0; i<n; i++){
cin >> v[i]; occur[v[i]] = 1;
}
for(int &k:v){
int it = k+k;
while(it <= 1000000){
if(occur[it]) {ans[it]--; ans[k]++;}
it += k;
}
}
for(int &k:v){
cout << ans[k] << ' ';
}
}
/<17404> RGB거리 2
RGB거리의 원형 버전... 이라고 생각하기 쉽지만 사실은 그냥 가능한 색의 조합이 얼마 안된다는 점을 사용해 $1$번 집과 $N$번 집의 색을 정해둔 후 그냥 RGB거리랑 동일하게 해결 가능합니다.
void init(ll arr[][3], int n){
for(int i=0; i<n; i++){
fill(arr[i], arr[i]+3, INF);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n; cin >> n; ll cost[n][3];
for(int i=0; i<n; i++) cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
vector<int>p = {0, 1, 2};
ll mn = INF;
do{
ll dp[n][3]; init(dp, n);
int c1 = p[0], cn = p[1];
dp[0][c1] = cost[0][c1];
for(int i=1; i<n; i++){
if(i!=n-1){
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
}
else{
for(int k=0; k<3; k++){
if(k!=cn) continue;
for(int j=0; j<3; j++){
if(j==k) continue;
dp[i][k] = min(dp[i][k], dp[i-1][j] + cost[i][k]);
}
}
}
}
mn = min(mn, min({dp[n-1][0], dp[n-1][1], dp[n-1][2]}));
}while(next_permutation(p.begin(), p.end()));
cout << mn;
}
/<2143> 두 배열의 합
누적합을 전처리 해둔 후 B의 모든 구간합으로 가능한 것들이 몇번 등장하는지 map같은 자료구조에 저장해둔 후 A의 모든 구간합이 B에서 몇번 등장했는지 전부 더해주면 됩니다.
ll T; int n, m;
map<ll, ll>mp;
ll a[1005], b[1005], prea[1005], preb[1005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> T;
cin >> n;
for(int i=1; i<=n; i++){
cin >> a[i]; prea[i] = prea[i-1] + a[i];
}
cin >> m;
for(int i=1; i<=m; i++){
cin >> b[i]; preb[i] = preb[i-1] + b[i];
}
for(int i=1; i<=m; i++){
for(int j=i; j<=m; j++){
if(mp.find(preb[j]-preb[i-1])==mp.end()){
mp[preb[j]-preb[i-1]] = 1;
}
else{
mp[preb[j]-preb[i-1]] += 1;
}
}
}
ll ans = 0;
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
if(mp.find(T-(prea[j]-prea[i-1]))!=mp.end()){
ans += mp[T-(prea[j]-prea[i-1])];
}
}
}
cout << ans;
}
/<2342> Dance Dance Revolution
DP의 상태를 정의하는데 좀 어려움을 겪었던 문제입니다. 결론적으로는 단순히 $i$번째 패턴을 처리 할 때 왼쪽 발이 $l$ 위치에 있고 오른쪽 발이 $r$ 위치에 있다고 가정을 하면 상태를 $(i, l, r)$의 길이 3의 튜플로 생각 할 수 있게 됩니다.
그러면 상태 전이는 단순히 모든 가능한 $(i-1, l, r)$에서 $(i, l, r)$로의 전이를 보면 됩니다.
int f(int i, int j){
if(i > j) swap(i, j);
if(i==0) return 2;
if(i==1 && j==4) return 3;
else{
return 2 + j - i;
}
}
int dp[100005][5][5];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
vector<int>v;
while(1){
int tmp; cin >> tmp; if(!tmp) break;
v.push_back(tmp);
}
int n = v.size(); // [i][l][r]
for(int i=0; i<=n; i++){
for(int j=0; j<5; j++){
for(int k=0; k<5; k++){
dp[i][j][k] = INF;
}
}
}
dp[0][0][0] = 0;
dp[1][0][v[0]] = 2; dp[1][v[0]][0] = 2;
for(int i=2; i<=n; i++){
int curstep = v[i-1];
// r
for(int j=0; j<5; j++){
for(int k=0; k<5; k++){
if(j==k) continue;
dp[i][j][curstep] = min(dp[i][j][curstep],
dp[i-1][j][k] +
(k == curstep ? 1 : f(k, curstep)));
}
}
// l
for(int j=0; j<5; j++){
for(int k=0; k<5; k++){
if(j==k) continue;
dp[i][curstep][j] = min(dp[i][curstep][j],
dp[i-1][k][j] +
(k == curstep ? 1 : f(k, curstep)));
}
}
}
int ans = INF;
for(int j=0; j<5; j++){
for(int k=0; k<5; k++){
ans = min(ans, dp[n][j][k]);
}
}
cout << ans;
}
/<2473> 세 용액
set으로 비비려다가 망했습니다. 결국 이진 탐색 써서 $\mathcal{O}(N^{2} log N)$에 해결했습니다. 상수 차이가 이렇게 무섭군요. 투 포인터 풀이도 있고 이 풀이가 오히려 더 아름다우니 이쪽을 찾아보시는거도 좋겠습니다.
int n;
vector<ll> arr;
set<ll>s;
ll diff = LLINF; vector<ll>ans;
void upd(ll x, ll y, ll z){
ll tmp = abs(x + y + z);
if(tmp < diff){
diff = tmp;
ans = {x, y, z};
}
}
void solve(ll x, ll y, vector<ll>& a){
auto it = lower_bound(a.begin(), a.end(), -x-y);
if(it!=a.end() && *it!=x && *it!=y){
upd(x, y, *it);
}
if(it!=a.begin()){
auto prv = it; prv--;
if(*prv != x && *prv != y) upd(x, y, *prv);
}
if(it!=a.end()){
auto nxt = it; nxt++;
if(*nxt != x && *nxt != y) upd(x, y, *nxt);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n; arr.resize(n);
for(int i=0; i<n; i++) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(i == j) continue;
solve(arr[i], arr[j], arr);
}
}
sort(ans.begin(), ans.end());
for(auto i:ans) cout << i << ' ';
}
/<16724> 피리 부는 사나이
문제 상황을 생각해보면 이렇게 어떤 칸에 위치한 사람은 그 칸에 적힌 방향을 따라가다가 어떤 사이클 안에 갇히게 되는데 이 사이클에 있는 칸 어떤걸 골라도 SAFE ZONE이 됩니다. 따라서 이 개수를 세주면 되고 이는 유니온 파인드로 쉽게 가능합니다 (이미 합쳐져 있지 않은 모든 정점을 적힌 방향으로 전부 합쳐준 후 부모 == 자신인 정점의 수).
int n, m;
char grid[1005][1005];
pii par[1005][1005];
pii fnd(pii node){
if(par[node.fr][node.sc] == node) return node;
else return par[node.fr][node.sc] = fnd(par[node.fr][node.sc]);
}
bool uni(pii node1, pii node2){
// 2 -> 1
pii p1 = fnd(node1), p2 = fnd(node2);
if(p1 == p2) return false;
else{par[p2.fr][p2.sc] = p1; return true;}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n >> m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> grid[i][j];
par[i][j] = {i, j};
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
pii n1 = {i, j}, n2;
if(grid[i][j]=='U'){
n2 = {i-1, j};
}
if(grid[i][j]=='L'){
n2 = {i, j-1};
}
if(grid[i][j]=='R'){
n2 = {i, j+1};
}
if(grid[i][j]=='D'){
n2 = {i+1, j};
}
uni(n1, n2);
}
}
int ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(fnd({i, j}) == make_pair(i, j)){
ans++;
}
}
}
cout << ans;
}
/<7670> Game Dice
공평한 4, 6, 8, 10, 12, 또는 20면의 주사위가 $d (d \le 13)$개 주어졌을때 합이 $x$가 되게 하는 확률을 구하는 문제입니다. 냅색 느낌의 DP로 간단하게 해결 가능합니다. $dp[i][j]$를 $i$번째까지 굴렸을때 합이 $j$가 되는 경우의 수라고 하면 단순히 $i$번째 주사위의 각 주사위 면에 대해 $j$를 $1$에서 $260$ (이거 보다 큰 합은 못 나오니까) 까지 봐주면서 $j - k$ (주사위 면에 적힌 수) 가 $0$보다 크면 $dp[i][j]$에 $dp[i-1][j-k]$를 더해주면 됩니다.
최종 답은 모든 주사위의 면의 수를 곱한걸 $D$라고 했을 때 $\frac{dp[d][x]}{D}$가 됩니다.
while(1){
int d; cin >> d;
if(!d) return 0;
vector<ll>v;
ll den = 1;
for(int i=0; i<d; i++){
char dd; cin >> dd;
ll f; cin >> f;
v.push_back(f); den *= f;
}
ll x; cin >> x;
if(x == 0 || x > 260) {
cout << "0.00000\n";
continue;
}
ll dp[d][261];
for(int i=0; i<d; i++){
fill(dp[i], dp[i]+261, 0);
}
for(int k=1; k<=v[0]; k++) dp[0][k] = 1;
for(int i=1; i<d; i++){
for(ll j=1; j<=260; j++){
for(ll k=1; k<=v[i]; k++){
if(j-k > 0 && dp[i-1][j-k]){
dp[i][j] += dp[i-1][j-k];
}
}
}
}
ll num = dp[d-1][x];
cout << (ld)num/den << endl;
}
/<1029> Hiking
단순 격자 다익스트라 문제입니다.
int T;
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 1, -1, -1, 1, 0, 0};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> T;
while(T--){
int n, m; cin >> n >> m;
ll dist[n][m]; ll h[n][m];
int fx = 0, fy = 0, fh = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
char tmp; cin >> tmp;
if(tmp == '#') h[i][j] = -1;
else{
h[i][j] = tmp - '0';
if(h[i][j] > fh){
fx = i; fy = j; fh = h[i][j];
}
}
// cout << h[i][j] << ' ';
dist[i][j] = INF;
}
// cout << endl;
}
int x, y; cin >> x >> y;
priority_queue< pair<ll, pii>, vector< pair<ll, pii> >, greater<pair<ll, pii>> >pq;
dist[x][y] = 0;
pq.push({0, {x, y}});
while(!pq.empty()){
ll cdst = pq.top().fr;
int cx = pq.top().sc.fr, cy = pq.top().sc.sc;
pq.pop();
if(cdst > dist[cx][cy]) continue;
for(int dir=0; dir<8; dir++){
int nx = cx + dx[dir], ny = cy + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(h[nx][ny] == -1) continue;
ll cost = (h[nx][ny] == h[cx][cy] ? 1 : (abs(h[nx][ny]-h[cx][cy])+1)*(abs(h[nx][ny]-h[cx][cy])+1));
// cout << cx << ' ' << cy << ' ' << nx << ' ' << ny << ' ' << cost << endl;
ll ndst = cdst + cost;
if(ndst >= dist[nx][ny]) continue;
dist[nx][ny] = ndst;
pq.push({ndst, {nx, ny}});
}
}
if(dist[fx][fy] == INF) cout << "NO" << endl;
else cout << dist[fx][fy] << endl;
}
}
/<10722> Binary Mobile Tree
약간의 물리학 사전지식이 필요한 트리 dp문제입니다. 트리 dfs를 통해 각 막대가 평형을 이루려면 매달린 위치에서 얼마만큼 좌우로 위치를 옮겨야 하는지 계산한후 이를 토대로 전체 너비를 계산하면 됩니다. 왼쪽인지 오른쪽인지에 따른 처리가 조금 햇갈릴 수 있습니다.
int T; ld ansl = 0; ld ansr = 0;
// 0 = left, 1 = right
ll dfs(ll cur, int dir, vector<ll>& l, vector<ll>& r, vector<ll>& len, vector<pll> &dp){
ll node = abs(cur);
if(cur > 0){
return cur;
}
if(cur == -1){
ll cl = dfs(l[node], 0, l, r, len, dp);
ll cr = dfs(r[node], 1, l, r, len, dp);
dp[node] = {cl , cr};
return cl + cr;
}
else{
ll cl = dfs(l[node], dir, l, r, len, dp);
ll cr = dfs(r[node], dir, l, r, len, dp);
ld x = (ld)(cr*len[node])/(cl+cr);
dp[node] = {cl , cr};
return cl + cr;
}
}
void ddfs(int cur, ld cst, vector<ll>& l, vector<ll>& r, vector<ll>& len, vector<pll> &dp){
int node = abs(cur);
if(cur > 0) return;
ll cl = dp[node].fr, cr = dp[node].sc;
ld x = (ld)(cr*len[node])/(cl+cr);
ld y = (ld)len[node] - x;
ansl = max(ansl, cst+x); ansr = min(ansr, cst-y);
ddfs(l[node], cst + x, l, r, len, dp);
ddfs(r[node], cst - y, l, r, len, dp);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> T;
while(T--){
int n;
cin >> n;
vector<ll>left(n+1), right(n+1), len(n+1);
vector<pll>dp(n+1, {0, 0});
for(int i=1; i<=n; i++){
cin >> len[i] >> left[i] >> right[i];
}
ansl = ansr = 0;
dfs(-1, -1, left, right, len, dp);
ddfs(-1, 0.0, left, right, len, dp);
// cout << ansl << ' ' <<ansr << endl;
cout << ansl - ansr << endl;
}
}
/<1202> 보석 도둑
PBDS로 날먹했습니다. 끝. (정해는 PQ에 적당한 그리디를 섞는겁니다.)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void m_erase(ordered_set &OS, int val){
int index = OS.order_of_key(val);
ordered_set::iterator it = OS.find_by_order(index);
OS.erase(it);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n, k; cin >> n >> k; vector<pll>v(n);
for(int i=0; i<n; i++) cin >> v[i].sc >> v[i].fr;
sort(v.begin(), v.end(), greater<pll>());
ordered_set s;
while(k--){
ll c; cin >> c; s.insert(c);
}
ll ans = 0;
for(int i=0; i<n; i++){
int it = s.order_of_key(v[i].sc);
if(it == (int)s.size()) continue;
m_erase(s, *s.find_by_order(it)); ans += v[i].fr;
}
cout << ans;
}
/<16946> 벽 부수고 이동하기 4
옛날에 은근 까다롭다고 생각했던 문제인데 지금은 쉽게 풀리네요. 벽을 부수지 않은 상태로 이동 가능한 인접한 칸들을 유니온 파인드를 사용해 하나로 묶고 이 묶음의 크기를 저장해 둡니다. 그 후 각 벽에 대해서 인접한 묶음들의 크기를 더합니다.
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
pii par[1005][1005]; int sz[1005][1005], grid[1005][1005];
int ans[1005][1005];
pii fnd(pii node){
if(par[node.fr][node.sc] == node) return node;
else return par[node.fr][node.sc] = fnd(par[node.fr][node.sc]);
}
bool uni(pii n1, pii n2){
pii p1 = fnd(n1), p2 = fnd(n2);
if(p1 == p2) return false;
else{
sz[p1.fr][p1.sc] += sz[p2.fr][p2.sc];
par[p2.fr][p2.sc] = p1;
return true;
}
}
void solve(int n, int m){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
char tmp; cin >> tmp;
grid[i][j] = tmp-'0';
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
par[i][j] = {i, j};
if(grid[i][j] == 0) sz[i][j] = 1;
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 1) continue;
for(int dir = 0; dir<4; dir++){
int nx = i + dx[dir], ny = j + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(grid[nx][ny] == 1) continue;
uni({i, j}, {nx, ny});
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 0) {
cout << 0;
continue;
}
set<pii>s;
for(int dir = 0; dir<4; dir++){
int nx = i + dx[dir], ny = j + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
pii p = fnd({nx, ny});
if(s.count(p)) continue;
ans[i][j] += sz[p.fr][p.sc]; s.insert(p);
}
cout << (ans[i][j]+1) %10;
}
cout << endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int N, M; cin >> N >> M;
solve(N, M);
}
/<18110> solved.ac
주어진 조건을 구현. Division by zero 주의.
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
ll n; cin >> n; vector<int>v(n);
if(n==0){
cout << 0; return 0;
}
for(int i=0; i<n; i++) cin >> v[i];
int k = (15 * n)/100 + (((15*n)/10)%10 < 5 ? 0 : 1);
sort(v.begin(), v.end());
ll sum = 0;
for(int i=k; i<n-k; i++){
sum += v[i];
}
cout << round((ld)(sum)/(ld)(n-2*k));
}
/<20529> 가장 가까운 세 사람의 심리적 거리
map으로 각 mbti가 몇번 등장 했는지를 저장해둔 후 가능한 모든 $16^3$개의 mbti조합중 가능한거에 대해서 답을 브루트포스 하면 됩니다. 태그에 비둘기집 원리가 있던데 왜 있는지 모르겠습니다.
nt dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
vector<string>mbti = {"ISTJ", "ISFJ", "INFJ", "INTJ", "ISTP", "ISFP", "INFP", "INTP", "ESTP", "ESFP", "ENFP", "ENTP", "ESTJ", "ESFJ", "ENFJ", "ENTJ"};
int get(string a, string b, string c){
int ret = 0;
for(int i=0; i<4; i++){
if(a[i] != b[i]) ret++;
if(b[i] != c[i]) ret++;
if(c[i] != a[i]) ret++;
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int T; cin >> T;
while(T--){
int N; cin >> N;
map<string, int>mp;
for(int i=0; i<N; i++){
string s; cin >> s;
if(mp.find(s) == mp.end()) mp[s] = 1;
else mp[s]++;
}
int ans = 20;
for(int i=0; i<16; i++){
for(int j=0; j<16; j++){
for(int k=0; k<16; k++){
string a = mbti[i], b = mbti[j], c = mbti[k];
if(mp.find(a) == mp.end() || mp.find(b) == mp.end() || mp.find(c) == mp.end()) continue;
int ta = mp[a], tb = mp[b], tc = mp[c];
mp[a]--; mp[b]--; mp[c]--;
if(mp[a] < 0 || mp[b] < 0 || mp[c] < 0){
mp[a] = ta, mp[b] = tb, mp[c] = tc;
continue;
}
ans = min(ans, get(a, b, c));
mp[a] = ta, mp[b] = tb, mp[c] = tc;
}
}
}
cout << ans << endl;
}
}
/<14940> 쉬운 최단거리
단순 격자 BFS.
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int N, M; cin >> N >> M; int grid[N][M], dist[N][M], vis[N][M]; queue<pii>q;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> grid[i][j];
dist[i][j] = -1; vis[i][j] = 0;
if(grid[i][j] == 2) {q.push({i, j}); dist[i][j] = 0; vis[i][j] = 1;}
}
}
while(!q.empty()){
int x = q.front().fr, y = q.front().sc; q.pop();
for(int dir=0; dir<4; dir++){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx < 0 || nx >=N || ny < 0 || ny >= M) continue;
if(vis[nx][ny] || grid[nx][ny] == 0) continue;
vis[nx][ny] = 1; dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cout << (grid[i][j] == 0 ? 0 : dist[i][j]) << ' ';
}
cout << endl;
}
}
/<6064> 카잉 달력
CRT밖에 안 떠오르던데... 태그 보면 다른 풀이가 있나 봅니다. 저는 CRT 썼습니다.
/ ax + by = __gcd(a, b) // returns __gcd(a, b)
ll extended_euclid(ll a, ll b, ll &x, ll &y) {
ll xx = y = 0;
ll yy = x = 1;
while (b) {
ll q = a / b;
ll t = b; b = a % b; a = t;
t = xx; xx = x - q * xx; x = t;
t = yy; yy = y - q * yy; y = t;
}
return a;
}
// finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime
// here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.
pair<ll, ll> CRT(ll a1, ll m1, ll a2, ll m2) {
ll p, q; ll g = extended_euclid(m1, m2, p, q);
if (a1 % g != a2 % g) return make_pair(0, -1);
ll m = m1 / g * m2;
p = (p % m + m) % m;
q = (q % m + m) % m;
return make_pair((p * a2 % m * (m1 / g) % m + q * a1 % m * (m2 / g) % m) % m, m);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int t; cin >> t;
while(t--){
int M, N, x, y; cin >> M >> N >> x >> y;
auto ans = CRT(x-1, M, y-1, N);
cout << (ans.sc == -1 ? -1 : ans.fr + 1) << endl;
}
}
/<21736> 헌내기는 친구가 필요해
단순 격자 BFS 2.
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int N, M; cin >> N >> M; char g[N][M]; bool vis[N][M]; queue<pii>q;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> g[i][j]; vis[i][j] = 0;
if(g[i][j] == 'I') {q.push({i, j}); vis[i][j] = 1;}
}
}
int ans = 0;
while(!q.empty()){
int x = q.front().fr, y = q.front().sc; q.pop();
for(int dir=0; dir<4; dir++){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
if(vis[nx][ny] || g[nx][ny] == 'X') continue;
if(g[nx][ny] == 'P') ans++;
vis[nx][ny] = 1; q.push({nx, ny});
}
}
if(ans) cout << ans;
else cout << "TT";
}
/<27312> 운영진에게 설정 짜기는 어려워
생각보다 까다로웠던 애드혹 문제입니다. 첫 단추를 잘못 꾀면 못 빠져나오는 느낌? 풀이 자체는 간단한데 $M \le Q \le N$이라는 점을 이용해 $i$번째 캐릭터의 $i$번째 특성을 물어본후 각각 돌아온 결과 외에 특성을 아무거나 출력해줍니다. 이러면 각 캐릭터마다 겹치지 않는 특성이 한개 씩 생기니 문제를 해결 할 수 있습니다.
이런걸 칸토어의 대각 논법이라 부른다던데 뭔지 모르겠습니다. 또 나만 모르는 웰노운인듯.
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int M, N, Q; cin >> M >> N >> Q;
vector<int>v(N); for(int i=0; i<N; i++) cin >> v[i];
vector<int>ans;
for(int i=1; i<=M; i++){
cout << "? " << i << ' ' << i << endl;
int ch; cin >> ch;
if(ch == 1) ans.push_back(v[i-1]);
else ans.push_back(ch-1);
}
for(int i=M+1; i<=N; i++){
ans.push_back(v[i-1]);
}
cout << "! ";
for(auto i:ans) cout << i << ' ';
cout << endl;
return 0;
}
/<1918> 후위 표기식
어려웠습니다. 결국 풀이를 찾아서 공부하면서 풀었습니다.
- 빈 스택과 빈 후위 표기식을 만들어줍니다.
- 주어진 중위 표기식을 앞에서부터 훑으면서 다음을 반복합니다.
- 현재 보는 문자가 피연산자라면 후위 표기식에 이어 붙입니다.
- 현재 보는 문자가 연산자라면 스택이 비어있거나 우선순위가 더 낮은 연산자나 괄호가 나올때 까지 스택의 맨위 원소를 제거해서 후위 표기식에 이어 붙입니다. 그 후 스택에 연산자를 넣어줍니다.
- 현재 보는 문자가 ( 라면 이를 스택에 넣어줍니다.
- 현재 보는 문자가 ) 라면 ( 가 나올때까지 스택의 맨위 원소를 제거해서 후위 표기식에 이어 붙입니다. ( 도 스택에서 지워줍니다.
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
string ex; cin >> ex;
map<char,int>pr;
pr['+'] = pr['-'] = 1; pr['*'] = pr['/'] = 2;
stack<char>st; string ret = "";
for(char& c:ex){
if(pr.find(c) == pr.end() && c != '(' && c != ')'){
ret += c;
}
else if(pr.find(c) != pr.end()){
while(!st.empty() && st.top() != '(' && pr[st.top()] >= pr[c]){
ret += st.top(); st.pop();
}
st.push(c);
}
else{
if(c == '(') st.push(c);
else{
while(!st.empty() && st.top() != '('){
ret += st.top(); st.pop();
}
if(!st.empty() && st.top() == '(') st.pop();
}
}
}
while(!st.empty()){
ret += st.top(); st.pop();
}
cout << ret;
}Codeforces
1805C - Place for a Selfie
$ax^2 + bx + c = kx$가 해가 없어지는 $k$를 찾으면 되는 문제입니다. $k$값을 정렬하고 중복값을 제거한 후 $(b-k)^2 - 4ac$가 최소가 되는 $k$를 찾은 후 이때 $(b-k)^2 - 4ac < 0$을 만족하는지 확인하면 됩니다. 저는 삼분탐색을 활용했습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
const ll INF = 4'500'000'000'000'000'000;
int t;
ll get(ll a, ll b, ll c, ll idx, vector<ll>& v){
return (b-v[idx])*(b-v[idx]) - 4LL*a*c;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
int n, m; cin >> n >> m;
vector<ll>li(n);
for(int i=0; i<n; i++) cin >> li[i];
compress(li);
for(int i=0; i<m; i++){
ll a, b, c; cin >> a >> b >> c;
int lo = 0, hi = n - 1;
while(hi-lo>=3){
int p = (lo+lo+hi)/3, q = (lo+hi+hi)/3;
if(get(a, b, c, p, li) <= get(a, b, c, q, li)){
hi = q;
} else lo = p;
}
bool flg = false;
for(int i=lo; i<=hi; i++){
if(get(a, b, c, i, li) < 0){
cout << "YES" << endl;
cout << li[i] << endl;
flg = true;
break;
}
}
if(!flg) cout << "NO" << endl;
}
cout << endl;
}
}
1805D - A Wide, Wide Graph
우선 $G$에 모든 정점은 서로 연결되어 있을 겁니다. 그러고 가까운 정점들 사이의 연결부터 하나씩 끊어지게 되는 형태를 이루게 되겠죠. 그러면 어떤 정점 $u$가 연결된 컴포넌트에서 분리되는 시점은 $k$가 $u$에서 가장 멀리 떨어진 정점까지의 거리보다 커지는 시점이 됩니다 (그 이전 시점까지는 어떻게든 다른 정점과 연결이 되어 있을거니까). 그리고 이 가장 멀리 떨어진 정점은 트리의 지름에 속해있는 두 정점중 더 멀리 떨어진 정점이 됩니다 (그렇지 않다면 지름일 수가 없기 때문). 따라서 트리의 정점을 구한 후 양 끝 정점에서 다른 모든 정점들까지의 거리를 구해주면 각 $k$에 대해서 몇개의 정점이 떨어져 나가게 되는지 구할 수 있습니다. 답이 $N$보다 커질수는 없음에 주의합시다.
제가 처음에 생각하지 못했던 부분은 다음 두가지 입니다.
- 지름의 후보가 여러개 일수는 있지만 결국 그러면 더 멀리 떨어진 정점까지 거리가 지름을 이루니 따로 처리해줄 필요가 없다.
- 둘 중 더 멀리 떨어진걸 저장해야 한다. (저는 실수로 더 가까운걸 저장했습니다.)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
const ll INF = 4'500'000'000'000'000'000;
int n;
int dist[100005];
vector<int>edges[100005];
int dinode = 1 , di1 = 1, di2 = 1, mxdist = 0;
void dfs1(int cur, int par, int d){
dist[cur] = d;
if(d >= mxdist){
mxdist = d;
dinode = cur;
}
for(auto nxt:edges[cur]){
if(nxt==par) continue;
dfs1(nxt, cur, d+1);
}
}
void dfs2(int cur, int par, int d, vector<int>&dst){
dst[cur] = d;
for(auto nxt:edges[cur]){
if(nxt == par) continue;
dfs2(nxt, cur, d+1, dst);
}
}
int removedat[100005]; int dp[100005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> n;
for(int i=1; i<n; i++){
int u, v; cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
dfs1(1, -1, 0); di1 = dinode;
dfs1(dinode, -1, 0); di2 = dinode;
vector<int>dd1(n+1, 0), dd2(n+1, 0);
dfs2(di1, -1, 0, dd1); dfs2(di2, -1, 0, dd2);
for(int i=1; i<=n; i++){
dd1[i] = max(dd1[i], dd2[i]);
removedat[dd1[i]]++;
}
int ans = 1;
for(int i=1; i<=n; i++){
cout << min(n, ans) << ' ';
ans += removedat[i];
}
}
1942D - Learning to Paint
우선 처음 해봤던 생각은 다음과 같습니다.
- $k$개의 가장 큰거만 중간 과정에 저장하는 DP로 해결할 수 있지 않을까?
- 어떤 원소 $a_{i,j}$를 합에 더하려면 이전 구간이 $i-2$전에는 끝나야 하는구나.
- 안 더하는 경우까지 고려를 해줘야 하는구나.
이 점들을 사용해서 DP를 사용 할 수 있을거 같았는데 결국 구체적인건 못 떠올리고 에디토리얼을 봤습니다. 풀이는 다음과 같습니다.
$dp[i]$가 $i$에서 끝나는 모든 구간들까지 고려 했을때 가장 큰 $min(k, 2^i)$개의 합들을 저장한 리스트라고 합시다. 그렇다면 결국 $dp[i]$를 구하는건 $dp[1], dp[2], \dots, dp[i-1]$ 안에 있는 원소나 그 중 $j \le i-2$인 $dp[j]$의 원소들에 $a_{j+2, i}$를 더한 값 중 가장 큰 $k$개를 구하는 문제가 됩니다. 이때 애초에 리스트에 더하는 순서를 큰거부터 넣어준 다면 정렬 순서를 유지할 수 있으니 기본적으로 각 $dp[i]$에 대해서 $dp[i][0]$가 가장 큰 원소임을 보장 할 수 있게 됩니다. 따라서 $dp[i]$를 구하는 과정은 다음과 같아집니다.
값, 리스트 번호, 리스트 내에서의 위치이 3가지 정보를 저장하는 PQ를 만듭시다. 그 후 PQ에 $0 \le j \le i-1$인 $j$에 대해
- $j = i-1$이면 $(dp[i-1][0], i-1, 0)$을 넣어줍니다.
- $j \le i-2$이면 $(dp[j][0] + a_{j+2, i}, j, 0)$을 넣어줍니다.
- $dp[0]$은 ${0}$으로 정의합니다.
- 그냥 단순히 $a_{1, i}$를 넣는거 까지 고려해서 이 또한 넣어줍니다. 이 때 $j$는 편의상 $-1$로 정합니다.
그 후 PQ가 비거나 $dp[i]$의 크기가 $k$가 될때 까지 다음을 반복합니다.
- PQ의 맨위에서 $(val, j, idx)$를 뽑아줍니다. 그 후 $val$을 $dp[i]$에 넣어줍니다.
- $j < 0$ 또는 $idx = len(dp[j])-1$ 이라면 아래 과정은 건너뜁니다.
- $j = i-1$이라면 $a_{j+2, i}$를 더해줄 수 없으니 단순히 $j$번째 리스트의 다음으로 큰 원소를 넣어줍니다 $(dp[i-1][idx+1], i-1, idx+1)$.
- $j \le i-2$이라면 $a_{j+2, i}$를 더해줄 수 있으니 $j$번째 리스트의 다음으로 큰 원소에 그 값을 더해서 넣어줍니다 $(dp[j][idx+1] + a_{j+2, i}, i-1, idx+1)$.
위 과정을 $1 \dots i$ 까지 반복해주면 $dp[n]$에 남아있는 $k$개의 원소가 답이 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
const ll LLINF = 4'500'000'000'000'000'000;
const int INF = 1'000'000'007;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int t; cin >> t;
while(t--) {
int n, k; cin >> n >> k;
vector<ll>dp[n+1]; ll arr[n+1][n+1];
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
cin >> arr[i][j];
}
}
dp[0].push_back(0);
for(int i=1; i<=n; i++){
// val, from-j, idx-in-list-j
priority_queue<pair<ll, pll> > pq;
pq.push({dp[i-1][0], {i-1, 0}});
// to add interval, must be at least 2 apart
for(int j=i-2; j>=0; j--){
if(j > 0) pq.push({dp[j][0] + arr[j+2][i], {j, 0}});
else{
pq.push({arr[j+2][i], {j, 0}});
}
}pq.push({arr[1][i], {-1, 0}});
while(!pq.empty() && dp[i].size() < k){
ll val = pq.top().fr; int j = pq.top().sc.fr, idx = pq.top().sc.sc; pq.pop();
dp[i].push_back(val);
if(j < 0 || idx == (int)dp[j].size()-1) continue;
if(j == i-1){
pq.push({dp[i-1][idx+1], {i-1, idx+1}});
}
else{
pq.push({dp[j][idx+1] + arr[j+2][i], {j, idx+1}});
}
}
}
for(auto i : dp[n]) cout << i << ' ';
cout << endl;
}
}일부러 문제를 읽어본 사람이 읽는다고 가정하고 풀이를 좀 짧게 짧게 적어봤습니다. 제가 개인적으로 복습하고 싶은 부분이 있는 문제들은 조금 더 힘을 줬고요. 앞으로도 얼마나 꾸준히 작성할지는 모르지만 주간 회고록은 이런 형식으로 적어 보도록 하겠습니다.
감사합니다.