ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

会津大学競技プログラミング合宿2019参加記

番外編

と言うことで、昨年も参加したACPCに再び参加しました。

1日目

行き

新幹線では、JAG合宿の復習として、最小費用流を写経しながら問題を解いていました。
郡山から会津若松への電車では、TABさんやてんぷらさん、てぃーいけさんを始めとした競プロerの方々が続々と乗ってきて面白かったです。

可愛い。

コンテスト

わくさん、drogskolさんとのあらかじめ組んでいたチームで出場しました。

コンテスト開始後は、わくさんがA、僕がB、drogskolさんがC以降を読む、という形で進めました。わくさんがAをかなりのスピードで通してくださったので(オンサイトだとFAでした)、そのまま自分もBを結構な速度で通すことができました(こちらもオンサイトFA、わーい)。
その後は、わくさんがCの実装を行うことになり、自分とdrogskolさんでD以降の問題の共有をしつつ、DEの考察を行いました。
Cの実装の合間を縫って自分がDを通しました(が、自分は嘘でした。それぞれの辺に対する2つの頂点を通った回数を加算する際に、どちらか片方の頂点分しか加算していなかった上、そもそも自分の解法にコーナーケースがありました)。
その後は、Cの考察をし直したときに、わくさんが強連結成分分解ですねぇ、と言ったので、たしかになんでここまで誰も気づかなかったのだろうみたいに反省をしながらCを通し、3人でEを行うことになりました。
E問題は、大方正しいDP解が求まっていたのですが、そもそもの笛をソートする優先順位が間違っていたので、そこに気づけずタイムアップとなりました…実際、数分後に優先順位を変えただけで通ったので悔しいです。
Fは3人とも何もわからず、Gはフローっぽくてやりたいことはなんとなくわかるのですがコーナーケースの処理が何もわからないので無理そう、となっていたので今後の課題になりそうです。

コンテスト後

まずはラーメンを食べました。

ラーメン屋に入る前、yamadさんが言っていたダジャレを晒しておいたのですが、数分後にてぃーいけさんにお会いしたときにはすでにバレていて、Twitterは怖いなぁと思いました。

その後はyamadさんを除いた早稲田勢で銭湯へ行きました。コーヒー牛乳うめぇ。


ホテルはyamadさんと同室だったのですが、

  1. yamadさんがTwitterを開く
  2. yamadさんが笑い出し、ボソッと「Twitterおもしれぇ」とつぶやく
  3. 僕が「どうしたんですか」と尋ねる
  4. うしさんの過去ツイートが朗読される
  5. 僕が爆笑する
  6. 数分経ち、yamadさんがボソッと「Twitterおもんな」とつぶやく
  7. 僕が爆笑する
  8. yamadさんがボソッと「Twitterアンインストールしたわ！ｗ」とつぶやく
  9. 僕が爆笑する
  10. 1へ

という雰囲気のやりとりを繰り返していたら日付が変わっていたような気がします。

2日目

朝

美味しかったです。

大学へ向かう途中、誰かのスマホから急に通知音が流れ、どうしたのだろうと思っていたのですが、
しろくん「ツバサさんが今他の方のツイートをRTしたので通知音が流れてしまいました、マナーモードにしてバイブだけにしますね」
？？？？？？？？？？？？？？？？？？？？

僕は後輩にストーキングされています。

コンテスト

ホスフィンさん、よこさんが2人で既に組んでいて、僕がランダムでそこに入るという形になりました。
自分はB以降の問題を全て読み、適当に解けそうな人に割り振る、みたいなことをしていました。
初めはC担当だったのですが、B担当のホスフィンさんがBがぱっとわからなさそう、というのと、Cが幾何で自分よりホスフィンさんがやるのがよさそう(ただやりたくないだけです)、ということで、Bの考察を行いました。結局Bの実装はAを終えたよこさんに投げました。
その後は、I,Hを自力で解き、Mは式変形が苦手だったのでホスフィンさんに投げてデバッグを行い、Gはゲームだったので、グランディ数の概念のみをよこさんに教えつつ必勝法を考えてもらう、という感じで割り振りました。
これがうまくハマり、残り時間40分ほどで7完という形になりました。
しかし、最後に考えていたE問題が全くわからず、転倒数が絡んでいそう、という地点から進まなくなっていませんでした。が、残り3分ぐらいでホスフィンさんに「実装をしていいですか」と聞かれ、何もわからず「いいです」と答えると、なんと残り数十秒で通ってしまいました。
？？？？？？

懇親会

懇親会がありました。
自分が座っていた卓は、全員20歳以上なのに2人しかお酒を飲まない卓で、隣の卓も、ninjaさん以外が全員未成年、という卓だったので、比較的平和でした。
途中、顔を真っ赤にしたmonkukuiさんがいらっしゃって、明日のジャッジに間に合わないと危ないから集合時間まで起きてお酒を飲んでいれば安全だねぇ！とか、Clarでしりとりをしたり解法を聞こう！みたいな謎の会話をしたり、てんぷらさんやTsutajさんがいらっしゃって、goodbatonさんとのセグ木トークに挟まれ逃げられなくなった結果、わけもわからず頷く係をしたりしていました(セグ木を使わずに累積和を書く人は偉い、みたいな声が聞こえて、？？？となっていました)。beetさん、てんぷらさんの卓では食事がレート順に取れるらしく、それを眺めて怖いなぁ、という話で盛り上がったりもしました。

懇親会後

懇親会をはやめに出て、この日も銭湯に行きました。

コーヒー牛乳うめぇ。
お風呂上りに、ちょうど銭湯に来たばかりのてんぷらさんや、赤みが引いたmonkukuiさん達に出会いましたが、懇親会の最後の方はやはり大変でした～、みたいなお話を聞きました。
monkukuiさんは、受付で預けるはずの下駄箱の鍵を下駄箱につけっぱなしにしてしまったらしく、入り口に戻って下駄箱の鍵をO(HW)で全探索していました。結局ポケットに入っていたみたいです。なんで。

寝る前は初日と同じく、yamadさんのTwitter実況を聞きながら笑う人になっていました。すると...

なんでスマホが鳴るの？？


3日目

朝

起きてしばらくしていると、部屋にボブネミミッミが大音量で流れました。

遅刻しました。ごめんなさい。

コンテスト

自分はB,Dを書きました。
Dは桁DPだったので自分がやりますと言ってそのまま通しました。
Bは実装が重そうだったので、ろーるまんさんの代わりに自分が実装をしました。
B問題は、前計算で4種類それぞれのテトラミノについて、一番左上のブロックからの相対座標をペアでメモしておくと、ミノの当てはめる順番をnext_permutationで全探索して、盤面を走査しつつ、左上の空きマスにぶち当たるたびにピースを埋められるかどうかを試していく、というように実装しました。
解説をなんとなく聞いていた感じ、毎回走査をして調べるのは想定TLE解らしい？のですが、AOJを信じているので通りました(自分は実装途中に、計算量で1か所×4を見落としていることに気づいたので、その時点で計算量について考えることをやめました)。

E問題:三人「セグ木をガリガリ書いたこと(残り時間で実装しきる力と気力)はないです。」
F問題:三人「suffix arrayを書いたことはないです。」
G問題:三人「全方位木DPを書いたことはないです。」
　　　　　　　　 　 終
　　　　　　　　制作・著作
　　　　　　　　━━━━━
　　　　　　　　　ⓃⒽⓀ

帰り

様々な方と一緒に学食でお昼を食べました。

帰り道の新幹線では、しろくんにday2のI問題を教えていました(実際は横からみていただけですが)。のですが、途中でいきなりしろくんが
「ツバサさんツイートしましたね？」
と言ってきました。
だからなんで？？？？？？？？？
助けを募集しています。

東京についた後、ふたたびてんぷらさん、おきもちさん、りあんさんと合流することができたので、その中でおきもちさん、りあんさんと、後輩のsuta君の4人でラーメンを食べました。


全体のまとめ

今年もとても楽しかったです。初めて競プロのイベントに参加した去年とは違い、いろんな方に認識してもらえていたり、去年よりも高度な話をしたり、問題を解いたりすることができたと思います。
来年も参加したいですね。

運営をしてくださった方々や、自分とお話をしてくださった方、ありがとうございました。

おまけ

JAGのときはお見掛けしただけだったのですが、改めててんぷらさんはかっこいいと思いました。
参考↓

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - D Permutation Sort

中国剰余定理

問題

問題概要

長さNの順列P,Qが与えられます。
1回の操作で、 P_{i} = Q_{p_{i}}に変換する、という操作を全ての1 \leqq i \leqq Nについて行います。
全ての1 \leqq i \leqq NがP_i = iとなるまでの操作回数の最小値を求めてください。

解法

何回か操作をするといずれループすることがわかります。
操作して初めてP_{i} = iとなるような操作回数をf_{i}、初期のP_{i}に戻ってくるまでの操作回数(ループの長さ)をl_{i}とすると、
x \equiv f_{i} (mod \ l _{i})を満たす最小のxが答えになります。
解が存在しなかったり、f_{i}が求まらなければ、答えは-1です。 これは中国剰余定理そのもので、拡張ユークリッドの互除法等で求めることができます(参考)。

感想

この分野は少し苦手なので今まで避けてきましたが、ようやく勉強することができました…一回書いておけば実装がそこまで重くないタイプに見えます。

提出コード

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

// as + bt = GCD(a,b) a,b:const s,t:var(any)
// return GCD(a,b)
long long extGCD(long long a, long long b, long long& s,
                 long long& t) {
    s = 1, t = 0;
    while(b) {
        long long tmp = a / b;
        a -= b * tmp;
        s -= t * tmp;
        swap(a, b);
        swap(s, t);
    }
    return a;
}

// x≡b_i(mod m_i) calc min x,lcm(m_i).
// if not exist, return (-1,-1)
pair<long long, long long> ChineseRem(
        const vector<long long>& b,
        const vector<long long>& m) {
    long long r = 0, lcm = 1;
    assert(b.size() == m.size());
    long long bsize = b.size();
    for(int i = 0; i < bsize; ++i) {
        long long p, q, d, now;
        d = extGCD(lcm, m[i], p, q);
        if((b[i] - r) % d != 0) return make_pair(-1, -1);
        now = (b[i] - r) / d * p % (m[i] / d);
        r += lcm * now;
        lcm *= m[i] / d;
    }
    return make_pair((r + lcm) % lcm, lcm);
}

long long n;
vector<long long> p,q,fmemo,lmemo;

long long solve();

int main(){
    cin >> n;
    p.resize(n);
    q.resize(n);
    fmemo.assign(n,0);
    lmemo.assign(n,0);
    for(int i = 0;i < n;++i){
        cin >> p[i];
        --p[i];
    }
    for(int i = 0;i < n;++i){
        cin >> q[i];
        --q[i];
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    // prepair
    for(int i = 0;i < n;++i){
        long long now = p[i];
        bool ch = 0;
        for(int j = 0;j < n;++j){
            if(now == i){
                fmemo[i] = j;
                ch = 1;
            }
            now = q[now];
            if(now == p[i]){
                lmemo[i] = j + 1;
                break;
            }
        }
        if(!ch)return -1;
    }
    long long ans = 0;
    return ChineseRem(fmemo,lmemo).first;
}

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - B Not-trivial Common Divisor

問題

問題概要

N個の数A_{i}が与えられます。
その中で、全ての要素がK (K \gt 1)で割り切れるような集合Sを作り、そのSの総和を最大化してください。

解法

Kを合成数にするよりも、素数にした方がお得( K = xyと選ぶと、xが約数ではあるがyが約数に含まれない数の分だけ損をしてしまう)なので、素因数についてのみ考えていけば良いです。
あとは、A_{i}に含まれる素因数全てについて、それを約数としてもつA_{i}の総和を計算し、最大値を求めればよいことになります。
素因数をキー、総和をvalueとするmapを作成し、A_{i}について素因数分解を行いつつ加算していくと楽な気がします。
提出コードは以下になります↓

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

long long n;
vector<long long> a;
map<long long,long long> mp;

long long solve();

int main(){
    cin >> n;
    a.resize(n);
    for(int i = 0;i < n;++i)cin >> a[i];
    cout << solve() << endl;
    return 0;
}

long long solve(){
    for(int i = 0;i < n;++i){
        long long x = a[i];
        for(long long j = 2;j * j <= a[i];++j)
            if(x % j == 0){
                while(x % j == 0)x /= j;
                mp[j] += a[i];
            }
        if(x > 1)mp[x] += a[i];
    }
    long long ans = 0;
    for(auto now : mp)ans = max(ans,now.second);
    return ans;
}

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - J Rooks Game

Union-Find木 二部マッチング Dinic法(最大流,最小カット) リベンジ

問題

問題概要

N \times Nの盤面に、M個の駒が配置されています。それぞれの駒は、縦か横方向に好きなだけ移動させることができ、他の駒にぶつかったら、その時点で停止してぶつかった駒を獲得することができます。ただし、他の駒が存在しない方向へ動かすことはできません。この操作を、駒が獲得できなくなるまで行います。
最適な操作をして、駒の獲得数を最小化、および最大化してその個数を求めてください、というものです。

解法

駒を最大化する方法の方が個人的には楽です。駒を頂点とみなし、縦、および横の座標が一致している2つの駒に辺を張ります。すると、どこか適当な駒を根とすると、葉から根に駒を順番にぶつけていくことで、獲得できる駒が最大化できます。
よって、答えは(グラフの連結成分-1)の総和になります(グラフが複数になる場合に注意します)。これはUnion-Findでよしなに連結していくことで簡単に求まります。
最小化するパターンは、最終的な盤面に着目すると、それぞれの行、もしくは列にたかだか1つの駒しか存在しません。
そこで、最終的に駒が存在する地点の行、列のペアを上手く組み合わせて最大化すると、それが最適なパターンになります。
実際に操作する場合は、残すと決めた駒に他の駒をぶつけていけばよいので、これで最適解がもとまります(もしこの方法で残すと決めた以外の駒が残ってしまった場合、そもそも残すと決めた駒のパターンが間違っています)。
ということで、行と列の二部マッチングを考えることになり、K個の駒の行と列のペアに辺を張り、フローを流すことで、最終的に残る駒の個数が求まります。あとは、これをMから引けばよいです。

感想

最終的に残る駒の個数を最大化、フローっぽい、まではいけたのですが二部マッチングに帰着させることができませんでした…
よく見るような形の問題な気がするので、おさえておきたいです。

提出コード

#include <bits/stdc++.h>
#define fi first
#define se second
#define inf (long long)1e8
using namespace std;
using p = pair<long long,long long>;

struct Unionfind{
    vector<int> par;
    vector<int> treerank;
    Unionfind(int n = 1){stree(n+1);}
    void stree(int n = 1){
        par.assign(n,-1);
        treerank.assign(n,0);
    }
    int root(int x){
        if(par[x] < 0)return x;
        return par[x] = root(par[x]);
    }
    bool issame(int x,int y){return root(x) == root(y);}
    bool uni(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return 0;
        if(treerank[x] > treerank[y])swap(x,y);
        if(treerank[x] == treerank[y])++treerank[y];
        par[y] -= size(x);
        par[x] = y;
        return 1;
    }
    int size(int x){return -par[root(x)];}
};

template<class T>
struct Dinic{
    struct edge{
        int to;
        T cap;
        int rev;
    };
    vector<vector<edge>> lst;
    vector<int> completed;
    vector<int> dist;
    Dinic(int n = 1){
        lst.resize(n);
        completed.resize(n);
        dist.resize(n);
    }
    bool add(int start,int goal,T capacity){
        lst[start].push_back((edge){goal,capacity,(int)lst[goal].size()});
        lst[goal].push_back((edge{start,0,(int)lst[start].size()-1}));
        return 1;
    }
    void distbfs(int start){
        fill(dist.begin(),dist.end(),-1);
        queue<int> bfsqu;
        dist[start] = 0;
        bfsqu.push(start);
        while(bfsqu.size() > 0){
            int now = bfsqu.front();
            bfsqu.pop();
            for(int i=0;i < lst[now].size();++i){
                edge* nowe = &lst[now][i];
                if(nowe->cap > 0 && dist[nowe->to]<0){
                    dist[nowe->to] = dist[now] + 1;
                    bfsqu.push(nowe->to);
                }
            }
        }
    }
    T pathdfs(int now,int goal,T nf){
        if(now == goal)return nf;
        for(int& i= completed[now];i < lst[now].size();++i){
            edge* e = &lst[now][i];
            if(e->cap > 0 && dist[now] < dist[e->to]){
                T ans = pathdfs(e->to,goal,min(nf,e->cap));
                if(ans > 0){
                    e->cap -= ans;
                    lst[e->to][e->rev].cap += ans;
                    return ans;
                }
            }
        }
        return 0;
    }
    T solve(int start,int goal){
        T ans=0,nf = 0;
        while(1){
            distbfs(start);
            if(dist[goal]<0)return ans;
            fill(completed.begin(),completed.end(),0);
            while((nf=pathdfs(start,goal,inf))>0)ans += nf;
        }
        return -1;
    }
};

long long n,m;
long long dp[1005][1005][2][2] = {0};
vector<long long> lstx[1005],lsty[1005];
vector<p> v;
Unionfind uf;
set<p> st;

long long solve();

int main() {
    cin >> n >> m;
    v.resize(m);
    for (int i = 0; i < m; ++i){
        cin >> v[i].fi >> v[i].se;
        --v[i].fi;
        --v[i].se;
        st.insert(v[i]);
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    long long ans = 0;
    uf = Unionfind(m);
    sort(v.begin(),v.end());
    for(int i = 0;i < m;++i){
        lstx[v[i].fi].push_back(i);
        lsty[v[i].se].push_back(i);
    }
    for(int i=0;i<n;++i){
        for(int j=1;j<lstx[i].size();++j)
            uf.uni(lstx[i][j],lstx[i][j-1]);
        for(int j=1;j<lsty[i].size();++j)
            uf.uni(lsty[i][j],lsty[i][j-1]);
    }
    //min
    Dinic<int> din(2 * n +2);
    for(int i = 0;i < m;++i)
        din.add(v[i].fi,v[i].se + n,1);
    for(int i = 0;i < n;++i){
        din.add(2 * n,i,1);
        din.add(i + n,2 * n + 1,1);
    }
    cout << m - din.solve(2 * n,2 * n+1)<< " ";
    // max
    ans = 0;
    vector<bool> ch(m,0);
    for(int i = 0;i < m;++i)
        if(!ch[uf.root(i)]) {
            ans += uf.size(uf.root(i)) - 1;
            ch[uf.root(i)] = 1;
        }
    return ans;
}

JAG夏合宿2019参加記

番外編

1日目

1日目からポンコツをたくさんしました。


目的地に向かう途中、goodbatonさんに声をかけていただき、一緒に向かうことになりました。前方にbeetさんがいらっしゃったので、右も左もわからない自分はただついていくだけの人になりました。

このツイート、あたかもbeetさんとお話をしたかのようにツイートしていますが、同じエレベーターに乗っていただけで、beetさんと、そのときに一緒にいらっしゃった方(お名前を知らなくてごめんなさい)とは一切お話できていません...(悲しい)

コンテストは、3日とも同じ大学の後輩であるHyado君、Sen君と「Prime_turtle」というチームで出ました。僕と、後輩二人のICPC予選の際のチーム名を少しずつ取り出して合わせたものです。
1日目の予定としては、はじめに僕がA、Sen君がB、Hyado君がCを解く予定でした。
ですが、僕がAを誤読したため何もできず、Hyado君に丸投げをして、代わりにHyado君のCを横取りしました。
A問題でとてつもない時間がかかったため、そのままA~Cの3完で終わりました。
Jの考察があと一歩だったので少し悔しいです。

コンテスト後もポンコツムーブをしました。
お風呂にあるコインロッカーのお釣りの100円を取り忘れたり、着替えのズボンを前後反対に履いたりしました。


2日目


この日は、Eをまず自分が解き、その後AをHyado君が通しました。
そして、Dを僕とSen君の2人で、Iを僕とHyado君の2人で通し、何とか4完をすることができました。
Dの計算量を落とすパートをSen君がやってくれたり、Iの実装の大枠や、細かい部分の指摘をHyado君がやってくれたりしたので助かりました。
I問題は自分が書いた繰り返し二乗法がバグっていて、ACするのに時間がかかりました。TTPCでも繰り返し二乗法の実装が蟻本と違って効率が悪く、大学の先輩に笑われたのですが、リベンジができませんでした…

昼寝をした後、懇親会に参加しました。初めは早稲田の人達でかたまっていたのですが、さすがにかたまりすぎるのもよくないと思い、後半はNOSSさん、こたつがめさん、まほろばさん、もりをさんとお話をしました(途中でてぃーいけさんが挨拶をしに来ていた気もします)。
今思い返すと、隙あらば自分語りをしていたような…？
直接お会いしたことがなくても、認知をされていたりして嬉しかったです。
ちょうど、懇親会後のABCでNOSSさんが黄色になっていたのでおめでたかったです(ルームメイトのidsigmaさんと、先を越されて悲しい、みたいな話をしたのは内緒です)。自分はテザリングを当日の朝に利用可能にして出場したのですが、レートが溶けました…
テザリング費用を払ってレートを溶かしたことになったので悲しいです。

3日目


3日目は、Hyado君がA、自分がB,Cを書きました。
BはSen君が詰まっていたので途中で交代したのですが、思いついた解法を投げて、自分が後半部分の考察にまわればよかったのかなぁと思いました(Sen君の実装が3日を通して少なかったのと、おそらく3人の中では自分が一番問題を解ける可能性が高かったため)。

感想

参加している人の層がかなり上の方(なイメージ)だったので、そこにくらいついていくのに必死だったのと同時に、やっぱりすごいなぁと思いました。
名前だけしっていて勉強するのをサボっている部分がピンポイントで出てきたりしているので、精進不足を実感しました…
あのレベルの問題をぽんぽん解けるようになりたいですね(これいつも言っているような気がします！)

ABC132 F - Small Products

動的計画法(DP)

問題
提出コード

解法

dp1[i][j] = i番目にjを置くような数列の場合の数(ただし、j \leqq \sqrt{N} )
dp2[i][j] = i番目に、xj \leqq N \lt x(j+1)を満たすようなx( x \gt \sqrt{N})を置く数列の場合の数
とします。
\sqrt{N}以下で最大の整数をp、xj \leqq N \lt x(j+1)を満たすようなx( x \gt \sqrt{N})の個数をc_{j}とすると、それぞれ次のように遷移を行うことができます。
\displaystyle dp1[i + 1][j] = \sum_{s = 1}^{p} dp1[i][s] + \sum_{m = j}^{p}dp2[i][m]
\displaystyle dp2[i+1][j] = \sum_{s = 1}^{j}dp1[i][s] \times c_{j}


あとは、全てΣの形になっているので、この部分を累積和で高速化することにより、dp1[k][j],dp[k][j]の総和が答えとなります。
初期値はdp1[0][1] = 1、それ以外が0です。

ABC128 F - Frog Jump

未分類

問題
提出コード

解法

A - B = Xとすると、実際の遷移は図のようになります。
f:id:emtubasa:20190821225843p:plain
ということで、距離Xおきに、前からk個、後ろからk個の蓮の得点を得ると決めた時のAは自動的に決まります。
Xをある値に固定したとき、kはだいたいN/X個の候補が存在し、Xについて全探索を行ってもO(N log N)におさまります。この全探索は、kが小さいパターンから順に、距離Xごとに前後から得点を足していくことで、十分高速に計算することができます。
あとは、A,Xが条件を満たす部分(つまりA \gt X)について全探索を行えば、その中で最も得点が高かったものを選ぶことで答えが求まります。
N-1がXで割り切れるときのみ注意が必要です。このパターンでは、前から見ている蓮と後ろから見ている蓮が被った、もしくは交差した時点で探索を終了する必要があります。

感想

今回ほぼ自力で解くことができたのですが、当時、F問題に十分時間を割けていたらどうだったのでしょうか…