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; }
RUPC day3: AA グラフ (AA Graph)
問題概要
https://onlinejudge.u-aizu.ac.jp/#/challenges/sources/VPC/HUPC/2869
アスキーアートでグラフが与えられるので最短経路を求める問題。
個人的にすごく好き。
注意するとこ
○|○○○
○|○G○
○|○○○
この場合はうまく弾かないと行けない。
#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 all(in) in.begin(), in.end() int dx[]={0,0,2,-2}; int dy[]={2,-2,0,0}; int _dx[]={0,0,1,-1}; int _dy[]={1,-1,0,0}; int W,H; bool inrange(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);} using namespace std; typedef pair<int, int> pii; #define MP make_pair signed main(){ char s,t; cin >> H >> W >> s >> t; vector<string>grid(H); vector<vector<pii>>edge(100); map<int,pii>memo; rep(i,H) cin >> grid[i]; rep(i,H)rep(j,grid[i].size()){ if('A' <= grid[i][j] && grid[i][j] <= 'Z' ){ memo[grid[i][j] - 'A'] = MP(j,i); } } for(auto itr : memo){ int vertex = itr.first; pii pos = itr.second; rep(i,4){ pii temp = MP(pos.first+dx[i],pos.second+dy[i]); if(!inrange(temp.first,temp.second))continue; if(grid[temp.second][temp.first] != '-' && grid[temp.second][temp.first] != '|') continue; if(grid[temp.second][temp.first] == '|' && ( i > 1)) continue; if(grid[temp.second][temp.first] == '-' && ( i <= 1))continue; pii now = temp; while(true){ if('A' <= grid[now.second][now.first] && grid[now.second][now.first] <= 'Z' ) break; now.first += _dx[i]; now.second += _dy[i]; assert(inrange(now.first, now.second)); } int next = grid[now.second][now.first] - 'A'; edge[vertex].push_back(pii(next,1)); } } // dijkstra vector<int>d(t,INF); d[s-'A'] = 0; priority_queue<pii,vector<pii>,greater<pii>>que; que.push(pii(0,s-'A')); while(!que.empty()){ pii now = que.top(); que.pop(); if(now.first > d[now.second])continue; rep(i,edge[now.second].size()){ int next = edge[now.second][i].first; if(d[next] < 1 + now.first) continue; d[next] = 1 + now.first; que.push(pii(d[next],next)); } } cout << d[t-'A'] << endl; }
CS Academy Array Removal
問題概要
要素の数列が与えられ、要素のsubarrayが与えられる。
回連続する数列の和の最大値を出力する。ただし、subarrayの番目の数字は使えなくなる。
解く前に考えてたこと
- DP : 不可能そう。使えない数字が出るたびに引くと間に合わない
- StarrySkyTree:区間がどれほど重複してるか数える必要が出てきて、無理となった。
解法
union-findとsubarrayを逆からみていくと良い。
番目の数字を使えるとすると、、番目の要素とuniteしていく。各集合のparentをkeyとする和の配列sumを持っていると良い。
答えとなりうるのは、番目の要素を足す前の最大値か、足した後の和となるので、そのあたりはうまいことやる。
#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 all(in) in.begin(), in.end() 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; } using namespace std; #define MAX 9999999 class unionfind { vector<int> par, rank, size_ ,sum; public: unionfind(int n) :par(n), rank(n), size_(n, 1),sum(n,0) { iota(all(par), 0); } int find(int x) { if (par[x] == x)return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y)return; if (rank[x] < rank[y])swap(x, y); par[y] = x; size_[x] += size_[y]; if (rank[x] == rank[y])rank[x]++; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return size_[find(x)]; } }; signed main(){ int n, maxi = 0; cin >> n; vector<int> v(n,0),sub(n),ans,sum(2*n,0); vector<bool> used(n,false); unionfind uni(2*n); rep(i,n) cin >> v[i]; rep(i,n) cin >> sub[i]; rep(i,n) { uni.unite(i,i+n); sum[uni.find(i)] = v[i]; } reverse(all(sub)); rep(i,sub.size()){ int index = sub[i]-1; maxi = max(maxi,v[index]); if(index+1 < n){ if(used[index+1]){ int val = sum[uni.find(index)]+sum[uni.find(index+1)]; uni.unite(index, index+1); sum[uni.find(index)] =val; } } if(index-1 >=0){ if(used[index-1]){ int val = sum[uni.find(index)]+sum[uni.find(index-1)]; uni.unite(index,index-1); sum[uni.find(index)] = val; } } cmax(maxi, sum[uni.find(index)]); ans.push_back(maxi); used[index] = true; } reverse(all(ans)); rep(i,ans.size()) cout << ans[i] << endl; }