gemでneovimをインストールできなかった
なんか
sudo gem install neovim
とかしたら
ERROR: Failed to build gem native extension
とか出てきて困った。
sudo apt-get install ruby-dev sudo gem install neovim
としたらいけた
SRM 700 Div1 Easy FindingFriend
解法
(2017/4/29:解き直したので下にちょっと付け足す.解法を確認するなら下に追記した部分を読んだほうがよい)
leader[i]がfriendPlaceよりも大きい場合、部屋i以降はleader[i]以上のランクの人だけで調整しなければならないのでleader[i]がfriendPlaceよりも小さいiのみ考えれば良い。
各部屋に収まる人数はroomSizeでそのうちleaderは決まっているので残りのroomSize-1人を埋めればよい。
leaderをソートしておきleaderのランクの小さい順にみる。
もしleader[i]-1 = roomSize*iだった場合、部屋0~i-1に入る人(roomSize*i人)は確定するのでfriendPlaceが入る余地はないので求めるパターンは0~i-1では0になり、部屋iから数え直す。
leader[i]のいる部屋iに対し、ランクがleader[i+1]-1の人までは部屋0~iのどこかに入らなくてはならない。
もし部屋iにleader[i]からleader[i+1]-1のランクの人を埋めてもランクleader[i]~leader[i+1]-1の人が余ったら以前の余っている部分を埋めて、それでも部屋0~iに余裕があるならその余裕の部分にfriendPlaceランクの人を入れることができるので余裕の部分が部屋iにできるようにすれば部屋iにfriendPlaceをいれることができる。
ソースコード
class FindingFriend{ public: int find(int roomSize, vector<int> leaders, int friendPlace) { int roomCount=leaders.size(); if(roomCount==1 or roomSize==1) return 1; rep(i,roomCount) if(leaders[i]==friendPlace) return 1; sort(ALL(leaders)); int ret=0; int rem=0; rep(i,roomCount){ if(leaders[i]>friendPlace) break; if(rem==0) ret=0; if(i==roomCount-1){ ret++; break; } assert(leaders[i]<=roomSize*i+1); int rs=roomSize-1; int diff=leaders[i+1]-leaders[i]-1; rem += rs-diff; ret++; } return ret; } };
感想
自分で解けなくて他の人のコードを見て理解した。なんか気がつけば当然の問題だけど全く気が付けない。。。friendPlaceの移動によりそれ以降の部分にも影響が出てしまうような気がしてしまうので難しかった。次に似た問題を見ても解けない気がする。。。
2017/4/29追記
解き直した.ソースコードがシンプルになったのであげ直す.
class FindingFriend{ public: int find(int roomSize,vector<int> leaders,int friendPlace){ int roomCount = leaders.size(); sort(all(leaders)); auto itr = std::find(all(leaders),friendPlace); if(itr!=leaders.end()){ return 1; } ll ans=0; for(int i=0;i<roomCount;i++){ if(leaders[i]>friendPlace) break; if(leaders[i]==i*roomSize+1){ ans=0; } ans++; } return ans; } };
解法は変わらないが,frindPlaceがleadersに含まれていないときに,
1.leaders[i]がfriendPlaceよりも大きければfrindPlaceをその部屋に追加するとleaders[i]よりfrindPlaceが小さくなり矛盾が生じるので考えなくて良い.
2.leaders[i]==i*roomSize+1の場合,部屋[0,i)は全て確定するのでfriendPlaceが追加される余地がない.ここでfriendPlaceはleaders[i]よりも小さいことが保証されているのでfriendPlaceは部屋iには入れる.
3.その他.普通に入れる.
2,3の場合は部屋iには入れるので前からカウント(+1)していけば部屋0~iは入れないが,i+1からjは入れるみたいな状況のときにi+1のときにカウントが0から再カウントされるので大丈夫.
AOJ 1138 Traveling by Stagecoach
解法
拡張ダイクストラを使ってd[現在のノード][使用した切符]を埋めていく。
使用した切符の枚数nはなのでbitで管理すればよい。
Queueには<距離,現在のノード,使用した切符>を入れ距離でソートして取り出せばよい。
計算量は多分くらいだと思う(違ったら指摘してください)...
ソースコード
void solve(int n,int m,int p,int a,int b){ vi t(n); rep(i,n) cin>>t[i]; vector<vector<int>> g(m,vi(m,INF)); rep(i,p){ int x,y,z;cin>>x>>y>>z; x--; y--; g[x][y]=z; g[y][x]=z; } sort(all(t)); vector<vector<double>> d(m,vector<double>(1<<n,DINF)); using P = pair<double,pair<int,int>>; // <distance , <node,used>> priority_queue<P,vector<P>,greater<P>> que; que.push(P(0,pii(a,0))); d[a][0] = 0; while(!que.empty()){ auto p = que.top();que.pop(); double dist = p.first; int v=p.second.first; int kip=p.second.second; if(dist>d[v][kip]) continue; for(int i=0;i<n;i++){ //i番目の切符を使用 if((kip>>i)&1) continue; int nkip = (kip | (1<<i)); for(int j=0;j<m;j++){ if(g[v][j]==INF) continue; double cost=dist+(g[v][j]/(double)t[i]); if(cost<d[j][nkip]){ d[j][nkip] = cost; que.push(P(cost,pii(j,nkip))); } } } } double ans = DINF; rep(i,(1<<n)){ ans = min(ans,d[b][i]); } if(abs(DINF-ans)<0.00001) cout << "Impossible" << endl; else printf("%.20lf\n",ans); } int main(){ int n,m,p,a,b; while(cin>>n>>m>>p>>a>>b){ if(n==0 and m==0 and p==0 and a==0 and b==0) break; a--; b--; solve(n,m,p,a,b); } }
感想
この問題自分で解けなかった...このくらいなら解けると思ったんだけど辺に対してどの切符を使えばいいかわからなかった...
これくらいは解けるようになりたい
vimでカラースキームが読み込まれたときにしたい処理
Vimでカラースキームが読み込まれた後に処理がしたい時がある
例えば特定のカラースキームのカーソルラインが気にいらない時とか....
そういう時のためのイベントとしてColorSchemeがあるらしい
例えばjellybeansのカラースキームが読み込まれた時に、カーソルラインをアンダーラインにして背景色をなしにしたいとすると
autocmd ColorScheme jellybeans highlight CursorLine ctermbg=NONE cterm=underline
とすればよい
イベントの一覧は
Vim documentation: autocmd
このあたりに書いてあるので参考になるかも?
SRM699 Div1 Easy OthersXor
問題
TopCoder Statistics - Problem Statement
要はN個の数字があり入力x[i]にはi番目の数字以外の数字のxorを取ったものが入っている。
入力xを満たすようなN個の数字の組み合わせのうち合計が最小となるようなものを見つけその最小値を求める(ただしそのようなN個の数字がなければ-1を返す)
解説
神ペーパーさんに教えて貰った。
各bitを個別に考えることができる(xorをとってるので繰り上がり、繰り下がりが発生することはない).
そして、数列の要素のうちiビット目が1のものがいくつあるかをそれぞれのbitについて確かめればいい。
それぞれのbitについて1がk個でxの条件を成立できるかを確かめ、成立できるkのうち最小のものを求めればよく、k個で可能かどうかは
kが奇数 かつ x[i]%2=1 なら i番目の数字の見ているビットは0(自分以外が奇数個)
kが偶数 かつ x[i]%2=1 なら i番目の数字の見ているビットは1(自分以外は偶数個)
(あとkが偶数/奇数で x[i]%2==0のときも考える)
としていって確かめればよい
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) typedef long long ll; const int BITS = 30; class OthersXor{ public: long long minSum(vector<int> x){ int N = x.size(); ll sum=0; vector<vector<int>> ans(N,vector<int>(30,-1)); vector<int> cnt(BITS); rep(i,BITS){ // see i-bit bool f=false; for(int num=0;num<=N;num++){ // num個にできる? int ones = 0; int undefine = 0; for(int j=0;j<N;j++){ if(x[j]==-1){ undefine++; continue; } // x[j]をみる int b = (x[j]>>i) & 1; if(num%2==1 and b==0){ ones++; }else if(num%2==0 and b==1){ ones++; } } if(ones > num) continue; if(undefine < num-ones) continue; for(int j=0;j<N;j++){ if(x[j]==-1) ones++; if(ones == num) break; } f=true; cnt[i] = num; break; } if(!f) return -1; } for(int i=0;i<BITS;i++){ ll t = 1 << i; sum += t * cnt[i]; } return sum; } };
感想
はじめてのDiv1だったから1問くらい解きたかった....
1問くらい解けないと緑に戻ってしまうだろうし怖い...
vim-autocloseで括弧入力直後にスペースを入力した時...
括弧の補完プラグインTownk/vim-autoclose(https://github.com/Townk/vim-autoclose)において、補完対象の括弧を入力直後にスペースが2つ入力されていた。
つまり
for(<ここでスペースを入力>
とした場合に、
for(__)
(_はスペース)
となってしまった。
これの解決策はここに記してあった。
github.com
つまり
let g:AutoCloseExpandSpace=0
としたら正常に動作した
技術室奥プログラミングコンテスト#2 C問題 有給休暇を解いたんだよ...
解法
二分探索で長さL(実際のコード中では"mid")の連続した1を作るか確認していき、作れる最長の長さを出力すればいい。
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define rep(i,n) for(int i=0;i<n;i++) #define INF INT_MAX/3 #define LINF LLONG_MAX/3 #define MP make_pair #define PB push_back #define EB emplace_back #define ALL(v) (v).begin(),(v).end() #define debug(x) cout<<#x<<":"<<x<<endl #define debug2(x,y) cout<<#x<<","<<#y":"<<x<<","<<y<<endl template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; } typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; #define MAXN 100001 int main(){ int N,K; int H[MAXN]; cin>>N>>K; rep(i,N) cin>>H[i]; int sum[MAXN+10] = {}; // sum[i] : [0,i)の0の個数 int cnt=0; for(int i=0;i<=N;i++){ sum[i] = cnt; if(!H[i]) cnt++; } int ul=0,ur=N+1; while(ur-ul>1){ int mid=(ul+ur)/2; // 長さmidの1の列を作れるか bool f=false; for(int i=0;i+mid<=N;i++){ int zero = sum[i+mid] - sum[i]; // [i,i+mid)に含まれる0の個数 if(zero<=K){ f=true; break; } } if(f){ ul = mid; }else{ ur = mid; } } cout << ul << endl; }
感想
コンテスト中には最初は左か右からK個全ての0を1に帰ればいいかと思ったけど
011000110 (K=3)の時とかに落ちてしまう。
そのあと二分探索を書いたけどWAが出てしまい解けなかった。とても悔しい。
コンテストの後りあん氏に聞いたらWAになってた原因は提出したコードで urの初期値を ur=Nとしていたので連続した1の個数がN個の列を作れる場合に落ちてしまっていた。
教訓 : 境界を求めるような二分探索での上界は必ず答えにならないような値にする必要がある。
自明なことではあるんだけど普通に気がつけなくて悲しい(o_o)
