AtCoder ABC 257 D, E

D. 

https://atcoder.jp/contests/abc257/tasks/abc257_d

D - Jumping Takahashi 2

 

시작점을 잘 정해서 조건을 만족하도록 전부 순회할 수 있는지 그 때 최소의 S를 찾는 문제입니다. 

시작점을 고정하고, S도 고정시킨 후 각 점에서 다른 모든 점으로 조건을 만족한다면 그래프 위에서

선분으로 연결해줍니다. 이 때, dfs를 쭉 해주고 나면 모든 점을 방문했는지 여부를 O(N)에 알 수 있습니다.

이제 시작점을 선택하는 경우 O(N)이고, S는 파라메트릭 서치로 O(log4e9)만에 S를 결정해줄 수 있습니다.

시간복잡도는 O(N^2log(4e9))이고, N<=200이므로 시간안에 돕니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x[222], y[222], P[222], vis[222];
vector<int>g[222];

void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

bool solve(ll mid) {
    for (int i = 1; i <= n; i++)g[i].clear();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (P[i] * mid >= abs(x[j] - x[i]) + abs(y[j] - y[i])) {
                g[i].push_back(j);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        dfs(i);
        int ok = 1;
        for (int i = 1; i <= n; i++) ok &= vis[i];
        if (ok) return 1;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> P[i];
    }
    ll l = 0, r = 4e9;
    ll ans = 0;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (solve(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans;
}

 

 

 

 

E. 

https://atcoder.jp/contests/abc257/tasks/abc257_e

E - Addition and Multiplication 2

 

우선 길이를 최대한 길게 해줘야 합니다. 그건 가장 최소인 비용을 제일 많이 사주면 됩니다. 

그럼 이제 길이가 고정됩니다. 이 부분이 중요한데 이 길이를 유지하면서 N을 최대한 써주면 됩니다. 

길이가 고정된다면 채울 수 있는 한도 내에서 9부터 거꾸로 보는게 유리합니다. 

최소비용을 mini라고 한다면, 길이 k를 채우는데 최소 k*mini 비용이 듭니다.

따라서 길이를 len으로고정시키고 현재 i번째를 채우려고 한다면 i+1~len까지의 길이는 mini로 채우기에

충분해야 합니다. 따라서 남은 비용이 (len-i)*mini 이상인 경우 그리디하게 뒤부터 채워주면 됩니다.

재밌는 문제입니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, c[10];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= 9; i++) cin >> c[i];
    int mini = *min_element(c + 1, c + 10);
    int len = n / mini;
    for (int i = 1; i <= len; i++) {
        for (int j = 9; j; j--) {
            if (mini * (len - i) + c[j] <= n) {
                n -= c[j];
                cout << (char)('0' + j);
                break;
            }
        }
    }
}