ACLを入れてAtCoder Library Practice Contestを解いてみる Part2(E~J)

前回の続きから解いていきます。

・E - MinCostFlow

最小費用流です。Dの最大流と似ていますが、少し違います。
・最大流 フローに流せる最大
・最小費用流 フローに、ある値を流すときのコストの最小

今回の問題はN*Nのグリッドに数字が書かれていて幾つか数字を選択し、任意の列と行の選択された数がK個以下になるようにする。
この時、選択した値を最大化せよ。
一見すると最小費用流っぽくないですね。

K個以下を選ぶを、流量をKまで流すフローを考えるとします。
具体的には、N=3の時に以下の頂点を持つ二部グラフを考えます。
・スタート地点のS
・列を頂点とするX1~XN
・行を頂点とするY1~YN
・ゴール地点のT
Sから各X1~XNへ、各X1~XNへ、各Y1~YNからTへとN+N*N+N個の辺を伸ばします。この時、最大流量をs->XとY->tはK、それ以外は1とします。(それぞれの列と行は最大K個まで選べる。各マスを1個選ぶ。が表現される。)
s->Xi->Yj->tのフローはi列目j行目を選んだことになるので、a->bのコストはaijの値を入れればいいです。
ただ、最小費用流なのでここのままでは最小値が答えになります。
大きな値(aijの最大値よりも大きく、最終計算の結果がオーバーフローしない、良い感じの値)からaを引いた値を設定することで、無理やり最小で最大を解くようにします。
なお、s->X,t->Yへの辺のコストは0とします。(ここは、アルゴリズムの仕組み上付けているだけなので、計算結果に影響しない値にする)

こうすることで何が嬉しいかというと、流量N*Kの最小費用流を求めることで、K個以下が表現できます。

※K=2で、X1->Y2,X2->Y2,X3->Y3と選んだ場合(2行目の選択数が3)、Y->tの最大流量がK=2なのですが、Y2には流量3あります。コストを最小にする場合、どれか一つ削って流量2にした方がよさそうです。
 K=2で、X2->Y1,X2->Y2,X2->Y3と選んだ場合(2列目の選択数が3)、s->Xの最大流量がK=2なので、Xiは全てのYに流量1を送れません。コストを最小にする場合、どれか一つ削って流量2で送れる数にした方がよさそうです。
 と、Kより多く選んだ場合、コストが超過してしまう(無駄になる)ことが分かります。
 なお、入力例 2のようにK個選ばない方が最小であるパターンがあります。
 これは、選ばない=aijが0の列と行を選んだと考え、s->tに最大流量INF、コスト大きな値の辺(コスト0)を別途追加し、これに流すことで表現します。

上記グラフから最小費用を求め、大きな値で無理やり最小にした分を調整した値が答えになります。(n*k(大きな値-a)になっているはずなのでn*k*大きな値から最小費用を引けばよい)
以下コードです。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   long long N,K;
   cin>>N>>K;
   long long ABIG=LLONG_MAX/(N*K+10);
   mcf_graph<long long,long long> mcf(N*2+2);
   int s=0;
   int t=N*2+1;
   for(int i=0;i<N;i++){
       for(int j=0;j<N;j++){
           int a;
           cin>>a;
           mcf.add_edge(i+1,N+1+j,1,ABIG-a);
       }
   }
   for(int i=0;i<N;i++){
       mcf.add_edge(s,i+1,K,0);
       mcf.add_edge(N+1+i,t,K,0);
   }
   mcf.add_edge(s,t,LLONG_MAX,ABIG);
   pair<long long,long long> ans=mcf.flow(s,t,N*K);
   cout<<N*K*ABIG-ans.second<<endl;
   //cout<<ans.second<<","<<ABIG<<endl;
   vector<mcf_graph<long long,long long>::edge> eg=mcf.edges();
   for(int i=0;i<N;i++){
       for(int j=0;j<N;j++){
           bool f=false;
           for(int k=0;k<eg.size();k++){
               //cout<<eg[k].from<<","<<eg[k].to<<","<<eg[k].flow<<endl;
               if(eg[k].from==i+1&&eg[k].to==j+N+1&&eg[k].flow==1){
                   f=true;
               }
           }
           if(f) cout<<"X";
           else cout<<".";
       }
       cout<<endl;
   }
}

ACLリファレンスのMinCostFlow.hrmlのソースから解法を逆算したのですが、こんなの思いつけって無理じゃないですか????

・F - Convolution

問題に書いてある式を0<=i<=N-1+M-1すべて解く問題。
シグマの式に書かれていませんが、aiやbiが未定義である場合は0が入るそうです。
この式は、畳み込みと言われているもので、競プロでのFFT(高速フーリエ変換)のことです。
ずばりのものがACLにあるので、それを使いましょう。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int N,M;
   cin>>N>>M;
   vector<long long> av,bv;
   for(int i=0;i<N;i++){
       long long a;
       cin>>a;
       av.push_back(a);
   }
   for(int i=0;i<M;i++){
       long long b;
       cin>>b;
       bv.push_back(b);
   }
   vector<long long> ans=convolution(av,bv);
   for(int i=0;i<ans.size();i++){
       cout<<ans[i]<<endl;
       if(i==ans.size()-1) cout<<endl;
       else cout<<" ";
   }
}

制約がやたら変ですが、N,M=524288は畳み込みのO(NlogN)が9961472(≒10^7)になる値です。
998244353は畳み込みによく使われるMODらしいです(理由はいまいち分からなかったです)。メタ読みっぽくなりますが、mod 998244353が問題文にある場合は、畳み込みを考慮に入れてもいいかもしれません。
(と思ったのですが、K問題で関係ないのに998244353が出てきたので、メタ読みあんまりしない方がいいかも(どっち?)

・G - SCC

強連結成分分解(Strongly Connected Component)は、有効グラフでループとなるグループに分けるものです。
SCCするものがACLにあるのでそれを使います。なお、SCC後の結果はソート済みになっているため、変なことをせずにそのまま出力するだけでOKです。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int N,M;
   cin>>N>>M;
   scc_graph ss(N);
   for(int i=0;i<M;i++){
       int a,b;
       cin>>a>>b;
       ss.add_edge(a,b);
   }
   vector<vector<int>> ans=ss.scc();
   cout<<ans.size()<<endl;
   for(int i=0;i<ans.size();i++){
       cout<<ans[i].size()<<" ";
       for(int j=0;j<ans[i].size();j++){
           cout<<ans[i][j];
           if(j==ans[i].size()-1) cout<<endl;
           else cout<<" ";
       }
   }
}

このコードを実行すると、出力例が若干違うと思いますが問題ありません。
問題文にあるトポロジカルソートは、ループを一周辿った時の順番通りということで、スタートはどこでも良いです。
例えば、
5 1 2 3 4 5
5 3 4 5 1 2
上記二つの出力は、(1->2->3->4->5->->先頭へ)というループにおいて、どちらもソート済みとなります。

・H - Two SAT

SATとはsatisfiability(充足可能性問題)のことで、Wikiによると

一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。

とのこと。今回の場合、各Xiと各YiでのSAT(リテラルが二つ)となるため、2-SATとなるそうです。
細かいアルゴリズムは省く(僕もよく知らない)のですが、以下の手順で解けます。
・2*N個の頂点を持つグラフを作成する。(各XYiの真と偽の頂点)
・Xにフラグを置く場合をtrue、Yにフラグを置く場合をfalseとして、2点間に対してフラグの距離がD未満の場合は辺を付ける(有向グラフを作る)
・SCCする
・トポロジカルの順序を見て、何やかんやすると分かる!!
これらの操作を裏でやってくれるものがACLにあるので、それを使って解きます。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   long long N,D;
   cin>>N>>D;
   long long X[N],Y[N];
   for(int i=0;i<N;i++){
       cin>>X[i]>>Y[i];
   }
   two_sat ts(N);
   for(int i=0;i<N;i++){
       for(int j=i+1;j<N;j++){
           long long pat1=abs(X[i]-X[j]);
           long long pat2=abs(X[i]-Y[j]);
           long long pat3=abs(Y[i]-X[j]);
           long long pat4=abs(Y[i]-Y[j]);
           //cout<<i<<","<<j<<"---"<<pat1<<","<<pat2<<","<<pat3<<","<<pat4<<","<<D*D<<endl;
           if(pat1<D) ts.add_clause(i,true,j,true);
           if(pat2<D) ts.add_clause(i,true,j,false);
           if(pat3<D) ts.add_clause(i,false,j,true);
           if(pat4<D) ts.add_clause(i,false,j,false);
       }
   }
   if(ts.satisfiable()){
       cout<<"Yes"<<endl;
       vector<bool> v=ts.answer();
       for(int i=0;i<v.size();i++){
           if(!v[i]) cout<<X[i]<<endl;
           else cout<<Y[i]<<endl;
       }
   }
   else cout<<"No"<<endl;
}

※どうでもいい話ですが、入力の変数がxとyなので二次元平面考えていました。(二本の数直線上に置く)
 元問題であると思われるFlagに一直線上と書かれていて、誤読に気付きました。

・I - Number of Substrings

接尾辞配列(suffix array)や最長共通接頭辞(LCP)の問題。
接尾辞配列とは、先頭から削ってできた文字列を辞書順に並び替えたもの。例えばnullkaraなら、
a,ara,kara,lkara,llkara,nullkara,ra,ullkara
となります。これに対して隣り合う文字列同士の先頭何文字が共通かを配列にしたものがLCPです。

部分文字列の種類を答える問題になんで関係あるの?という話ですが、結論から言うと部分文字列の総和からLCPの[1,n)区間の数の和を削ったものが答えになるからです。
※入力例 1 abcbcbaで考える
suffix array=a,abcbcba,ba,bcba,bcbcba,cba,cbcba
このときのLCPについて考えます。
bcbaとbcbcbaのLCPは3です。なので、"b","bc","bcb"の3パターンが重複することが分かります。
上記のように、suffix arrayが辞書順であることを利用して、LCPから重複数が判明します。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   string S;
   cin>>S;
   vector<int> vsa=suffix_array(S);
   vector<int> vlc=lcp_array(S,vsa);
   long long sum=0;
   for(long long i=0;i<vlc.size();i++){
       sum+=(i+1)-(long long)vlc[i];
   }
   cout<<sum+S.size()<<endl;
}

・J - Segment Tree 

セグ木です。ACLのセグ木はかなり育っていて、抽象化まで扱えるようです。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int segop(int a,int b){
   return max(a,b);
}
int sege(){
   return -1;
}
int segfn;
bool segf(int v){
   return v < segfn;
}
int main(){
   int N,Q;
   cin>>N>>Q;
   segtree<int,segop,sege> seg(N+1);
   for(int i=0;i<N;i++){
       int A;
       cin>>A;
       seg.set(i+1,A);
   }
   for(int i=0;i<Q;i++){
       int t,x,v;
       cin>>t>>x>>v;
       if(t==1){
           seg.set(x,v);
       }
       if(t==2){
           cout<<seg.prod(x,v+1)<<endl;
       }
       if(t==3){
           segfn=v;
           cout<<seg.max_right<segf>(x)<<endl;
       }
   }
}

抽象化、いまいち使いづらいですね...。
二分探索を使う際に、渡してある関数の中身の変数を二分探索前に書き換えないといけないのが何だかなぁという感じです。
単純な好き嫌いの話ですが嫌いです。やっぱり、セグ木に関しては自分でチューニングした方が良さそうです...。

・続きは次回

あとは遅延セグ木の問題二つだけなのですが、ACLの遅延セグ木のコンストラクタ
lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
を見て、やる気が削がれたので一旦辞めます。(朝7時から5時間くらいぶっ通しなので、さすがに疲れました。)

Two SATは初めて聞いたアルゴリズム?(問題?)でしたし、SCCやLCPは名前こそ知ってはいましたが、考え方等は今回初めて知りました。
そういった意味でも、ACLを試す以外にAtCoder Library Practice Contestを埋めたことは、かなり大きい意味があったと思います。

この記事が気に入ったらサポートをしてみませんか?