AtCoder ARC 074

결과

CDF 풀고, E를 못 풀었습니다.

C. Chocolate Bar

세 조각으로 자르는 경우는 (1)두 절단선이 평행한 경우 (2)두 절단선이 수직으로 만나는 경우, 총 2가지입니다.

두 절단선이 평행한 경우에는 $H$ 혹은 $W$가 3의 배수이면 모두 똑같은 넓이로 만들 수 있고, 그렇지 않으면 $\min(H, W)$만큼 차이나게 만들 수 있습니다.

두 절단선이 수직으로 만나는 경우를 처리하는 것은 여러가지 방법이 있는 것으로 알고 있습니다.
저는 세로방향으로 자르는 위치를 고정해두고, 가로방향으로 자르는 위치를 삼분탐색 했습니다. $O(H \log W)$에 처리할 수 있습니다. $H$와 $W$를 swap한 다음에 한 번 더 돌려주면 $O(H \log W + W \log H)$에 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll a, b, ans;

ll chk(ll a, ll b, ll c){
    ll mx = max({a, b, c});
    ll mn = min({a, b, c});
    return min(ans, mx-mn);
}

void f(){
    for(int i=0; i<=a/2+1; i++){
        ll x = b*i, y, z;
        ll l = 0, r = b/2+1;
        while(l+3 <= r){
            ll m1 = (l+l+r)/3, m2 = (l+r+r)/3, r1, r2;

            y = m1*(a-i); z = (b-m1)*(a-i);
            if(x && y && z) r1 = chk(x, y, z);
            else r1 = 1e18;

            y = m2*(a-i); z = (b-m2)*(a-i);
            if(x && y && z) r2 = chk(x, y, z);
            else r2 = 1e18;

            if(r1 < r2) r = m2 - 1;
            else l = m1 + 1;
        }
        for(ll j=l; j<=r; j++){
            y = j*(a-i); z = (b-j)*(a-i);
            if(x && y && z) ans = min(ans, chk(x, y, z));
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> a >> b;
    if(a%3 == 0 || b%3 == 0){ cout << 0; return 0; }
    ans = min(a, b); f(); swap(a, b); f();
    cout << ans;
}

D. 3N Numbers

$3N$개의 원소를 앞 $K$개의 원소와 뒤 $3N-K$개의 원소로 나눠봅시다$(N \leq K \leq 2N)$. 앞 $K$개의 원소에서는 가장 큰 $N$개의 합을 구하면 되고, 뒤 $3N-K$개의 원소에서는 가장 작은 $N$개의 합을 구하면 됩니다.
이런 작업은 적당한 트리 자료구조 2개를 이용해서 관리해줄 수 있습니다.

heap 2개를 써도 되고, pbds를 이용해도 됩니다.

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, a[303030], pv;

ordered_set<p> st1, st2;
ll s1, s2;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=3*n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) s1 += a[i], st1.insert(p(a[i], i));
    for(int i=n+1; i<=3*n; i++) st2.insert(p(a[i], i));
    for(auto it=st2.begin(); ; it++){
        pv++; if(pv > n) break;
        s2 += it->x;
    }
    ll mx = s1 - s2;
    for(int i=n+1; i<=n+n; i++){
        int ord = st2.order_of_key(p(a[i], i)) + 1;
        if(ord <= n){
            s2 -= a[i]; s2 += st2.find_by_order(n)->x;
        }
        st2.erase(p(a[i], i));
        if(a[i] > st1.find_by_order(i-n-1)->x){
            s1 -= st1.find_by_order(i-n-1)->x;
            s1 += a[i];
        }
        st1.insert(p(a[i], i));
        mx = max(mx, s1 - s2);
    }
    cout << mx;
}

E. RGB Sequence

F. Lotus Leaves

그래프를 잘 만들어서 min cut을 구하면 된다는 것을 알 수 있습니다.

행을 나타내는 정점과 열을 나타내는 정점을 만듭시다.
$(i, j)$에 잎이 있다면 $i$번째 행을 나타내는 정점과 $j$번째 열을 나타내는 정점을 용량이 1인 간선으로 이어줍시다.
$(i, j)$가 시작지점이라면 source를 $i$번째 행을 나타내는 정점과 용량이 $\infty$인 간선으로 이어주고, $j$번째 열을 나타내는 정점과도 똑같이 이어줍시다.
$(i, j)$가 도착지점이라면 sink를 $i$번째 행을 나타내는 정점과 용량이 $\infty$인 간선으로 이어주고, $j$번째 열을 나타내는 정점과도 똑같이 이어줍시다.

min cut을 구해주면 됩니다.

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

const int SZ = 222;
struct Dinic{
    using FlowType = ll;
    const FlowType flow_max = 1e9;
    int s, t; // source, sink;
    struct Edge{ int v, dual; FlowType c; };
    vector<Edge> g[SZ];
    void addEdge(int s, int e, FlowType x){
        g[s].push_back({e, (int)g[e].size(), x});
        g[e].push_back({s, (int)g[s].size()-1, x});
    }
    int lv[SZ], work[SZ];
    bool bfs(){
        memset(lv, -1, sizeof lv);
        queue<int> q; q.push(s); lv[s] = 0;
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto i : g[v]){
                if(lv[i.v] == -1 && i.c > 0){
                    q.push(i.v); lv[i.v] = lv[v] + 1;
                }
            }
        }
        return lv[t] != -1;
    }
    FlowType dfs(int v, FlowType tot){
        if(v == t) return tot;
        for(int &_i=work[v]; _i<g[v].size(); _i++){
            Edge &i = g[v][_i];
            if(lv[i.v] == lv[v] + 1 && i.c > 0){
                int fl = dfs(i.v, min(tot, i.c));
                if(fl > 0){
                    i.c -= fl;
                    g[i.v][i.dual].c += fl;
                    return fl;
                }
            }
        }
        return 0;
    }
    FlowType run(int _s, int _t){
        s = _s; t = _t; FlowType ret = 0;
        while(bfs()){
            memset(work, 0, sizeof work);
            FlowType tmp;
            while((tmp = dfs(s, flow_max))) ret += tmp;
        }
        return ret;
    }
} flow;

int n, m;
char a[111][111];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    const int S = 219, T = 220;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        cin >> a[i][j];
        if(a[i][j] == '.') continue;
        flow.addEdge(i, 100+j, 1);
        if(a[i][j] == 'S') flow.addEdge(S, i, 1e9), flow.addEdge(S, 100+j, 1e9);
        if(a[i][j] == 'T') flow.addEdge(i, T, 1e9), flow.addEdge(100+j, T, 1e9);
    }
    auto res = flow.run(S, T);
    if(res > 50505) cout << -1;
    else cout << res;
}