ACLを入れてAtCoder Library Practice Contestを解いてみる Part1(A~D)

https://atcoder.jp/posts/517
Atcoderに大きな変更点がありました。
UnionFind等のC++の標準関数にないデータ構造等がACLとして提供され、コンテスト中に使えるようになりました。

SNSでは賛否両論?な感じですが、個人的には賛成です。
そもそも、プログラミングの思想的にデータ構造とかはパッケージ化して、コーディングする人は知らなくても利用できることがGoodなはずです。(実際、std::sortは使うけど、動きは知らないって人多いと思います。私もよく知りません)
そういった意味で、こういうことが出来るっていう関数が提供されるのは割と普通なのかなと思います。
(とはいっても、データ構造を一つずつ覚えてライブラリを整備するのが競プロの醍醐味って思いもあります。どうなんでしょうね?
そういう楽しみは、CodeForcesとかに任せてAtcoderでは別の楽しみをすればいいだけと思いますが....。)

・ACLをローカル環境に入れる

手元で動かすために、ローカル環境で使えるようにします。
今回、QtCreatorというIDEを使って作業していますが、他のIDEでも概ね変わらないと思います。

公式サイトよりzipを落とす
→zipを解凍して、中にあるatcoderファイルを好きな場所に置く
→"atcoder/~~.h"でincludeできるようパスを通す
 Qtcreatorの場合、.proのINCLUDEPATHを追加すればいいです。

INCLUDEPATH += "C:\Users\nullkara\Desktop\ac-library"

後はcppファイルで

#include<atcoder/all>
using namespace atcoder;

とかって書けば使えます。
allはACL全部てんこ盛りのもので、これをincludeすれば一先ず全部使えます。using namespaceはいつもの名前空間省略です。
ただ、標準関数と名前がぶつかるって事はないと思いますが、自作関数等を使う場合は注意です。状況に応じて、includeを減らしたり、using namespaceを削ったりして衝突をなくしましょう。

あと、コンパイルするためには-std=14か17のオプションがいります。忘れずにつけましょう。
QtCreatorなら.proに

CONFIG += c++14

とかって書けばいいです。
私の環境ではMinGW 64bit 7.3.0で動きました。

・A - Disjoint Set Union

実際に使って解いてみます。
私はDSUに聞き覚えがなかったのですが、(多分)UnionFindのことです。
.zipにある.htmlのマニュアルを読みながら実装します。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int Q,N;
   cin>>N>>Q;
   dsu ds(N);
   for(int i=0;i<Q;i++){
       int t,u,v;
       cin>>t>>u>>v;
       if(t==0){
           ds.merge(u,v);
       }
       else{
           cout<<ds.same(u,v)<<endl;
       }
   }
}

mergeで辺の追加、sameで同じグラフかどうか判定します。
提出するとき、ACLを使う用の言語選択があるので注意しましょう。

・B - Fenwick Tree

BITのことですね。
私のセグ木ライブラリと違ってl~r-1区間の操作なのでちょっと使いにくいです(こっちのが一般的?)

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int N,Q;
   cin>>N>>Q;
   fenwick_tree<long long> fw(N);
   for(int i=0;i<N;i++){
       int a;
       cin>>a;
       fw.add(i,a);
   }
   for(int i=0;i<Q;i++){
       int a,b,c;
       cin>>a>>b>>c;
       if(a==0){
           fw.add(b,c);
       }
       else{
           cout<<fw.sum(b,c)<<endl;
       }
   }
}

intだとoverflowします。

・C - Floor Sum

??????????
(a*i+b)/mの切り捨ての0~Nまでの和を求める。
ずばり、これを解くものがあるので使う。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int T;
   cin>>T;
   for(int i=0;i<T;i++){
       long long N,M,A,B;
       cin>>N>>M>>A>>B;
       cout<<floor_sum(N,M,A,B)<<endl;
   }
}

シグマがあるのでO(N)っぽいけど、O(log(max(A,M)))らしい。(黒魔術が過ぎる)
役割がいまいち不明だけど、どうやらy=(Ax+B)/M(y>=0,N>=X>=0)のyより下の格子点の数を求めるらしい。
覚えといて損はなさそう...なのかな?

・D - Maxflow

最大フローの問題。最小カットとか、二部グラフの最大とかのやつ。
この問題、今までと毛色が変わってライブラリを貼るだけでは解けなくなっています。

"."であるマスに注目した時、その周辺4マスの"."であるマスにまたがってブロックが置ける可能性があります。また、置いた別のマスは使えなくなってしまいます。
置く=グラフの辺を付けるとするとマッチング問題っぽくなりそうです。さらに、各マスは各マスの隣り合うマスしか影響を与えないことを考えると、市松模様の白黒で分けることにより、二部グラフの最大マッチングになりそうですね。

よって以下の手順で解けます。
・市松の白と黒で二部グラフを作り、s,tから辺を伸ばす。
・市松の白と黒から、違う色をまたがっておける場合、辺を追加する
・最大流が置けるブロック数の最大
・流量が1である辺(最大流として使われた辺)が実際に置いたブロックなので、そこから復元する。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int N,M;
   cin>>N>>M;
   string S[N+2];
   for(int i=1;i<=N;i++){
       cin>>S[i];
       S[i]="#"+S[i]+"#";
   }
   S[0]="";
   S[N+1]="";
   for(int i=0;i<M+10;i++){
       S[0]+="#";
       S[N+1]+="#";
   }
   mf_graph<int> g(N*M+2);
   int s=0;
   int t=N*M+1;
   for(int i=1;i<=N;i++){
       for(int j=1;j<=M;j++){
           //cout<<"----"<<i<<","<<j<<endl;
           int ij=(i-1)*M+j;
           //cout<<ij<<endl;
           if(S[i][j]=='.'){
               if((i+j)%2==0){
                   //cout<<s<<","<<ij<<endl;
                   g.add_edge(s,ij,1);
                   int dx[]={0,0,1,-1};
                   int dy[]={1,-1,0,0};
                   for(int k=0;k<4;k++){
                       if(S[i+dy[k]][j+dx[k]]=='.'){
                           int ij2=(i-1+dy[k])*M+j+dx[k];
                           //cout<<ij<<","<<ij2<<endl;
                           g.add_edge(ij,ij2,1);
                       }
                   }
               }
               else {
                   //cout<<ij<<","<<t<<endl;
                   g.add_edge(ij,t,1);
               }
           }
       }
   }
   cout<<g.flow(s,t)<<endl;
   vector<mf_graph<int>::edge> ge=g.edges();
   for(int i=0;i<ge.size();i++){
       int fl=ge[i].flow;
       int to=ge[i].to;
       int fr=ge[i].from;
       int tx=(to-1)%M+1;
       int ty=(to-1)/M+1;
       int fx=(fr-1)%M+1;
       int fy=(fr-1)/M+1;
       if(fl!=0&&s!=fr&&t!=to){
           //cout<<fx<<","<<fy<<","<<tx<<","<<ty<<endl;
           if(fx+1==tx){
               S[fy][fx]='>';
               S[ty][tx]='<';
           }
           if(fx-1==tx){
               S[fy][fx]='<';
               S[ty][tx]='>';
           }
           if(fy+1==ty){
               S[fy][fx]='v';
               S[ty][tx]='^';
           }
           if(fy-1==ty){
               S[fy][fx]='^';
               S[ty][tx]='v';
           }
       }
   }
   for(int i=1;i<=N;i++){
       for(int j=1;j<=M;j++){
           cout<<S[i][j];
       }
       cout<<endl;
   }
}

Atcoder的にやりたかった問題(面白いけど、ライブラリの有無で出しにくい)って感じの問題でした。

・続きは次回

ライブラリ貼るだけなので、全部解こうと思っていましたがDに時間がかかりました...。E以降は次回やります。
来週のACLコンテストまでにLまで解きたいところです。(今週末のABCにも試しで使ってみたいですね...)

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