ABC205 解説
AtCoder Beginner Contest 205 の解説記事です。私は2100点(43:06)25位でした。
A - kcal
思考
一般的な比の問題です。誤差や出力方式にだけ気をつけましょう。自分は小数出力の時は何も考えずにsetprecision(20)を付けていますが、失敗したことはないです。入力は整数ですが、どうせ浮動小数点数で扱うので、最初からdoubleで受け取っています。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ double a, b; cin >> a >> b; cout << setprecision(20) << a/100.0*b << endl; }
B - Permutation Check
思考
ある2つの数列が、一方の並び替えによって他方が得られるための必要十分条件は、2つの数列をソートした列が一致することです。今回は片方の数列はすでにソートされているので、Aをソートして(1,2,...,N)と一致するかを確認すれば良いです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(auto&i:a) cin >> i,--i; sort(begin(a),end(a)); for(int i{};i<(n);++i){ if(i!=a[i]){ cout <<"No" << endl; return; } } cout << "Yes" << endl; }
C - POW
思考
Cが奇数のときはAとBの大小を、Cが偶数のときはAの絶対値とBの絶対値の大小を比較すれば良いです。ちゃんと証明しようとすると若干大変ですが、偶数のときは割と明らかで、奇数のときは符号に気をつければ割と明らかです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c; cin >> a >> b >> c; if(c%2){ if(a==b) cout <<"="; else if(a<b) cout<<"<"; else cout<<">"; } else{ if(abs(a)==abs(b)) cout <<"="; else if(abs(a)<abs(b)) cout<<"<"; else cout<<">"; } cout<<endl; }
D - Kth Excluded
思考
これどうやってもできそうに見えるんですが、丁寧にやらないと実装が破滅したり、下手したらTLEしそう、かなり厄介な問題だなぁという気持ちになります。
多少遅くてもTLEしないなら実装を簡単なの方法を考えます。最初に思いついたのは、二分探索です。K番目を求めるのは難しいですが、Xが何番目かを求めるのはそこそこ簡単なので、実際この方針でもできると思います*1。ですが、2分探索2回することになり、めんどいので、やめます。
の区間では、数が1増えると、番目も1増えるので、どの区間に属しているかと、
が何番目かがわかればすぐに計算できるので、これをmapを利用して実装します。最初にこの方針が直感的に生えたんですが、実装めんどそうで棄却しちゃったんですが、やりたいことを整理したら、思ったよりも綺麗にかけることに気づきました。
実装例
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n,q; cin >> n >> q; vector<ll> a(n); for(auto&i:a) cin >> i; map<ll, ll> mp; mp[0]=0; for(int i{};i<(n);++i){ mp[a[i]-i] = a[i]+1; } for(ll _{},k;_<(q);++_){ cin >> k; auto it = mp.upper_bound(k); --it; cout << it->second + k-it->first << '\n'; } }
E - White and Black Balls
思考
i=N+Mの時点で条件を満たさないような場合は並べる方法は存在しません。以下並べる方法は存在するとします。
グリッドグラフを(0,0)から、右にN回、上にM回移動することで(N,M)に移動する問題を考えます。この設定で、右下の一部に侵入できないとした時の、移動の仕方の総数が求めるものです。
ここで、余事象を考えます。つまり右下に侵入してしまう場合を考えます。侵入してしまった場合の経路を、初めて侵入した位置で、下図のように折り返すことで、(0,0)から(M+K+1, N-K-1)への経路と1対1対応させることができます。
よって存在する場合は
通りとなります。
これ最近似たような話( (N,M)のカタラン数みたいな)をチームの人達と話したときに、この手法を聞いてなかったら、かなり沼っていた気がします。まあまともに考察しなくても、実験でエスパーできる範囲だとは思います。
実装例
#include<bits/stdc++.h> using namespace std; template <class Mint> struct combination; //二項係数の構造体 int main(){ int n, m, k; combination<modint1000000007> comb(2000001); cin >> n >> m >> k; if(n>m+k){ cout << 0 << endl; } else{ cout<<(comb(n+m, n)-comb(n+m, n-k-1)).val() << endl; } }
F - Grid and Tokens
思考
典型キーワードは「こんなんフローしかないやろ」です。制約が小さく、いわゆる多項式時間ならなんでも通る問題*2で、問題も明らかにマッチングっぽいので、流石にフローです。
ただどうフローを流すかは、結局天才構築か、経験によるパターンマッチング(激ウマギャグ)か、天啓を待つなどして思いつく必要があります。
グリッドのマッチングは、列や行をノードとして、ソースから行ノードに1流す、列ノードからシンクに1流す、とすることで、各行各列に1つだけしかマッチングできなくできます。さらに、マッチングできる行と列の対応は、駒に従います。1つの駒で1つのマッチングしかできないので、駒ノードは2つ作り、その2つの間に1だけ流すなどとやればできそうです。
こんな感じでフローと戯れていると、最終的に下図のようなフローの最大流が答えになることがわかります。
あとはACLを使って、丁寧に辺を張ればOKです。
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; int main(){ int h,w,n; cin >> h >> w >> n; int s=2*n+h+w, t=s+1; mf_graph<int> g(t+1); for(int i{};i<(h);++i){ g.add_edge(s,2*n+i,1); } for(int i{};i<(w);++i){ g.add_edge(2*n+h+i, t, 1); } for(int i{},a,b,c,d;i<(n);++i){ cin >> a >> b >> c >> d;--a,--b; for(int j{a};j<c;++j) g.add_edge(2*n+j, 2*i,1); for(int j{b};j<d;++j) g.add_edge(2*i+1, 2*n+h+j,1); g.add_edge(2*i, 2*i+1, 1); } cout << g.flow(s, t) << endl; }
終わりに
図を使った解説記事、初めて書いた気がします。雑な手書きでごめんなさい。コンテスト中にちゃんとした描画ソフトで解説書くのは難しいです。
