ちゃっくのメモ帳

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

Xmas Contestに参加したっぽい?

競技プログラミング 感想 Atcoder

クリスマスイブ！
とくに予定もないのでXmas contestに参加しました。このコンテストはチームでの参加が許されていたので、すごぷろさんにチームを組んで頂いて参加しました。(開始4分前に突然チームを組もうとお願いする馬鹿の図👇)

https://twitter.com/chakku_000/status/812522220375281664

部室に集まって解くことにしました。

とりあえずA問題.
僕「とりあえずできるだけ大きい2の累乗を取っていったらどうですかね!」
とこのまま実装して56点を取る。流石に56点じゃ悲しいので考察を続けて「N/2を超える最大の2の累乗の数を左と右からとっていって被った部分を引く」という解法を考え,最初の1回だけに適用する。これで75点。ここまで順調だったので「毎回これにすればいいんじゃない!」とか調子に乗る。実装して提出してみると27点。絶望。改善を入れても33点程度。ならば2の累乗の数2個 or 3個に分割できるときだけ別で分ければ良いのじゃないかと考えたりしてみる。

ここですごぷろさんがBを出して24点獲得してEを時始めてた。

この時点で自分らより上にA100点が結構いたのでAをもう少し頑張るが、いい方法が思い浮かばなくて困る(;´･ω･)。
諦めてI問題にうつる。

I問題を読んでたらすごぷろさんがEで100点をだす。凄い。。。そのまますごプロさんはJ問題を始めた。

とりあえずIの部分点を狙うが実装が面倒臭そうなのと計算量が厳しそうなのですごぷろさんに相談。計算量についてはすごぷろさんと部分点なら行けるのではと考え実装し始める。

実装つらい。

ここで僕が実装をバグらせる && 実装をそもそも間違える
をしてしまい計算量が凄く大きくなって(多分予定の10^4倍くらい大きくなった...)しまうが残り数秒なので諦め。

すごぷろさんは知らない間にJを50点とってた。。。。
終了。


昼の部21位で結構良い順位じゃないかとおもったけどどう考えても僕の功績殆ど無いですよね！！！すごぷろさんチーム組んでくれてありがとうございました！

その後部室で考察したりおしゃべりしたりでぐだぐだ~して帰りました(o_o)v

XPS13(9360)にubuntuを入れた

linux

DellのXPS13(9360)を買ったのでubuntuを入れようとした。
目的としてはwindows10とubuntuのデュアルブートをしようとしたが、それ以前の問題でubuntuのインストール時にSSDを認識できなかった。

とりあえずArchwiki
Dell XPS 13 (2016) - ArchWiki

また、dellのxps13は9350のときも問題があったらしくその解決方法が日本語であった.
qiita.com

ぶつかった問題

上記したとおりubuntuの起動usbを作成し、起動後にDELLマークが出ている間にF12を連打してOne Time Bootからubuntuの起動usbを指定して起動する。このときに使用したubuntuのバージョンはubuntu16.04であった。

Try without install ubuntuを選択し起動するとまずWifiが使用できない。おそらくドライバの問題?

更にインストーラーを起動するとSSDが認識されていないのでインストールする先がなくエラーでインストーラーが停止してしまう。

つまりこのままではインストールできない。

実際にやったこと

　とりあえずwindowsの回復ドライブを作った。デュアルブートの場合あとで使用するので作成は必須である。ubuntuのみにするなら必須ではないが作っておいてもUSBメモリ1本分くらいしか損はしないので作っておいて良いのではないだろうか...

　まずubuntuからSSDが認識出来ない問題について、これはどうもSATA controllerがRaidになっているのが問題らしい(そもそもなんでSSD1台のノートの初期設定をraidにしているのか意味不明である). これをAHCIにするとSSDが認識できるらしい。
これはPCを起動してDELLマークが表示されている間にF2を連打してBIOSの設定を開く。そしてSystem ConfigurationのSATA OperationがRaidになっているのでAHCIを選択して終了する。

　これでWindowsを起動しようとすると起動に失敗する！！！
が上のQiita通りなので問題なし。

回復ドライブからwindowsを起動して再インストールすれば何も問題がない。

windowsを再インストールしたらPCにubuntuの起動usbを挿し、PCを起動。
DELLマークが表示されている状態でF12を連打してusbから起動する。

Wifiが使用できないのは変わらないがインストーラーを使用して落ちることなくインストールできる。
これでインストールは終了。

これで終わりとおもってubuntuを起動したら、

問題が発生する！！！

まず、解像度が800x600に固定されてしまい変更ができない。更にusbからの起動時同様にWifiが使用できない。

「おいおいまってくれ、、、Wifiはともかく君usbから起動した時は解像度問題なかったやろ...その時の状況で動いてくれ」

状況は依然厳しい。

まあどちらもディスプレイと内蔵Wifiアダプタのドライバがはいっていないことが問題なきがする。とりあえずカーネルのバージョンを調べたらkernel4.4.0だった。
カーネルのバージョン的には(適当にググったあたり)大丈夫そうな感じはしたがとりあえず16.10にしてみることで解決を目論んだ。

ubuntu16.10の起動usbを作り起動してみるとwifiが動いている。そのままインストールして起動するとwifiは動き解像度も正しく表示されている。

おそらくubuntuのインストールはこれで完了!!!

疑問点

疑問1 16.04のときにusbから起動して解像度は問題なかったのになぜインストールしたらおかしくなったのだろうか?wifiが使えなかったから「ubuntuのインストール中にアップデートをダウンロードする」と「「サードパーティソフトウェアをインストールする」を選択できなかったのが問題だったのだろうか?

疑問2 海外ではxps13 developer editonなるものがあってそれにはubuntu16.04がインストールされておりドライバ周りなどの動作が保証されているらしい。おそらく同じwifiアダプタ使ってるのではと思っていたのだが16.04で動作しなかったのはなぜだろうか....

疑問3 xps13のドライバでlinuxから使えるのってどこにあるんですか.....(dellの公式みてもwindows用しかない)

だれかこの疑問点解決(特に疑問3)を解決できるひといたら教えてくださいっ

感想

Dellさん頼むからDeveloper Editionを日本でも販売してくださいお願いします

SRM 700 Div1 Easy FindingFriend

競技プログラミング Topcoder

問題

TopCoder Statistics - Problem Statement

解法

(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

競技プログラミング AOJ

解法

拡張ダイクストラを使って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

Vimでカラースキームが読み込まれた後に処理がしたい時がある

例えば特定のカラースキームのカーソルラインが気にいらない時とか....

そういう時のためのイベントとしてColorSchemeがあるらしい

例えばjellybeansのカラースキームが読み込まれた時に、カーソルラインをアンダーラインにして背景色をなしにしたいとすると

autocmd ColorScheme jellybeans highlight CursorLine ctermbg=NONE cterm=underline

とすればよい

イベントの一覧は
Vim documentation: autocmd

このあたりに書いてあるので参考になるかも?