ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

AOJ 1138 Traveling by Stagecoach

解法

拡張ダイクストラを使ってd[現在のノード][使用した切符]を埋めていく。
使用した切符の枚数nは{n<=8}なのでbitで管理すればよい。
Queueには<距離,現在のノード,使用した切符>を入れ距離でソートして取り出せばよい。
計算量は多分{O(m2^n)}くらいだと思う(違ったら指摘してください)...

ソースコード

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問題 有給休暇を解いたんだよ...

tkppc2.contest.atcoder.jp

解法

二分探索で長さ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)

tmuxをビルドしたんだよっ

ubuntu15.10でtmuxをaptで入れてもバージョンが2.0とかしか入らないので最新版を使うためにはソースからビルドする必要がある。

cd /usr/loca/src
sudo git clone https://github.com/tmux/tmux.git
cd tmux
sudo ./autogen.sh
sudo ./configure --prefix=/usr/local
sudo make
sudo make install

としてビルドすることができた。
もしこれでエラーが出たら

sudo apt-get install libevent-dev

とかしてみるといいかもしれない。

感想

aptを使って入れられるのが一番楽なんだけどaptを使うと古いバージョンだったりするから結局最新版を使うためにはビルドする必要があるのちょっと面倒くさいよね(o_o)....

ICPC2016国内予選

ICPC2016国内予選に参加しました。
チームnikkuとして参加し、メンバーはすごプロ(@jken_ull),いしづ(@ish_774),僕でした。

結果としてはA,B,Cの3完で97位でした。

以下当日の流れです(時間はだいたい。記憶は結構あやふや)

16:30 -- 開始 --
 とりあえず問題を印刷して、A僕,Bいしづ,Dすごぷろさんの担当。
 10分くらいでA問題を通して僕はC問題を読む。

16:45
 いしづがB問題を書き始めるがバグったらしく、苦戦している。僕はC問題考察終了、F問題を読み始める。

このあたりかもう少し後ですごぷろさんがD問題の考察を終了したらしく、E問題を考察を始めてる。

17:10くらい
 いしづがB問題に詰まっているので画面の半分でいしづがコードとにらめっこし、もう半分ですごぷろさんがD問題を書き始める。

17:30 くらい?
 とりあえずいしづがB問題を通した。すごぷろさんがD問題提出するが、WA. サンプルがあっているのでデバッグがつらそう。
 F問題の考察にいしづが参加。

 D問題がすぐには通らなさそうなので僕がCが問題を書くがサンプルが合わない。
 合わないサンプルの値が小さいので手で確認したらバグが判明して書き直す。
 最大ケースを解くのに十秒くらいかかったので焦ったがとりあえずサンプルが合うので提出。AC。
 すごぷろさんはD問題のデバッグ

 この後、僕はF問題の考察を諦める。G問題を読んでみる。
 G問題、問題の意味がよく分からず放棄。F問題の考察に戻る。

18:30 くらい?(たぶんもう少し後)
 すごぷろさんがD問題のデバッグ続けるよりE問題書いたほうが良いと判断。E問題を書き始める。
 いしづはF問題の考察を続行。
 僕はD問題のデバッグに移る。

19:10
 Eの問題のサンプルが合わないらしい。F問題は考察が出来たとしても実装が間に合わないのでいしづがD問題のデバッグに参加。

19:28
 いしづがD問題のデバッグでおかしな挙動を見つけるが、間に合わず。。。。

19:30 --終了--

感想

今回のコンテストでは思考が必要な問題をすべてすごプロさんにまかせてしまい申し訳なかった。
ぼくがD問題くらいまで担当できるようになりたい。