ubuntu 16.04 LTSのかな入力で長音(ー)が入力できない問題

またまたこの問題にぶちあたってしまいました。 インストールした当初(かな86)は正しく動作していたのに、気づいたら上手くいかなくなってたので奮闘した話。

症状

fcitx&mozcのかな入力(ローマ字でも)で、\キーを押したときの挙動が変になる。 具体的には、「ほーむ」を入力しようとしてとして「ほ「長音」む」と入力すると、「\ほむ」みたいな感じになって全くわけがわからない。

解決策

シフトキーを押しながら入力すると正しく動作するが、それは面倒くさい。 ということで、原因が何かを探ってみた。

どうやら\の挙動が変になるキーボード入力設定に一瞬でも切り替わったら、その\の挙動がmozcなどにも伝搬するらしいということが分かった(理由は探ってない)。IM(fcitx)を再起動すると治る。

これは、ログイン直後にデフォのインプットメソッドがmozcに設定されている間だけ正しく動作することから推測した。

ということで、インプットメソッド一覧にあった「キーボード 日本語(かな86)」を削除して、さらに規定のキーボードレイアウトを「日本語 - 日本語(OADG 109A)」にしてログインしなおしたら治った。

こんなかんじ。

振り返り

英語キーボードとかも\のキー設定をぶっ壊すっぽい。実際英語キーボード入れた後壊れた。

ところでとりあえず適当に「日本語 - 日本語(OADG 109A)」を選択したんですけど、これどれ選択するのが一番いいんですかね。

UbuntuにpycharmをLauncher(ランチャー)に登録する

pycharm.shをコンソールでもなんでもいいから起動したあと、起動中にランチャーに出てくるアイコンを右クリックして『Launcherに登録』を押せば良い。

Djangoでメールを送信しようとして出るsmtplib.SMTPAuthenticationError:

smtplib.SMTPAuthenticationErrorと出たらgoogleのセキュリティ設定が原因かもしれないので以下を確認してみましょう。

https://www.google.com/settings/security/lesssecureapps

ICPC 国内予選 2016

@a3636takoと@aki33524と出てました．8位でした． 多分通過しました．

作戦

僕が全部の問題のコーダーになって，他の二人には解法係になってもらい，基本的にペアプロをするように心がける 理由は僕が色々実装テクを知っているから早いだろうというだけ．

結果

トータルでは事無きを得たけど，恐らく失敗． この作戦は，バグがない場合に限り有効であることが分かった．バグが発生したとき，死亡する． 普通のバグは大体潰してもらえるのだけれど，見落としがちな論理的なバグはペアプロでも潰しようがない．

具体的には，A・BをFAして1位に踊りでた後，Dでバグらせた上に，デバッグ放棄してCの実装をしたので順位がヤバいことになった． その間チームメイトにバグを探してもらったけど見つからなくて，結局論理的に間違っていることが分かった． 黄色コーダー級のチームメイトが2人いるのだから，簡単な問題を実装してもらいつつ僕がデバッグをしてもよかった．

僕しかパソコンに触らない状況だと，僕がデバッグするときに全くパソコンが開かない．

今後

アジア地区予選に向けて，この作戦を適用できるかどうかは再度考慮しないといけない． 少なくともアジア地区は解法がすぐに降ってくるタイプの問題が少ないので，パソコンの前をできるだけ無駄に空けたくない． ということで，コーダー2人体制とか3人体制とかいろいろ試してみようと思います．

悩み

僕がチームの中で飛び抜けているのは経験に基づく解法力のみで，やはり思考力がないので，そこを伸ばしていきたい． 経験により実力は誤魔化せるけど，頭の回転の遅さは何年経っても改善しないのをうっすら感じる． 「典型レパートリーを無限に増やし続けるのだ」という某の言説が聞こえてきますが，それを早くこなすようなガッツも時間も能力もないので，やっぱりそういうことができるのは強い人だと思います(やや悲観的)．

ICPC2016 模擬国内予選B

A

日本語を読む

紛失

B

グイッと実装．stringstreamは便利

#include <bits/stdc++.h>
using namespace std;

// 頭が整理されてないまま書いた糞コード

int main(){
    string S;
    int a,b,c,d;
    while( cin >> S && S != "#" ){
        cin >> a >> b >> c >> d;

        for(int i = 0 ; i < S.size() ; i++){
            if( S[i] == '/' ) S[i] = ' ';
        }
        vector<string> to;
        stringstream ss(S);
        string t;
        while( ss >> t ){
            string a;
            for( auto c : t ){
                if( '0' <= c && c <= '9' ){
                    a += string(c-'0',' ');
                }else{
                    a += c;
                }
            }
            to.push_back(a);
        }
        swap(to[a-1][b-1],to[c-1][d-1]);
        string ans;
        for( auto l : to ){
            string a = "";
            for(int i = 0 ; i < l.size() ; ){
                if( l[i] == 'b' ) a += 'b', i++;
                else{
                    int j = i;
                    while( j < l.size() and l[j] == ' ' ) j++;
                    a += '0'+j-i;
                    i = j;
                }
            }
            ans += a + "/";
        }
        cout << ans.substr(0,ans.size()-1) << endl;
    }
}

C

座圧してセルの内外判定する気が起きなかったので平面走査

#include <bits/stdc++.h>
using namespace std;
//　計算量は O(N+窓の周長)

int main(){
    int N;
    while( cin >> N && N){
        map<int,vector< pair<int,int> > > seg;
        for(int i = 0 ; i < 50000 ; i++) seg[i] = {};
        
        
        //(1) 窓の入力 & x軸に平行な線分のみをy座標毎に列挙
        int px,py;
        int sx,sy;
        for(int i = 0 ; i < N ; i++){
            int x,y;
            cin >> x >> y;
            x += 20000;
            y += 20000;
            if(i){
                if( y == py ){
                    int a = x;
                    int b = px;
                    if( b < a ) swap(a,b);
                    seg[y].push_back({a,b});
                }
            }else sx = x, sy = y;
            px = x;
            py = y;
        }
        if( sy == py ){
            int a = sx;
            int b = px;
            if( b < a ) swap(a,b);
            seg[sy].push_back({a,b});
        }
        
        // (2) カーテンの入力 & カーテンの範囲を求める
        int x1 = 1e9,x2 = -1e9,y1 = 1e9,y2 = -1e9;
        for(int i = 0 ; i < 4 ; i++){
            int x,y;
            cin >> x >> y;
            x += 20000;
            y += 20000;
            x1 = min(x1,x);
            x2 = max(x2,x);
            y1 = min(y1,y);
            y2 = max(y2,y);
        }
        // 平面走査 & 正直あんましimosしてない
        vector<int> imos(50000);
        long long allans = 0;
        long long innerans = 0;
        long long innertot = 0;
        long long alltot = 0;
        
        for( auto vec : seg){                               
            int y = vec.first;
            for(auto s : vec.second ){
                for(int x = s.first ; x < s.second ; x++){
                    imos[x] ^= 1;
                    // for inner 
                    if( (x1 <= x and x < x2) ){
                        if( imos[x] ) innertot += 1;
                        else innertot -= 1;
                    }
                    // for all
                    if( imos[x] ) alltot += 1;
                    else alltot -= 1;
                }
            }
            // for all
            allans += alltot;
            // for inner
            if( (y1 <= y && y < y2) ){
                innerans += innerans;
            }
        }
        cout << allans - innerans  << endl;
    }
}

D

本質は強連結成分分解なのですが，O(N+M)のアルゴリズム使わなくてもO(N³)のワーシャルフロイドっぽい実装で代替できます(N:頂点数，M:辺数)．

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    while(cin >> N && N){
        bool g[110][110]={};
        bool g_src[110][110]={};
        int in[110] = {};
        double p[110];
        for(int i = 0 ; i < N ; i++){
            int m;
            cin >> p[i] >> m;
            while(m--){
                int j;
                cin >> j;
                --j;
                g[i][j] = true;
                g_src[i][j] = true;
            }
        }
        
        for(int i = 0 ; i < N ; i++)
            g[i][i] = true;
        for(int i = 0 ; i < N ; i++)
            for(int j = 0 ; j < N ; j++)
                for(int k = 0 ; k < N ; k++)
                    g[j][k] |= g[j][i] & g[i][k];
        bool used[110] = {};
        int color[110] = {};
        double p_to_col[110] = {};
        
        // 強連結成分分解
        for(int i = 0 ; i < N ; i++){
            if( used[i] ) continue;
            double bad = 1.0;
            for(int j = 0 ; j < N ; j++){
                if( used[j] == false and g[i][j] && g[j][i] ){
                    bad *= p[j];
                    used[j] = true;
                    color[j] = i;
                }
            }
            p_to_col[i] = bad;
        }
        // 入次数数える
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < N ; j++){
                if( g_src[i][j] and color[i] != color[j] ){
                    in[j]++;
                }
            }
        }
        
        // 入次数0の頂点のみに着目
        double ans = 1.0;
        for(int i = 0 ; i < N ; i++){
            if( in[i] == 0 and color[i] == i ){
                ans *= 1 - p_to_col[i];
            }
        }
        printf("%.10lf\n",ans);

    }
}

E

よく考えるとdはソートしてよさそうなのでソートすると，布団を片付けることを一切考えなくて良い状態になってハッピー． 頭が悪いので遷移に全ての部分集合をぶち込んでいるが，遷移を工夫すれば計算量落ちます．

#include <bits/stdc++.h>
using namespace std;
// O(M*3^N)

int s[110],d[110];
int N,M;

int dp[110][1<<16];

vector<int> bit[1<<15];
int sum[1<<16];

int dfs(int x,int bit){
    if( x == M ) return 0;
    if( dp[x][bit] != -1 ) return dp[x][bit];

    int ans = 1e9;
    /*for(int i = 0 ; i < (1<<N) ; i++){
        if( bit & i ) continue;
        ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans); 
    }*/
    // 上と下は等価
    int sup = ((1<<N)-1)^bit;
    int i = sup;
    do{
        ans = min(dfs(x+1,bit|i)+abs(sum[i|bit]-d[x]),ans);
        i = (i-1)&sup;
    } while( i != sup );
    
    return dp[x][bit] = ans;
}
int main(){
    int t = 0;
    while( cin >> N >> M && N ){
        memset(dp,-1,sizeof(dp));
        for(int i = 0 ; i < N ; i++) cin >> s[i];
        for(int i = 0 ; i < M ; i++) cin >> d[i];
        for(int i = 0 ; i < (1<<N) ; i++){
            int t = 0;
            for(int j = 0 ; j < N ; j++){
                if( i >> j & 1 ){
                    t += s[j];
                }
            }
            sum[i] = t;
        }
        sort(d,d+M);
        cout << dfs(0,0) << endl;


    }
}

G

全てきひろちゃんとa3636takoが考えた．実装しただけ．

#include <bits/stdc++.h>
using namespace std;

long long mod = (int)1e9 + 7;

long long b_pow(long long a,long long b){
    return b ? b_pow(a*a%mod,b/2) * (b&1?a:1) % mod : 1;
}

#define CCCCCC 4000000
long long f[4000010];
long long inv[4000010];

long long ncr(long long a,long long b){
    //cout << a << " " << b << endl;
    assert( b <= a );

    return f[a] * inv[a-b] % mod * inv[b] % mod;
}
int main(){

    // N!とN!の逆元を全て求めとく
    f[0] = 1;
    for(int i = 1 ; i <= CCCCCC ; i++)
        f[i] = f[i-1] * i % mod;
    for(int i = 0 ; i <= CCCCCC ; i++)
        inv[i] = b_pow(f[i],mod-2);
        
    int A,B,C,Sx,Sy;
    while( cin >> A >> B >> C >> Sx >> Sy and A+B+C ){
        if( A == 0 and B == 0 ){
            if( Sx != Sy ) cout << 0 << endl;
            else cout << ncr( Sx + C - 1, C - 1 ) << endl;
            continue;
        }

        if( A == 0 ){
            swap(A,B);
            swap(Sx,Sy);
        }
        long long ans;
        if( B == 0 ){
            ans = ncr(Sx-Sy-1,A-1) * ncr( (A+C-1) + Sy, A+C-1) % mod;
        }else{
            ans = 0;
            for(int a = A ; a <= Sx ; a++){
                long long X = ncr(a+A-1-A,A-1);
                int b = Sy - Sx + a;
                if( b < B ) continue;

                long long Y = ncr(b+B-1-B,B-1);
                long long Z = ncr( (A+B+C-1) + (Sx-a), A+B+C-1);

                ans += X * Y % mod * Z % mod;
                ans %= mod;
            }
        }
        cout << ans * f[A+B+C] % mod * inv[A] % mod * inv[B] % mod * inv[C] % mod << endl;  
    }
}

撹乱順列(完全順列)の数について理解する

撹乱順列とは

{1,2,3,...n}の順列で，どの要素も元の位置にないような順列を撹乱順列(またの名を完全順列)といいます．例えばn=3の撹乱順列として{2,3,1},{3,2,1},{3,1,2}とかが挙げられます．{2,1,3}とかは撹乱順列ではありません．3番目の要素が元の位置にあります．

つまり，{1,2,...n} の順列 P = {p1,p2,...,pn}について考えるとき，全ての i についてpi≠iが成り立つような順列を撹乱順列と呼びます．

そしてその撹乱順列の個数はモンモール数という名前がついており，以下の漸化式で求められます．

個数の漸化式

• a1 = 1
• a2 = 1
• an = (n-1)(an-1+an-2) (n ≧ 3)

なぜこのような漸化式になるのかについて考えてみましょう．説明のために遷移とかいう言葉を使っていますが再帰をイメージしてください．

まず，長さnの撹乱順列 {1,2,..,n}のうち，1の位置をiで確定させることを考えます(n-1通りあります)．別に確定させる数字のはnとかでも何でもいいですが，とりあえず1に着目してその位置を考えます． 確定としては，こんな感じですね．いま，位置 i が埋まってしまったのですが，数字 i はフリーです．これはちょっと厄介な状態です． 撹乱順列の漸化式は，ある使われてない数字の元の位置が既に埋まっているような状態に対する式ではありませんでした．

iをどこに置くか考えてみましょう．

数字 i の位置を 1 に行かせるケース

数字 i の位置を 1 に行かせるケースを考えます．

この場合，なんか明らかに残ったやつを再ラベリングすれば{1,2,...n-2}の撹乱順列を求めることと同等になるので，an-2に遷移したら良さそうな感じしますね．このケースはとても簡単でした．

数字 i の位置を 1以外 に行かせるケース

さて，もうひとつが厄介です．以下のような1じゃないところに遷移するケースです．

これ頭の良い人がグッと睨むと，長さn-1の撹乱順列と状態が等価らしいんですが，「は?」状態です．いやいや，下の図の2つの状態が等価てお前．

何言ってるのって気分になりました(図で本来 1 2 3 … i-1 i+1 … nとなるべきところが1 2 3 n とはしょられてるのはご愛嬌)．

いやだってさ，上の状態，数字1使われてるやん，しかも数字iの元の位置埋まってるのに数字iフリーじゃん．下の綺麗な状態と等価だなんてとても思えない．

ただ，よく見てみると「数字iの位置は1以外」という条件があります．これがキモっぽいです．

よく考えてみると，上の状態における数字iを数字1に再ラベルしても問題なさそうな感じがしませんか? だって，数字iを1にしたところで，「iの位置は1以外」という性質が「1の位置は1以外」と言い変わるだけで，その性質というのは常に撹乱順列だから元々成り立っているはずです．

この変換によって，上の状態が下の状態と等価な状態になり，長さn-1の撹乱順列の状態であることがわかりました．

まとめ

まとめると，iを選ぶ候補として(n-1)通りあって，あとはiを選ぶとそれぞれのiについてan-1+an-2通りだけ組み合わせの数があることが分かるので，冒頭で述べた漸化式になります．

参考にしたサイト

ちなみに，ほとんどこちら様の受け売りです．こちら様の素晴らしい親切な説明ですら少し悩んだので，悩んだ部分について皆さんと共有しようと思いました．

for-e-study.com

JAG Contest 2016 Domestic C - みさわさんの根付き木

jag2016-domestic.contest.atcoder.jp

誤って書いた記事を消してしまったので再投稿です．

問題文

省略

解法(反転して表示)

LL(1)による再帰構文解析を知っていると特に思考をせず木構造に直すことができる． 木に落としたらマージをするが，これは再帰でやるのが実装が楽でおすすめ．平衡二分木をmerge-splitベースで実装したことがあるとイメージがつきやすいかも． 余談ですが，構文解析，「次に来る文字が△◎×だったら～」みたいな処理を結構アドホックだと思っていたら，first集合やfollow集合とかいう概念があったりするので，そういうのを学んでみて，強く意識すると迷ったり漏れが発生することが少なくなるかも．

ソース

#include <bits/stdc++.h>
using namespace std;
 
 
string S;
int p;
struct T{
    int v;
    T *l,*r; 
    T(){
        l = r = NULL;
    }
}; 
 
T *merge(T *a,T *b){
    if( a == NULL || b == NULL ) return NULL;
    T *r = new T();
    r->v = a->v + b->v;
    r->l = merge(a->l,b->l);
    r->r = merge(a->r,b->r);
    return r;
}
void view(T *x){
    
    if( !x ) return;
    cout << "(";
    view(x->l);
    cout << ")";
    cout << "[";
    cout << x->v;
    cout << "]";
    cout << "(";
    view(x->r);
    cout << ")";
    
}
 
T* expr(){
    if( S[p] != '(' ) return NULL;
    T *res = new T();
    //←の子
    p++;
    res->l = expr();
    p++;
    
    p++;
    int x = 0;
    while( S[p] >= '0' && S[p] <= '9' ) x = x * 10 + S[p++] - '0';
    res->v = x;
    p++;
    //→の子
    p++;
    res->r = expr();
    p++;
    return res;
}
int main(){
    string s,t;
    cin >> s >> t;
    S = s;
    p = 0;
    auto one = expr();
    S = t;
    p = 0;
    auto two = expr();
    view(merge(one,two));
    cout << endl;
}