naoya_t@hatenablog

いわゆるチラシノウラであります

ゆるふわ競プロオンサイト ＠FORCIA

Programming Contest

forcia.connpass.com
2/9(土) 14:00-

FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。
（over28枠に空きが1つ出たのを知って前日に登録）
最初404が出てコンテストがなかなか始められず（CTF？）、HackerRankでコンテスト開催経験のある人が呼ばれて対応に当たっていた…
そして15分遅れて（URLを変更して）コンテスト開始。
100-200-300-400-500-600-700-800 という配点と問題の体感難易度が大きくずれていた気がする。
4完(+部分点)で27位とかそのくらい。
Programming Problems and Competitions :: HackerRank

コンテストだけ出て懇親会は（ピザonlyであることが知られているので）帰るつもりだったけど、皆さんと色々話してて結局懇親会の最後（19:00）まで滞在。（お菓子と飲み物があって助かった）
FORCIAさん@matsu7874さんどうもありがとうございました。

A - B式A+B (100)

2進数の足し算。pythonでやった方が楽だったかも。
→AC

string solve(string& s, string& t) {
    int ls=s.size(), lt=t.size(), l=max(ls,lt);
    reverse(ALL(s)); reverse(ALL(t));
    vi a(l+1,0);
    rep(i,l+1) {
        if (i<ls && s[i]=='B') a[i]++;
        if (i<lt && t[i]=='B') a[i]++;
        if (a[i] >= 2) {
            a[i+1] += a[i]/2;
            a[i] %= 2;
        }
    }
    if (a[l] == 0) a.pop_back();
    reverse(ALL(a));
    vector<char> r(a.size());
    rep(i,a.size()) {
        r[i] = a[i] ? 'B' : 'b';
    }
    return string(ALL(r));
}

B - 集合写真 (200)

シミュレーションした
→AC

char solve(int k, int y, int x) {
    vector<vector<char>> mp(y, vector<char>(k, 0));
    int c=0;
    rep(i,y){
        rep(j,k){
            if (i%2==0)
                mp[i][j] = "yfkpo"[(c++) % 5];
            else
                mp[i][k-1-j] = "yfkpo"[(c++) % 5];
        }
    }
    return  mp[y-1][x-1];
}

C - 線香 (300)

約分するだけの問題
gcdって知ってますか、みたいな
→AC

// int gcd(int a, int b) { while(a) swap(a, b%=a); return b; }

void solve(int N, vi& s, vi& t) {
    int denom = s[0] - t[0];
    rep(i,N){
        int numer = s[i] - t[i];
        int g = gcd(numer, denom);
        printf("%d %d\n", numer/g, denom/g);
    }
}

D - 最短経路は何本ありますか (400)

最短距離のルートが何通りあるか
どこかで見たような典型問題だと思うんだけど
→1ケースTLE（HackerRankのシステムは全テストケース通らなくても部分点がつくのね）

後で

Dijkstraしてから、#0に近い順にルート数を後ろに足し込んでいけば余裕で間に合う。
→AC

void dij1(int nV, vector<vector<pair<int,T>>>& adjacent, vector<T>& d, int start); // 略

ll solve(int N, int M, vi& s, vi& t, vi& c) {
    vector<vector<pair<int,ll>>> adj(N);
    rep(i,M){
        adj[ s[i] ].pb(make_pair(t[i], (ll)c[i]));
        adj[ t[i] ].pb(make_pair(s[i], (ll)c[i]));
    }

    vll d(N, INT_MAX);
    d[0]=0;

    dij1(N, adj, d, 0);
    vii d2(N);
    rep(i,N) d2[i] = ii(d[i], i);
    sort(ALL(d2));

    vll dc(N, 0);
    dc[0] = 1;

    for (ii p: d2) {
        int di = p.first, u = p.second;
        for (auto p: adj[u]){
            int v = p.first; ll dij = p.second;
            if (d[v] <= d[u]) continue;

            if (d[u] + dij == d[v]) {
                (dc[v] += dc[u]) %= MOD;
            }
        }
    }
    return dc[N-1];
}

E - ガソリンスタンド (500)

条件を満たす（距離がD以内の）辺を繋いでダイクストラして経路を逆に辿るやつ
→AC

void dij1(int nV, vector<vector<pair<int,T>>>& adjacent, vector<T>& d, int start, vector<int>& prev); // 略

void solve(int N,int D, vi& y, vi& x) {
    vector<vector<double>> d(N, vector<double>(N, 1e9));

    rep(i,N) d[i][i] = 0;
    vector<vector<pair<int,double>>> adj(N);
    repC2(i,j,N){
        double h = hypot(x[i]-x[j], y[i]-y[j]);
        if (h <= D + 1e-9) {
            d[i][j] = d[j][i] = h;
            adj[i].pb(make_pair(j, h));
            adj[j].pb(make_pair(i, h));
        }
    }

    vector<int> prev;
    vector<double> e(N);
    dij1(N, adj, e, 0, prev);

    vi route;
    int here = N-1;
    while (here != 0) {
        route.pb(here);
        here = prev[here];
    }
    route.pb(0);
    reverse(ALL(route));

    for (int n: route){
        printf("%d\n", n+1);
    }
}

F - 無向木 (600)

全方位木DPだ
こないだ習ったsnuke法の出番だ
…
計算が最後まで合わず
試合終了
（あとで解く）

あとで

下からの寄与分を引くのは合ってたけど差分を下ろしてくるときにcnt分増やすのを忘れていた
→AC

vvi nxt;
vi deg;

typedef pair<ll,int> P;

vector<map<int,P>> mp; // mp[u][v] = some
vll ans;

void dfs(int u, int p=-1){
    ll ans = 0;
    int cnt = 0;
    for (int v: nxt[u]){
        if (v==p) continue;
        if (!found(mp[v], u)) dfs(v, u);
        P res = mp[v][u];
        debug("  sub %d->%d : res=P(%lld %d)\n", v,u, res.first, res.second);
        ans += res.first + res.second;
        cnt += res.second;
    }

    debug("} -> mp[%d][%d] = P(%lld %d)\n", u,p, ans,cnt+1);
    mp[u][p] = P(ans, cnt+1); // cntはuを含む
}

void bfs(int u) {
    ll Tm = mp[u][-1].first; int Ta = mp[u][-1].second;
    ans[u] = Tm; // P(Tm, Ta);

    for (int v: nxt[u]) {
        if (ans[v] != -1) continue;

        ll Sm = mp[v][u].first; int Sa = mp[v][u].second;
        Sm += Sa; // TのうちのSの寄与分

        ll Dm = Tm - Sm; int Da = Ta - Sa;
        Dm += Da; // それをこっちに下ろしてくる

        mp[v][-1] = P(
            mp[v][u].first + Dm,
            mp[v][u].second + Da
        );
        bfs(v);
    }
}

void solve(int N, vi& p) {
    nxt.resize(N);
    deg.assign(N, 0);
    mp.resize(N);
    ans.assign(N, -1);

    rep(i,N-1){
        int u=1+i, v=p[1+i];
        nxt[u].pb(v);
        nxt[v].pb(u);
        deg[u]++; deg[v]++;
    }

    dfs(0);
    bfs(0);

    rep(i,N){
        printf("%lld\n", ans[i]);
    }
}

G - 射的 (700)

開かなかった

終了後に問題を開いた

何これ… セグ木貼り付けて瞬殺な問題だった（開けばよかった）
→AC

// セグ木略
int solve(int N, int k, vi& f, vi& b) {
    SegmentTree<int> sg(131071, MAXIMUM);
    rep(i,N){
        sg.update(i, b[i]);
    }
    int best = 0;
    rep(i,N){
        int x = f[i] + sg.query(max(0,i-k), min(100001,i+k+1));
        amax(best, x);
    }
    return best;
}

H - 三角形 (800)

開かなかった

解説

解説によると、Bから2つ入りA,Cに1つずつ出るフロー問題として解けるらしい。
（各点1回ずつしか通れないので、各点を2ノードに分けて繋ぐやつ）
あとで解く

あとで

暫く考えてたんだけど
ああ、maximum flowじゃなくて min-cost flowね
はい

sourceからBに2つ入るとBを2つ使うことになって（使えないから）A/C片方しか通せない…
→Bの上と下に繋げば良い

Spaghetti Sourceのやつを使おうと思ったんだけどちゃんと使えてないみたいで、サンプルケースは合うけど投げるとWA&TLE
蟻本のやつで行こう
→AC

// 以下、後で自分がコピペする用に全文掲載
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }


struct Edge {
    int to, cap, cost, rev;
};
const int INF = INT_MAX;

class MinCostFlow {
    int V;
    vector<vector<Edge>> G;
    vector<int> dist;
    vector<int> prevv, preve;

 public:
    MinCostFlow(int V) : V(V) {
        G.resize(V);
        dist.assign(V, -1);
        prevv.assign(V, -1);
        preve.assign(V, -1);
    }

    void add_edge(int from, int to, int cap, int cost) {
        G[from].pb((Edge){to, cap, cost, (int)G[to].size()});
        G[to].pb((Edge){from, 0, -cost, (int)G[from].size()-1});
    }

    int run(int s, int t, int f) {
        int res = 0;
        while (f > 0) {
            dist.assign(V, INF);
            // fill(dist, dist+V, INF);
            dist[s] = 0;
            bool update = true;
            while (update) {
                update = false;
                for (int v=0; v<V; ++v) {
                    if (dist[v] == INF) continue;
                    for (int i=0; i<G[v].size(); ++i) {
                        Edge& e = G[v][i];
                        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            update = true;
                        }
                    }
                }
            }
            if (dist[t] == INF) {
                return -1;
            }

            int d = f;
            for (int v=t; v!=s; v=prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * dist[t];
            for (int v=t; v!=s; v=prevv[v]) {
                Edge& e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};


inline int PT(int n){ return n*(n+1)/2; } // 0, 1, 3, 6, 10, ...
inline int U(int i, int j) { return PT(i) + j; } // 0 ; 1 2 ; 3 4 5 ; ...

ll solve(int N, vvi& a) {
    int NN = PT(N);
    // n:2*[0..NN); each node: { 2n -> 2n+1 }
    int src = 2*NN, sink = 2*NN+1;
    int node_a = U(0,0), node_b = U(N-1,0), node_c = U(N-1,N-1);

    MinCostFlow mcf(2*NN+2);

    auto add_edge_with_check = [&](int from_i, int from_j, int to_i, int to_j) {
        if (IN(to_i, 0, N-1) && IN(to_j, 0, to_i)) {
            int from = 2*U(from_i, from_j)+1;
            int to = 2*U(to_i, to_j);
            mcf.add_edge(from, to, 1, 0); // cap, cost
        }
    };

    rep(i,N) {
        rep(j,1+i) {
            int u = 2*U(i,j);
            // G[u].emplace_back(u, u+1, 1, a[i][j]);
            mcf.add_edge(u, u+1, 1, a[i][j]);

            add_edge_with_check(i,j, i-1,j-1);
            add_edge_with_check(i,j, i-1,j);
            add_edge_with_check(i,j, i,j-1);
            add_edge_with_check(i,j, i,j+1);
            add_edge_with_check(i,j, i+1,j);
            add_edge_with_check(i,j, i+1,j+1);
        }
    }

    mcf.add_edge(src, 2*node_b, 1, 0);
    mcf.add_edge(src, 2*node_b+1, 1, 0);
    mcf.add_edge(2*node_a+1, sink, 1, 0);
    mcf.add_edge(2*node_c+1, sink, 1, 0);

    int res = mcf.run(src, sink, 2);
    return res;
}

int main() {
    int N; scanf("%d", &N);
    vvi a(N);
    rep(i,N){
        a[i].resize(1+i);
        rep(j, 1+i){
            scanf("%d", &a[i][j]);
        }
    }
    cout << solve(N,a) << endl;
    return 0;
}