long long expr(State &begin) {
    long long ret = term(begin);

    for (;;) {
        if (*begin == '+') {
            begin++;
            ret += term(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term(begin);
        } else if (*begin == '*'){
            begin++;
            ret *= term(begin);
        } else {
            break;
        }
    }
    return ret;
}

とりあえず全部書けば通りますが、面倒なのでどうにかして楽に書きましょう。

4つのparserを書いたり*1、bitを使って全通り試したりしましょう。

ACされたコード
AIZU ONLINE JUDGE: Code Review

注意点

解の初期化に注意する
解のmaxを取っていくのなら、解を入れる変数を小さい数値で初期化しなければいけません。
ここでは最小値で初期化しましょう。雑に小さい数値を入れるとWAです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012

問題概要

集合の演算を行う構文解析です。
演算子は u, i, d, s, c の5つあり、式はセット名、演算子、括弧からなります。
この問題の式は、以下のように与えられます。

<expr> ::= <term> <op> <term>
<term> ::= c <factor> | <factor>
<factor> ::= ( <expr> ) | <set>
<set> ::= A | B | C | D | E
<op> ::= u | i | d | s

見様見真似なので、正しいか全く自信がないです。

解法

まさに構文解析という問題です。
形は変われどやっていることは同じです。
集合の計算は関数があるので、演算子の処理を考える必要はありません。

順番にテンプレを書き換えていきましょう。

number関数
集合を返すだけです。
文字列を数値に変換するなどの操作がないので、number関数を使わなくても問題ありません。

factor関数
括弧を処理するか数を返すかのどちらかなので、そのままで問題がなさそうです。

term関数
ここで行う演算は 'c' のみです。今見ている文字が'c'のとき、factor関数の戻り値を補集合にすればよいです。
'c'ではなかったら、戻り値をそのまま返します。

expr関数
四則演算で言うところの + や - にあたる部分を u, i, d, s を変えます。
条件分岐させて演算するようにします。

ACされたコード
AIZU ONLINE JUDGE: Code Review
構文解析部分は50行と短いです。

注意点

集合は始めにソートする。
set_unionやset_intersectionは、ソートされていないと正しい集合を返しません。

NULLを出力する。
解が空集合の場合、NULLを出力しなければなりません。
ここでいうNULLはテキストの "NULL" です。 '¥0' ではないです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155

問題概要

0, 1, 2, P, Q, R, -, *, +, (, ) からなる式が与えられます。
P, Q, R は、それぞれ 0 ~ 2 までの数値へ置き換えることができます。
このとき、式の解が 2 であるような P, Q, R の組み合わせは何通りあるでしょうか。

解法

P, Q, R の組み合わせは 27 通りしかないので、全部試して解が 2 になる回数を数えればよさそうです。
次に、式をどのようにして演算すれば良いのかを考えます。

演算子 +, * は、与えられた数値のmax, minを取ればよいです。
- 演算子は、http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012の c 演算子のように処理すればよさそうです。

つまり、expr→term（ここで - 演算子を処理）→factor→numberとすれば計算できます。
ただ、 - 演算子は連続することもあります。
ですので、もし - 演算子があれば、term関数を呼ぶ。
それ以外はfactor関数を呼ぶようにして、連続した - 演算子を処理します。

int term(State &begin){
    if (*begin == '-') {
        begin++;
        //inverted(x) = xを反転した値
        return inverted(term(begin)); 
    } else {
        return factor(begin);
    }
}

ACされたコード
AIZU ONLINE JUDGE: Code Review

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570

問題概要

>>、S<>、数値からなる式を計算する。

解法

まず、空白はあってもなくても変わらないので全部消します。
次に、>> 、S<>について考えます。
>>はexprで処理し、S<>はfactorの括弧の処理を少し書き換えて実装します。

>>を素直に実装すると、

if(*being == '>' && *(begin + 1) == '>'){
    begin++; 
    begin++;
    ret = ret >> term(begin);
}

とやってしまいそうですが、少しまずいです。
まず、この条件では、”S< S< S< 1 > > >” このようなケースのときに、シフトを行ってしまいます。
３つ '>' が並んでいるときは、シフト演算子ではありません。

if(*begin == '>' && *(begin + 1) == '>' && *(begin + 2) != '>')

２つのみ並んでいるときだけ、シフトしましょう。

次に、 "ret >> term(begin)" の部分に注目します。
上記の実装では、"1 >> 20000" という計算を行うこともあります。
これだとオーバーフローを起こして 0 ではない値になるので、シフト演算子の右辺は小さめに抑えたほうがよいです。

ACされたコード
AIZU ONLINE JUDGE: Code Review

注意点

2 乗でオーバーフロー
int型だとS<>を処理するときにオーバーフローします。

まとめ

処理を関数にまとめて、順番を決めて、終わり。
バグらせると辛い。

*1:http://tubo28.me/blog/post/2015/06/21/aoj2613/

2017-05-21

vimに構文チェックのプラグインを入れた（C++）

メモ開発環境

syntastic
- 導入の流れ
- 導入してわかったこと
  - ファイル上書き時に構文チェックされる。
  - 割と重い
w0rp/ale Asynchronous Lint Engine
- 導入してわかったこと
  - syntasticと比べて速い
結論

syntastic

f:id:noy72:20170512093811p:plain
このようになりました。

導入の流れ

GitHub - vim-syntastic/syntastic: Syntax checking hacks for vim
丁寧に書いてあるので、特に迷うこともないと思います。
インストールの手順に沿って、上から順番にコマンドを実行していきましょう。

しかし、その状態ではエラーチェックが行われなかったので、正しく動作しているかを確かめるため以下のコマンドを入力しました。

:SyntasticInfo

f:id:noy72:20170511184017p:plain
明らかに動いていなさそう。

Q&Aによれば、構文チェッカーが有効になっていない可能性があるのこと。
以下を.vimrcに書き込みました。

let g:syntastic_cpp_checkers = ['gcc']

f:id:noy72:20170512093803p:plain
できまし……ん？

errorやwarningが出ます。
構文チェックがc++11に対応していません。

そこで、

let g:syntastic_cpp_compiler="gcc"
let g:syntastic_cpp_compiler_options=" -std=c++11"

ちゃんとオプションをつけてあげましょう*1。

これで正しくチェックしてくれるようになりました。

導入してわかったこと

ファイル上書き時に構文チェックされる。

リアルタイムで更新されると思っていました。
vimrcで設定を変えれば、編集モードに入ったときにチェックしてくれます*2。

割と重い

チェックする時に微妙に止まります。
バニラのvimがぬるぬる動くように感じる程度には止まります。

w0rp/ale Asynchronous Lint Engine

f:id:noy72:20170521103009p:plain

こちら脱VimしようとしてAtomを触ってたけど、やっぱりVimを使うことにした - console.lealog(); で速いとの情報を得たので、早速インストール

GitHub - dense-analysis/ale: Check syntax in Vim asynchronously and fix files, with Language Server Protocol (LSP) support
同じようにインストール。
syntasticがあると衝突するのでアンインストールしておきます。

導入してわかったこと

syntasticと比べて速い

確かに速い。スムーズに動きます。
ただ、エラー箇所を示す矢印（>>）の表示がやや遅いです。

結論

ファイルが小さいなら、syntasticが極端に遅くなることはない。
Asynchronous Lint Engineの方が速い。
適当にコマンドをコピペするだけでインストールできる

*1:http://d.hatena.ne.jp/akahana_1/20160615/p1

*2:Vimで最強の文法チェックを実現するための簡単な方法 - Qiita

2017-04-02

AOJ - 2170 Marked Ancestor

競技プログラミング

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170

問題概要

木が与えられる。
以下の２つのクエリを処理し、出力された番号の合計を求める。

頂点aをマークする
頂点aから最も近いマークされた祖先の番号を出力する

解法

union-find

このスライドにある解法をそのまま実装した。
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2009%2FPractice%2F夏合宿%2F講評&openfile=3f.pdf

入力を隣接リストで受け取った後、クエリ ’M' だけを処理する。
マークされた頂点を記録する。このとき、同じ部分にマークされた場合、処理せずなかったものとして扱う。

その後、与えられた木を構築するためdfsを行う。このとき、depthに木の深さを記録した。
深さの情報をもとに、マークされなかった頂点と、その頂点の親をuniteした。
常に根に近い部分を親としてuniteしなければいけないため、深さを利用した。

後はクエリを逆順に処理していく。
’Q' クエリはfindし、値を足す。
'M' クエリは、自分の親とuniteする。

木を構築する、各頂点の親を持つ、uniteするときに根に近い頂点を親にする、などやることが多く実装に時間がかかった。

コード

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

const int gmax_n = 100005;

int par[gmax_n]; //親
int depth[gmax_n];//木の深さ

void init(int n){
    rep(i,n){
        par[i] = i;
        depth[i] = 0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(depth[x] > depth[y]){
        par[x] = y;
    }else{
        par[y] = x;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

void dfs(vector<int> t[gmax_n], int g[gmax_n], int cur){
    rep(i,t[cur].size()){
        int next = t[cur][i];
        if(g[next] != -1) continue;

        depth[next] = depth[cur] + 1;
        g[next] = cur;
        dfs(t,g,next);
    }
}

int main(){
    int n, m;
    while(cin >> n >> m, n||m){
        vector<int> tree[gmax_n];
        init(n);
        rep(i,n - 1){ //木の構築
            int a;
            cin >> a;
            a--;
            tree[i + 1].emplace_back(a);
            tree[a].emplace_back(i + 1);
        }

        bool marked[gmax_n] = {false};//マークされるノードを記録
        marked[0] = true;
        vector<pair<char, int>> q;
        rep(i,m){
            char a;
            int b;
            cin >> a >> b;
            b--;
            if(a == 'M'){
                if(marked[b]) continue; //同じ部分にマークした場合は、初回以外を無視。
                else{
                    marked[b] = true;
                    q.emplace_back(make_pair(a, b));
                }
            }else{
                q.emplace_back(make_pair(a,b));
            }
        }

        int g[gmax_n] = {0};
        range(i,1,gmax_n) g[i] = -1;
        dfs(tree, g, 0);

        rep(i,n){
            if(not marked[i]) unite(g[i], i);
        }

        //rep(i,n) show(g[i])
        //rep(i,n){ show(find(i)) }
        //rep(i,n){ show(depth[i]) }

        long long ans = 0;
        for(int i = q.size() - 1; i >= 0; i--){ //クエリを逆順に処理
            if(q[i].first == 'Q') ans += find(q[i].second) + 1;
            else{
                unite(g[q[i].second], q[i].second);
            }
        }
        cout << ans << endl;
    }
}

2017-02-27

ネットワークインターフェイスの名前

メモ

MacBook Air でifconfigして表示されたネットワークインターフェイス一覧。

lo0
ループバックアドレス

gif0
トンネリングを行う

en0
Ethernet

en1
有線のEthernet

en1
Air Mac

stf0
IPv6パケットをIPv4ネットワークにルーティングする

p2p0
Air Dropの機能用

awdl0
Handoffの機能用

bridge0
仮想インターフェイスを外部ネットワークに接続する

参考URL

http://www.tkd55.net/blog/?p=604
ターミナルからプライベートIPアドレスとMACアドレス、ルーティングテーブルを確認する - bambinya's blog
Murusの使い方その3 「Network interface」 | Sawayaka Trip!
https://support.apple.com/kb/PH18510?locale=ja_JP

2017-02-17

vimで構文ハイライトをいじった

メモ

f:id:noy72:20170217200405p:plain
こんな感じに。

おしゃれしたい

競技プログラミングでよく使うマクロやデータ構造に色をつけたくなったので構文ハイライトをいじった。

これでforとrepが肩を並べるよう（同じ色）になり、デバッグ用のマクロが目立つようになった。
あと、色がついて気分が良くなる。正直、あまり意味はない。

構文ファイル

自分はデフォルトのカラースキームを利用している。
whichやls -lでvimフォルダを探し出し、その中のcpp.vimファイルを変更することでハイライトを変更できた。

syn keyword cppType vector map
syn keyword cppStatement rep range
syn keyword cppConstant INF
syn keyword cppRawStringDelimiter debug show

cppRawStringDelimiterが何を表しているかはわからないが、とにかく目立つ色なのでdebug用マクロに設定。
cppTypeだけ長くなったので省略。

無駄にカラフルになって読みにくくなりそうである。

2017-02-13

sshでリモートマシンへログインする際にやったこと

メモ

ログインするだけなのに時間がかかった。
mac -> VMware CentOS7

opensshのインストール

yum install openssh-server

sshdサービスの起動

systemctl start sshd-service

ここでエラーが出て実行できなかった。SELinuxが原因な気がしたので、

setenforce permissive

で設定を変更した。
すると実行できた。

systemctl status sshd.service

で起動できているかを確認した。

その後sshで通信しようとするも、TLE。

ファイアウォールを確認する。

firewall-cmd --list-all

これでファイアウォールがsshを見逃してくれているかを確認。sshがservicesにあれば大丈夫っぽい。しかしログインできず。

自分はsshのポート番号を変更していたので、それもファイアウォールに示した。

firewall-cmd --permanent --add-port=<ポート番号>/tcp

その後、ログインできた。

とりあえずログインはできたので、次はセキュリティについて試す。

2017-02-11

グラフ　メモ

メモ

連結

任意の２点間に辺がある。
連結グラフは、グラフ上の任意の２点間に辺があるグラフのこと。

関節点

削除すると部分グラフが非連結になる点。

削除すると部分グラフが非連結になる辺。

強連結

任意の2点間に有向路がある、という条件を満たしている有向グラフの頂点の部分集合を強連結であるという。

強連結成分

強連結な集合Sに、どのような頂点集合を付け足しても強連結にならないとき、Sを強連結成分という。