JAG夏合宿2019 Day1 参加記

2019/9/14に行われたJAG夏合宿2019 Day1にチームEldoradoとして参加しました。

チームメンバーは、ニクロー、まほろば、NOSS

Day1

コンテスト

コンテストリンク:https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day1

Aをまほろば、Bをニクロー、Cを僕が読む。

CはN個の区間で領域全体をカバーする問題。最小数は解いたことがあったので後半を考える。何個まで取り除けるか考えると区間の重なりが少ないところがネックになるのでこれはimos法で解けそう。一応メンバーに解法を確認してもらい了解を得る。

(00:12) A問題 AC

ニクローさんがBの実装に入る。 途中でBの嘘が発覚したらしいので僕がCの実装に交代する。

Cの実装がバグる。+-の符号が逆だったり比較すべき値が違ったりで申し訳なかった… 後ろでBの修正が終わっているようなので急いで直す。

(00:45) C問題 AC

(00:54) B問題 AC

Dは有向グラフを作ると閉路がいくつかできるので、各閉路の周期を調べてすべてが昇順になるような回数を求めればよさそう。蟻本を開くと連立線形合同式の解を求める方法が載っているのでこれは解けました。

Cで実装に自信が無くなってしまったのでまほろば君に書いてもらう。

Dの考察の間にニクローさんが問題を読み進めていたので概要を聞く。比較的解けそうなのはEとJらしかった。

(02:06) D問題 AC

Eは無限増殖が可能か判定する問題。無限増殖がない条件を整理すると、任意の経路をたどって戻ってきたときの倍率が1であることがわかった。適当な根からdfsをしてすでに訪れた頂点へは倍率1で戻っているか確認すれば解けそう。問題は倍率が最大10⁹⁰⁰⁰⁰⁰になるのでやばい。 logをとることを思いつく。とりあえず書くとサンプルが合うので投げる。でも誤差怖いなあ...

(02:53) E問題 WA

それなりのケースが通っているのでやっぱり誤差がやばそう。long double にしたりEPSの値を小さくしたりして調整する。

(03:37) E問題 WA

なにも解決策が思いつかない。いったんEを諦めてJをみんなで考察する。

最大値はM-連結成分の個数なので簡単。問題は最小値でコマを頂点とする最大独立集合が解ければいいのだが不可能なので困った。

行き詰っているとまほろば君が「フロー...?」とつぶやいたのでよく見ると2部マッチングとわかる。蟻本の二部マッチングを写してもらうとサンプルが合ったので提出。

(04:10) J問題 AC

Eの解決法として複数MODをとればいいのではと思いつく。とりあえず5個MODを用意してlogと併用して判定に利用する。

(04:39) E問題 WA

テストケースがすすんだので誤差の問題だとわかる。よくわからないので10⁹以上の素数を100個くらい列挙して埋め込む。

(04:50) E問題 TLE

流石に多すぎたので50個に減らす。

(04:52) E問題 WA

？？？

このときはテストケース強すぎではと思った。これだけやってだめならMODガチャだね、とコンテスト終了まで粘った。が、ACはできませんでした。

感想・反省

EのEPSを1e-14から1e-5に緩くしたら通った。むしろlogないほうが良かったらしい。少数誤差を甘く見過ぎました...

全体としては解ける問題を解けているので悪くはなかったと思います。

ABC044 D - 桁和

問題

自然数 を 進数で表したときの桁和を とするとき、 を満たす最小の を求めよ。

問題リンク：ABC044 D

制約

• 
• 

解法

条件をまとめると、

• 
• 

となるような を探せばよい。

ここで2つの式の差をとると、

となる。 は必ず を因数に持つことから右辺は で割り切れる。すなわち、

が成り立つことが導かれる。よって解の候補は の約数+1。

以上から、 の全ての約数 対し を求め と一致するかを確認すれば解が求まる。 の場合は 以外の候補はない。

Code

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

ll f(ll b, ll n){
    if(n<b) return n;
    else return f(b,n/b)+n%b;
}

vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

int main() {
    ll n, s;
    cin >> n >> s;
    vector<ll> d = divisor(n-s);
    d.push_back(n);
    sort(d.begin(), d.end());
    for(auto x : d){
        if(f(x+1,n)==s){
            cout << x+1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Codeforces Round #304 (Div. 2) E. Soldier and Traveling

問題

頂点 辺の無向が与えられる。最初、 番目の頂点には 人の兵士がおり、各兵士は隣接する頂点に移動するかその場にとどまるかを行う。ただし、兵士が移動できる辺の本数は1本までとする。

すべての移動後、 番目の頂点にいる兵士の人数を となるようにできるか判定せよ。可能である場合、その移動の方法を出力せよ。

問題リンク：Codeforces Round #304 (Div. 2) E. Soldier and Traveling

制約

• 
• 
• 

解法

では不可能なので とします。

問題を次のように読み替えます。「 番目の頂点への入力を、出力を となるようにネットワークを構築できるか？」このようにするとフローによって問題を解くことができます。

辺を1度までしか使えないという制約のため、頂点を入力側と出力側に分けます。入力側から出力側へ隣接する頂点間と自分自身に辺を張ることで辺を1度までしか使用しないようにします。辺の容量は十分大きな値とします。

始点と終点を用意し、始点から入力点へ容量 の辺、出力点から終点へ の辺を張ります。このとき始点から終点への最大流 が となっていれば構築可能です。

頂点間の流量は逆辺の容量からわかります。

Code

#include <bits/stdc++.h>
using namespace std;
 
constexpr int IINF = INT_MAX;
 
struct edge{
    int to, cap, rev;
    bool isrev;
};
 
vector<vector<edge> > G;
vector<bool> used;
 
void add_edge(int from, int to, int cap){
    G[from].emplace_back((edge){to, cap, int(G[to].size()), false});
    G[to].emplace_back((edge){from, 0, int(G[from].size())-1, true});
}
 
// 増加路の探索
int dfs(int v, int t, int f){
    if(v == t) return f;
    used[v] = true;
    for(auto &e : G[v]){
        if(!used[e.to] && e.cap > 0){
            int d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// 最大流
int max_flow(int s, int t){
    used.resize(G.size());
    int flow = 0;
    while(1){
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, IINF);
        if(f==0) break;
        flow += f;
    }
    return flow;
}
 
int main() {
    int n, m, asum = 0, bsum = 0;
    cin >> n >> m;
    G.resize(n*2+2);  // 入力点、出力点、始点、終点
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        add_edge(n*2, i, a);  // 始点->入力点
        asum += a;
    }
    for(int i=0;i<n;i++){
        int b;
        cin >> b;
        add_edge(i+n, n*2+1, b);  // 出力点->終点
        bsum += b;
    }
    for(int i=0;i<n;i++){
        add_edge(i, i+n, IINF);  // とどまる辺
    }
    for(int i=0;i<m;i++){
        int p, q;
        cin >> p >> q;
        p--; q--;
        add_edge(p, q+n, IINF);  // 隣接する頂点間の辺
        add_edge(q, p+n, IINF);
    }
    if(asum != bsum || max_flow(n*2, n*2+1) != asum){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
        vector<vector<int> > ans(n, vector<int>(n,0));
        for(int i=0;i<n;i++){
            for(auto &e : G[i+n]){
                if(e.isrev){
                    ans[e.to][i] += e.cap;
                }
            }
        }
        // 出力
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout << ans[i][j] << " \n"[j==n-1];
            }
        }
    }
    return 0;
}

UVa Live Archive 6266 - Admiral

問題

ICPC Europe Northwestern Regional 2012 A

V頂点E辺の有向グラフが与えられる。このグラフ上で始点から終点への2本のパスを作る。ただし、2つのパスは始点と終点以外で同じ頂点を共有しないようにする。このとき、パスに使用される辺のコストの総和を最小化せよ。

問題リンク：UVa Live Archive 6266 - Admiral

制約

• 
• 

解法

始点から終点へ流量2を流すときの最小費用流として求めることができます。

2つのパスが頂点を共有しないようにするためには、頂点の容量を1とすればよいです。頂点に容量を設定するには、頂点を入力用と出力用に分け、その2つを設定したい容量でつなぎます。

計算量は です。

Code

最小費用流は蟻本p.203ほぼそのままです。

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

typedef pair<int, int> P;
constexpr int IINF = INT_MAX;

struct edge{
    int to, cap, cost, rev;
};

int V, E;
vector<vector<edge> > G;
vector<int> h, dist, prevv, preve;

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

// 最小費用流
int min_cost_flow(int s, int t, int f){
    int res = 0;
    fill(h.begin(), h.end(), 0);
    while(f > 0){
        priority_queue<P, vector<P>, greater<P> > que;
        fill(dist.begin(), dist.end(), IINF);
        dist[s] = 0;
        que.push({0,s});
        while(!que.empty()){
            P p = que.top();
            que.pop();
            int v = p.second;
            if(dist[v] < p.first) continue;
            for(int i=0;i<int(G[v].size());i++){
                auto &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push({dist[e.to], e.to});
                }
            }
        }
        if(dist[t] == IINF){
            return -1;
        }
        for(int v=0; v<V*2; v++) h[v] += dist[v];
        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*h[t];
        for(int v=t; v!=s; v=prevv[v]){
            auto &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main() {
    while(cin >> V >> E){
        G.clear();
        G.resize(V*2);
        h.resize(V*2);
        dist.resize(V*2);
        prevv.resize(V*2);
        preve.resize(V*2);

        // 頂点iの出力点i、入力点i+V
        for(int i=0;i<E;i++){
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            add_edge(a, b+V, 1, c);
        }
        // 頂点の容量を1とする
        for(int i=0;i<V;i++){
            add_edge(i+V, i, 1, 0);
        }
        cout << min_cost_flow(0, V*2-1, 2) << endl;
    }
    return 0;
}

UVa Live Archive 5920 - Kingdom Roadmap

問題

ICPC Regionals 2011 Europe - Northeastern の問題

問題リンク：UVa Live Archive 5920 - Kingdom Roadmap

N頂点の木が与えられる。どの1つの辺を取り除いても全体の連結性が保たれるように辺を追加するとき、必要な辺の最小本数とその追加する場所を求めよ。

• 

解法

どの1つの辺を取り除いても連結であるということは、橋である辺が無いということである。つまり、各辺が1つ以上の閉路に含まれるようにすればよい。

辺のつなぎ方を考える。葉である頂点には少なくとも1本辺を追加する必要があるので葉同士を辺でつないでいくのが最も効率的である。ある2頂点を結ぶと閉路ができ、その2頂点間の最短経路上の辺はすべて閉路に含まれることを利用する。

実装では、葉以外を根とする適当な根付き木をつくり、dfsで親に戻るとき1つ以上葉の頂点を持ちながら戻ればよい(これが辺(u,v)を閉路に含ませることに対応する)。イメージ的には探索で葉の頂点を回収しながら親へ向かう辺をまたがせるような感じである。持っている頂点数が3以上になったら辺でつないで頂点数が2以下になるようにする。葉の頂点数が奇数で最後まで余ったら根とつないでおく。

追加する辺の本数は(葉の頂点数)/2の切り上げとなる。

Code

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

typedef pair<int, int> P;

int n;
vector<vector<int> > g;  // グラフ
vector<P> ans;  // 追加する辺集合

vector<int> rec(int now, int pre){
    vector<int> res;
    if(g[now].size() == 1){  // 葉の頂点である
        res.push_back(now);
    }
    else{
        for(auto& nxt : g[now]){
            if(nxt == pre) continue;
            auto tmp = rec(nxt, now);
            if(res.size() + tmp.size() >= 3){  // 異なる部分木間で葉を結ぶ
                ans.push_back(make_pair(res.back(), tmp.back()));
                res.pop_back();
                tmp.pop_back();
            }
            for(auto& v : tmp) res.push_back(v);
        }
    }
    return res;
}

int main() {
    while(cin >> n){
        ans.clear();
        g.clear();
        g.resize(n);
        // 入力
        for(int i=0;i<n-1;i++){
            int u, v;
            cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        for(int i=0;i<n;i++){
            if(g[i].size()>1){  // 葉でない頂点を根とする
                vector<int> v;
                v = rec(i, -1);  // 根付き木で探索
                if(v.size()==2){  // 余った頂点が2つ
                    ans.push_back(make_pair(v[0], v[1]));
                }
                else{  // 余った頂点が1つ
                    ans.push_back(make_pair(i, v[0]));
                }
                break;
            }
        }
        // 出力
        cout << ans.size() << endl;
        for(auto& e : ans){
            cout << e.first+1 << " " << e.second+1 << endl;
        }
    }
    return 0;
}

AOJ 1350 There is No Alternative

問題

問題リンク：There is No Alternative

N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。

• 
• 

解法

最小全域木に1つ辺を追加したとき、その辺によって作られる閉路内にコストの一致する辺があればこれらの辺は交換可能なので必ず使用する辺の条件を満たさない。

よって、最小全域木を作り、閉路をつくるような辺に対してそれぞれ閉路内の辺から追加する辺とコストの一致する辺を候補から除けばよい。

Code

以下はクラスカル法で最小全域木を求めながらDFSで閉路探索を行う実装。計算量は

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> P3;
typedef pair<P ,P> PP;

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};

int n, m;
vector<P3> es;
UnionFindTree uf;
vector<vector<P> > g;
bool noAlt[50005];

// pre->nowの辺が閉路に含まれるか
bool dfs(int now, int pre, int t, int sc){
    if(now == t) return true;
    for(auto e : g[now]){
        int to = e.first, c = es[e.second].first;
        if(to == pre)continue;
        if(dfs(to, now, t, sc)){
            if(c == sc) noAlt[e.second] = false;  // 同じコストは除く
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int s, d, c;
        cin >> s >> d >> c;
        s--; d--;
        es.push_back({c,{s,d}});
    }
    // Kruskal法
    sort(es.begin(), es.end());
    uf.init(n);
    g.resize(n);
    for(int i=0;i<m;i++){
        auto e = es[i];
        int c = e.first, u = e.second.first, v = e.second.second;
        if(!uf.is_same(u,v)){  // 候補に加える
            uf.unite(u,v);
            noAlt[i] = true;
            g[u].push_back({v, i});  // 行先と辺番号のペア
            g[v].push_back({u, i});
        }
        else{
            // 閉路内でコストがcと同じ辺を候補から除く
            dfs(u, -1, v, c);
        }
    }
    int ecnt = 0, csum = 0;
    for(int i=0;i<m;i++){
        if(noAlt[i]){
            ecnt++;
            csum += es[i].first;
        }
    }
    cout << ecnt << " " << csum << endl;
    return 0;
}

ICPC2019 国内予選 参加記

2019/7/12(金)に行われたICPC2019国内予選にチームEldoradoとして参加しました。

チームメンバーは、nicklaw、mhrb、NOSSです。

チームメンバーの参加記
- ICPC2019 国内予選 参加記 - まほろば精進日誌

結果

ICPC2019順位表

ABCD4完で順位は41位でした。学内1位で予選突破しました。

順位表：ICPC 2019 国内予選順位表

本番前

模擬国内のとき：ICPC模擬国内予選2019 参加記

開始直前まで講義が入っていたため、会場入りが一番最後になってしまった。
ちょっとドタバタしながらも開始5分前くらいに準備が完了し、開始を待つ。

本番

Aをmhrb君、Bをnicklawさん、C以降を僕が読む戦略。

問題の印刷が完了するまで時間がかかるので、Aを見守る。ぱっとみて総和のmaxをとるだけなので大丈夫そう。印刷機で待機する。

mhrb君がAを高速にACした頃(5:32)ちょうど印刷ができたので、そのままBをnicklawさん、Cをmhrb君、Dを僕に割り振る。

Dの考察に入ったあたりでmhrb君が「Cが解けました」というので概要を聞く。大丈夫そうだと感じたので一緒にDを考え始める(後にこの時点でのC解法は嘘であることが発覚する)。

mhrb君にDの概要を伝えているうちに思考がまとまって、「これはDPでは？」という考察に至る。手元で遷移を書くとサンプルが合うのでうれしくなる。この時点で4完できそう感じだったので大丈夫そうと思っていた...。

Bを実装しているnicklawさんがバグに苦戦し、コード印刷してデバッグに移る。バトンタッチでmhrb君がC実装に入る。が、Cのサンプルが合わず嘘が発覚する。

またバトンタッチし、Bが通る(1:00:00)。Cの修正がまだかかりそうだったので紙実装しておいたDを書く。サンプルがあったので意気揚々とテストケースを実行する。しかし、無限に実行が終わらない。メンバーに実装を見せると、「ここ壊れてませんか」「ここ高速化できます」と言われたので、裏でそのまま実行させつつDのコードを印刷して修正に入る。

ここから「Cできます！」→「できませんでした...」→「Dできます！」→「できませんでした...」みたいなのを繰り返す。かなり険しい気持ちになった。

ついにCが通る(1:56:37)。残り1時間、ペナが重いので予選突破はDが通るかにかかってきた。

オーダーが全く改善できずつらくなっていると「コンパイル最適化でなんとかなるのでは」とnicklawさんから助言を受ける。試しにやってみると高速にテストケースが実行されている！これはいけそうとなり祈りながら実行を待つ。提出するとAC！(2:02:38) 順位表を見るとこの時点で25位くらいだったので喜びに包まれる。

Eは実装だと分かっていたがチームに実装ゴリラがいないので見送り、Fを全員で考える。いろいろ考察するもそれらしい解は生えず。この間順位表を見る度に順位が落ちていったのでちょっと心配した。

最終的にこのままコンテスト終了となった。

打ち上げ

ICPC国内予選お疲れ様でした！打ち上げ情報です pic.twitter.com/4bci2fHqLh

— 横浜国立大学競技プログラミング部 (@ynu_cpc) July 12, 2019

OBの方のご厚意で打ち上げを行ってくださいました。すごく楽しかったです。

普段お酒を飲まないので思ったより酔ってしまいました。

感想

模擬国内のときもそうだったのですが、かなり危なげない結果でした。Dが通っていなかったら予選通過できていないと考えると怖いです。反省としては、メンバーの考察の誤りを見つけられなかったことと、実装力の不足を感じました。このチームが出せるパフォーマンスはもっと高いと思っているのでアジア地区までに仕上げたいです。

コーチやチーム登録、会場準備をしてくださった先生、先輩、OBの方々、ありがとうございました。横浜大会がんばります。