ABC106 AtCoder Express 2
解く前に考えていたこと
区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。
実装の際に盛大にバグらせたので戒めとして書きました。
解法
+ クエリ先読みのオフラインアルゴリズムというらしい
#include<bits/stdc++.h> using ll = long long; #define rep(i,n) for(int i=0;i<n;i++) #define erep(e,v) for(auto && e :v) #define all(in) in.begin(), in.end() #define INF (sizeof(int) == 4 ? 1e9:1e18) using namespace std; template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} } using pii = pair<int,int>; using piii = pair<int,pii>; int bit [1000] = {},n; int sum(int i){ int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add (int i,int x){ while (i <= n) { bit[i] += x; i += i & -i; } } signed main(){ int m,q; cin >> n >> m >> q; vector<piii>v( m + q); rep(i,m+q) { int a,b; cin >> a >> b; piii temp; temp.first = a, temp.second.first = b; temp.second.second = i; v[i] = temp; } sort (all(v),[](auto const x,auto const y) { return ( x.second.first < y.second.first or (x.second.first == y.second.first and x.second.second < y.second.second) ); }); int ans[100000] = {}; erep(e,v){ int left = e.first; int right = e.second.first; bool isQuery = e.second.second >= m; int index = e.second.second - m; if (isQuery){ ans[index] = sum(right) - sum (left - 1); } else { add(left, 1); } } rep(i,q) cout << ans[i] << endl; }
9/6 追記
一応segtreeの解答も載せておこうかな
https://beta.atcoder.jp/contests/abc106/submissions/3096327
ABC038 D - プレゼント
問題概要
解く前に考えていたこと
・AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がで解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にあるのLISを書くがWA
・途中でpair型dpを更新していた。
正解
まず前提として、プレゼントがプレゼントの中に梱包される条件とは、
> > が成立することである。
プレゼントの順番は自由に並びかえることができるので、ソートして考えるのが良い。
を昇順にソートして に関してLISを考えればうまくいきそう。
以下,二分探索で、番目の要素の更新位置を探す解法を考える。
・番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素は番目()とする。
・このとき、が成り立っていると、となっているため、上書きできない。(直感的に説明すると、番目の要素の方が番目の要素より条件が厳しい)
逆に言えば、のときとなっていれば、通常通り更新することができる。
追記
6/10 別解で解いたので、その解法を載せる.
通常のLISと同じく、lower_boundを用いて更新していく(ただし、今回はpair型のdp)。
更新する位置は、以上の要素がある部分である。
さて、この問題でより真に大きいとは、 && が成り立つことである。
さらに, 以上とは、 or となる。なので、適当に二分探索して置き換える位置を探す。
この定義を採用すると、同値のまたはの更新時に厄介なことになる。よって最初の同じく、比較関数をよしなにしてソートすること。
lower_boundといっておきながら普通の二分探索の理由は、また比較関数を書き換えないと行けないので。(比較関数を書き換えたver)
#include<bits/stdc++.h> using namespace std; using Int = long long; constexpr Int inf =1e18; template<class F, class T> auto minimize(T imin,T imax,F &f){ while(imax - imin > 1){ T mid = imin + (imax - imin)/2; if(f(mid)) imax = mid; else imin = mid; } return imax; } int main(){ int N; cin >> N; vector<pair<Int,Int>>v(N); for(auto& p : v) cin >> p.first >> p.second; sort(v.begin(),v.end(),[&](const auto& l, const auto& r){ if(l.first == r.first) return l.second > r.second; return l.first < r.first; }); pair<Int,Int>p; vector<pair<Int,Int>>dp(N,make_pair(inf,inf)); auto f = [&](int mid){ return dp[mid].first >= p.first or dp[mid].second >= p.second; }; for(int i = 0; i < N; ++i){ p = v[i]; int id = minimize(-1,N - 1,f); dp[id] = p; } cout << count_if(dp.begin(), dp.end(), [&](auto p){ return p != make_pair(inf,inf); }) << endl; }
VimでIndentlineが動かなかった話
VimでIndentlineが動かなったのでメモ。
調べてみると、githubのIssueで報告されていました。
github.com
以下日本語でもメモを残しておきます。
まずターミナルで
vim --version
を実行します。すると、以下のような画面が現れるはずです。
ここで、-conceal となっているのが問題です*1。vimを入れ直しましょう。(画像では+になっています。)
brew install vim
を実行して新しいVimを入れ直します。後は.bashrcにaliasを貼ると完成です。
以下の記事を参考にしていただけるとわかりやすいと思います。
qiita.com
qiita.com
ICPC 2018国内予選
国内予選に後輩(わたあめくん)と先輩とともに参加しました。
開始1時間前
大雨の影響で大学までの電車がなかったので、大阪の別キャンパスで参加することになる。
yebiが到着 → アナウンス「全館4時半で閉館です☆」(は?)
わたあめくんと合流して、帰宅難民向けに開放された食堂か近くのイ○ンの中にあるカフェのどちらかで参加しようとする。
先輩と合流してカフェのほうがおしゃれなのでカフェですることになる。このとき16:20。なんだこれは。
コンテスト
・開始してC問題を見る。累積和見るだけでしょとなる。
・気がつくと後輩がAを通す。プロ
・後輩にCを説明すると、累積を見るだけではヤバイことがわかる。bの制約的にしゃくとり法も間に合わなさそうで考察が振り出しに戻る。
・後輩がトイレに行ってる間に、bがN個に分割できるかどうか判定できることに気づく。後輩に伝えて実験してみると行けそうとなったので方針が固まる。
・Bが虚無そうだった。途中でBと交代してCを書く。5分ぐらいで書いてAC。
・先輩にBを任せてDを二人で考える。
・なんやこの制約、どうせ全探索やろ。
・いいえ、後輩くんに実装を任せてサンプルを試すも、実行時間が長すぎる。でもDPできなさそうなので迷う。
・よく考えると、勝利数は(N-1)/2の場合しかないことに気づく。枝刈りする。
・それでも間に合わない。
・先輩がBを通す。プロ
・Dをいろいろ考えてるうちにコンテストが終わった。
感想
後輩、先輩と自分のレートが大きく離れているので、自分の考察力や実装力で劣るのではないかと考えることが多々ありました(実際その場面はあった。)
ただ、自分の考察の甘いところをすぐに指摘してくれたり、ペアプロする上で、後輩・先輩のコーディングを見ることはとても勉強になりました。チームを組んでくれた先輩・後輩にとても感謝しています。
vectorsのテンプレートを詳しく見る
はじめに
競プロやってると、多次元のvectorをよく使うことがあります。非常に便利なんだけど、宣言がめんどくさい。
例えば、3次元のvectorを宣言しようとすると、
vector<vector<vector<int>>>v(10,vector<vector<int>>(10,vector<int>(10,1000)));
こうなります。
4次元はもう書く気すらなくなってしまいます。しかしvectorsのテンプレートを用いると、
auto v = vectors(10,10,10,3);
このように簡単に書くことができます。
個の引数に対して、最後の数値を初期値として次元のvectorを生成できます。
今回はこのテンプレートを詳しく見ていくことにします(勉強を兼ねて)
vectorsテンプレート
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); } template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
vectorsのテンプレートは2つのvectorsという関数から成り立っています。
これを詳しく見ていきます。
可変引数テンプレート
任意のNについてvectorを生成するので、引数は毎度変化します。
これに対応するために、可変引数テンプレート*1が用いられています。
サンプルコードを見て見ましょう。
#include<bits/stdc++.h> using namespace std; template<class ...Args> void func(Args... arg){ //argの数を表示 cout << sizeof...(arg) << endl; } template<class Head, class ...args> void func2 (Head a,args... b){ cout << a << endl; cout << sizeof...(b) << endl; } signed main(){ func(1,2,3,4,5,6,7,8); func2(1,2.2,"3",'4'); /* output: 8 1 3 */ }
可変引数テンプレートでは、任意の型と任意の引数をテンプレートとして利用することができます。
上記のfunc関数では
・Argsがテンプレートパラメータパック
・argsをが関数パラメータパック
となっています。それぞれ、推論された型、引数が格納されています。
関数内でパラメータパックを用いる際は ... を用いて展開します。
func2に注目してみると、引数として渡された引数が、Head 型の a と args型のbに分割されています。
この関数を繰り返し用いると、やがてargs...の引数は一つになります。
勘がいい方はすでに気づいているかもしれませんが、これは繰り返し処理に用いることができます。
具体例を示します。
#include<bits/stdc++.h> using namespace std; template<class Head, class args> void func2 (Head a,args b){ cout << a << endl; cout << b << endl; } template<class Head, class... args> void func2 (Head a,args... b){ func2(b...); }signed main(){; func2(1,2.2,"3",'4'); /*output 3 4 */ }
複数の引数が渡された関数は、再帰的にfunc2関数を呼び、最後に引数の引数の数は2つになります。
このように、関数をオーバーロードすることで、タグディスパッチによって最適な関数が呼び出されます。
decltypeについて
上記の知識とautoがsyntax sugarであることがわかれば、ほとんど中身が理解できる…かもしれませんが、最後にdecltypeだけ説明しておきます。
decltypeとは、指定した式から型取得する機能です。
#include<bits/stdc++.h> using namespace std; signed main(){ cout << sizeof(decltype(2.2+ 3.4)) << endl; // decltypeはdouble型 cout << sizeof(decltype('a' )) << endl; //decltypeはchar 型 cout << sizeof(decltype(2+1))<<endl; //decltypeはint型 /* output 8 1 4 */ }
vectorsテンプレートでは、decltypeで取得した型とするvectorを返すことで、入れ子構造を達成しています。
*1:任意の数でテンプレートを引数をとれるテンプレートを宣言できる機能
B - Construct Sequences
解く前に考えてたこと
・配列の要素数を超える大きい公差を持った等差数列を考えて、順列による差を相殺したい。
・具体例を考えるも、一般化できずに死亡、特に、入力 の値によって、数列を構築しようとしたのが問題かもしれない。
正解
などとすると、 となる。つまり、添字の値によらず一定である。
問題はもまた単調に増加する数列とする必要があるので、の添字にを足してやる。が巨大なので、問題なく数列を構築することができる。
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() #define MP make_pair #define INF (sizeof(int) == 4 ? 1e9:1e18) #define EPS 0.0000000001 using namespace std; template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); } template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); } template<class T> void join(T a){int b=0;for(auto itr :a){if(b++!=0)cout << " "; cout << itr;} } using ll = long long; using ld = long double; using pii = pair<int,int>; using piii = pair<int,pii>; int W,H; int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);} #define int ll signed main(){ int n; cin >> n; vector<int>p(n); rep(i,n) cin >> p[i]; vector<int>a(n),b(n); int maxi = 40000; rep(i,n){ a[i] = maxi*(i+1); b[i] = maxi*(n-i-1)+1; } rep(i,n){ a[p[i] - 1] += i; } join(a); cout << endl; join(b); cout << endl; }
感想
書いてみると意外と解けそうな気がする。ちなみにWAを量産したのは
この制約を見落としていたため。
M = 1e7 などとすると死にます。
CS Academy No Prime Sum
問題概要
個の相異なる数字が与えられる。2つの和が素数にならないように数字を取り除くときき、最小の数と取り除く数字を答えよ。
解く前に考えていたいこと
・2つの色に彩色したい気分になった。しかし、グラフは木ではない。
・グラフがたくさんできてつらい気持ちになった。
解答
・最小頂点被覆問題。二部グラフを作成し最大流を流すことで、最小点カバーの数がわかる。
・頂点を列挙するには、 において、
から到達不能な の点 から到達可能な
を調べれば良い。
・頂点を調べるにはdfsを書けば良い、(自分はdijkstraを書いた)。
・素数にならない頂点も含めてグラフを作成し、最大流を流すと簡単に結果が得られるが、そうでないと、その頂点が使われたか判別する必要が出て来る(これでバグった)。
→ https://csacademy.com/submission/1570217/
#include<bits/stdc++.h> using ll = long long; #define int ll #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() #define MAX 100000 using namespace std; typedef pair<int, int> pii; typedef pair<int,pii> piii; #define MP make_pair struct Edge{int to,cap,rev;}; bool even(int a){return !(a%2);} class Dinic{//max flow public: int n; vector<vector<Edge> >G;//[MAX]; vector<int> level,iter;//[MAX]; Dinic(int size){ n=size; G=vector<vector<Edge> >(n); } void add_Edge(int from, int to, int cap){ Edge q={to,cap,int(G[to].size())}; G[from].push_back(q); q={from,0,int(G[from].size()-1)}; G[to].push_back(q); } void bfs(int s){ level=vector<int>(n,-1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){ int v=q.front();q.pop(); for(int i=0;i<G[v].size();i++){ Edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; q.push(e.to); } } } } int dfs(int v,int t, int f) { if(v==t)return f; for(int &i=iter[v];i<G[v].size();i++){ Edge &e=G[v][i]; if(level[v]>=level[e.to]||e.cap<=0) continue; int d =dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } return 0; } int mf(int s,int t) { int flow=0; while(1){ bfs(s); if(level[t]<0)return flow; iter=vector<int>(n); int f; while((f=dfs(s,t,INF))>0)flow+=f; } } }; class Prime{ public: vector<bool>flag; vector<int>prime; Prime(int size ){ flag = vector<bool>(size+1,true); for(int i = 2; i < size ;i++){ if(flag[i]){ for(int j = 2;i*j<size+1;j++) flag[i*j] = false; prime.push_back(i); } } } bool IsPrime(int num) {return flag[num];} int IndexOf(int index ) {return (index > prime.size()) ? INF:prime[index-1];} }; template <typename T> void show_with_brank(T a){ int cnt = 0; for (auto itr : a){ if(cnt++ != 0) cout << " "; cout << itr ; } } signed main(){ int n; cin >> n; Dinic fl(n+2); Prime prime(1e5*2); int source = n,sink = n+1; vector<int>v(n); vector<bool>used(n,false); rep(i,n) cin >> v[i]; rep(i,n)rep(j,n){ if(even(v[i]) and prime.IsPrime(v[i]+v[j])){ fl.add_Edge(i, j,1); } if(i == 0 and even(v[j])) fl.add_Edge(source,j,1); if(i == 0 and !even(v[j])) fl.add_Edge(j,sink, 1); } int res = fl.mf(source, sink); set<int>S; vector<vector<Edge>>edge = fl.G; vector<bool>visited(n+2,false); function<void(int)>dfs = [&] (int vertex){ if(visited[vertex])return; visited[vertex] = true; rep(i,edge[vertex].size()){ if(edge[vertex][i].cap)dfs(edge[vertex][i].to); } }; dfs(source); rep(i,n)if((even(v[i]) and !visited[i]) or ((!even(v[i])) and visited[i]))S.insert(v[i]); cout << res << endl; show_with_brank(S); cout << endl; }