ツバサの備忘録

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

AOJ 1232 - Calling Extraterrestrial Intelligence Again

問題
提出コード

問題概要

3つの整数m,a,bが与えられます。
pq \leqq mかつa/b \leqq p/q \leqq 1となるような(p,q)のうち、pqが最大となるようなペアを求めてください。
制約は、4 \lt m \lt 100000, 1 \leqq a \leqq b \leqq 1000です。

解法

まずはエラトステネスの篩を利用して、素数を洗い出します。
qについて全探索をすると、pの最適解は、あるqに対して、
p \leqq m/qaq/b \leqq p \leqq qを満たすような最大の素数になります。
ので、二分探索でpの最大値を毎回求め、答えを求めていけばよいです。

のですが、AC後に他の解説ブログを見たところ、m/qという制約のおかげで、pも全探索できるらしいです…ちょうど調和級数の形になりますね。

感想

篩で洗い出す素数の個数を2回間違えました(最初は少なすぎてWAが出て、その後増やしすぎてTLEになりました)…反省します。

ABC142 F - Pure

問題
提出コード

解法

方法は、i番目からi番目に戻ってくるサイズが最小の閉路について、問題の条件を満たしているかどうか調べる、というものです。
これを全てのiについて調べ、存在すればそれを答えればよいです。
何故なら、与えられたグラフの中で、最小のサイズの閉路を見つけると、それが問題の条件を満たすグラフになるからです。
まず、問題の条件を満たす閉路が1つあったとします。
そこに、辺を1つ追加すると、その閉路は問題の条件を満たさなくなってしまいます。
しかし、その閉路についてよく見ると、追加した辺を上手く使うことで、問題の条件を満たすような閉路が必ずどこかに存在しています。

f:id:emtubasa:20190928230144p:plain

例えば、黄色と青の辺からなる、問題の条件を満たす閉路が存在したときに、橙の辺を追加したとしても、黄色+橙の辺と、それにつながってる頂点のみを選ぶことで再び問題の条件を満たす閉路が完成します。
こうして完成した閉路に、適当な頂点と辺を追加したものが問題で入力されるグラフになるので、この一番小さい閉路を探せばよいことになります。
そして、それは上記の方法で求めることができます。
具体的には、閉路を探すパートについてはBFSとその復元(1つ前に通った頂点をメモしておく)を行い、問題の条件を満たすかどうか検査するパートでは、選んだ閉路につながっている辺についてチェックし、どこかで出次数か入次数が2以上になっている頂点が存在しないか見ればよいです。
結果的にはO(N(N+M))ぐらいで解けます。

感想

上手い実装方法がわからなかったのでこうなりましたが、バグなくかけたのでまぁ良かったです。

ABC142 E - Get Everything

問題
提出コード

解法

制約がbitDPをしろと言っているので、bitDPをします。
dp[S] = 現在開けた宝箱の状態がSのときに、そこからかかる費用の最小値
とします。
Sを整数型の変数1つで表し、2進数の桁に宝を割り振り、0:まだ開いていない、1:開いている、とすると
初期値はdp[2^{N}-1] = 0で、答えはdp[0]です。
dp[S]を求めることについて考えると、
状態がSの際にi番目の鍵を使うと、S \cup T_{i} (ただし、T_{i}i番目の鍵を使用して開けることのできる宝箱の集合)
となります。
鍵はM種類あり、これを全部試せばよく、
dp[S] = min(dp[S \cup T_{i} ] +a_{i})
となります。S \cup T_{i} = Sのパターンは注意する必要があり、スルーしなければなりません。
あとはこれを繰り返せば答えが求まります。
O(2^{N}MN)なのですが、T_{i}を前計算してあげるとO(2^{N}M)になります(自分は前計算してないです)

感想

久々にbitDPを見た気がします…
やっぱりbitDPに関しては再帰で書くのが個人的には好きです

会津大学競技プログラミング合宿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アンインストールしたわ!w」とつぶやく
  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 NP_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

問題

問題概要

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;
}