読者です 読者をやめる 読者になる 読者になる

noyのブログ

プログラミングとかゲームとか

構文解析初心者でも解ける問題を集めた+解説

水色コーダーが構文解析の問題を解きました。その記録です。
問題の難易度は、AOJ−ICPC基準で300点前後だと思います。

構文解析とは

構文解析とは、やるだけ問題です。
ここ構文解析 Howto · GitHubにもそう書いてあります。
 
構文解析初心者の方は、まずはこれを読みましょう。
読みましょう

ここを読めば、この記事で解説している問題に挑めるはずです。

問題

計算機 | Aizu Online Judge

四則演算の問題です。
テンプレを間違いなく写しましょう。

Unordered Operators | Aizu Online Judge

問題概要

四則演算の優先順位を自由に入れ替えて、解を最大化しましょう。
ただし、割り算は使いません。

解法

全ての優先順位を全通り試せば良いです。
テンプレを見ると分かりますが、同じ関数にある演算子は優先順位が同じで、先に処理される演算子ほど優先度が高いです。
例えば、全ての演算子の優先順位を同じにしたければ、expr関数に全ての演算子を書けばいいです。

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です。

Operations with Finite Sets | Aizu Online Judge

問題概要

集合の演算を行う構文解析です。
演算子は 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' ではないです。

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

問題概要

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

解法

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

演算子 +, * は、与えられた数値のmax, minを取ればよいです。
- 演算子は、Operations with Finite Sets | Aizu Online Judgeの 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

Shipura | Aizu Online Judge

問題概要

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

解法

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

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

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

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

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

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

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

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

注意点

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

まとめ

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

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

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 - w0rp/ale: Asynchronous Lint Engine
同じようにインストール。
syntasticがあると衝突するのでアンインストールしておきます。

導入してわかったこと

syntasticと比べて速い

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

エラーメッセージは控えめ

エラー箇所にカーソルを合わせると、その行のエラーが下部(statusline)に表示されます。

結論

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

AOJ 1249 Make a Sequence

Make a Sequence | Aizu Online Judge
AOJ-ICPC 200点

所用時間:1時間30分
遅すぎる。実装力が足りてない。

問題概要

簡単に言うと3次元五目並。
n * n個のマスがある。黒いボールと白いボールを交互に置いていき、先にm個一直線に並べれば勝ち。
同じマスにボールは置ける。その場合、ボールは積まれる。n個まで積めるので、マスは実質n * n * n個ある。

解法

やるだけ。
マス目にボールを積んでいく操作は難しくない。ただ、勝敗判定が面倒。
dfsを用いて、あるボールから一直線に見ていき、同じボールがm個あるかを数えた。

”座標が範囲外だったらcontinueする”if文の条件を間違えたせいで40分程度余分に費やした。
関数の引数を無駄に増やしてはいけない。

コード

#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;
using namespace std;

void pushBall(int c[10][10][10], int top[10][10], int x, int y, int f){
    c[x][y][ top[x][y] ] = f;
    top[x][y]++;
}

void dfs(int n, int m, int x, int y, int z, int ball, int c[10][10][10], int &ans, int k, int dx, int dy, int dz){
    if(ans != -1) return;
    if(c[x][y][z] == ball) k++;
    else return;
    if(k == m){
        ans = ball;
        return;
    }

    int nx = x + dx;
    int ny = y + dy;
    int nz = z + dz;
    if(nx < 0 || nx >= n || ny < 0 || ny >= n || nz >= n || nz < 0) return;
    dfs(n,m,nx,ny,nz,ball,c,ans,k,dx,dy,dz);
}

int check(int c[10][10][10], int top[10][10], int n, int m){
    rep(i,n){
        rep(j,n){
            rep(k,n){
                if(c[i][j][k] == -1) continue;
                int tmp = -1;
                range(x,-1,2) range(y,-1,2) range(z,-1,2){
                    if(x == 0 && y == 0 && z == 0) continue;
                    dfs(n,m,i,j,k,c[i][j][k],c,tmp,0,x,y,z);
                }
                if(tmp != -1) return tmp;
            }
        }
    }
    return -1;
}

int main(){
    int n,m,q;
    while(cin >> n >> m >> q, n||m||q){
        int c[10][10][10]; //Black 0, white 1,
        memset(c,-1,sizeof(c));
        int top[10][10] = {0};
        vector<int> x, y;
        rep(i,q){
            int a, b;
            cin >> a >> b;
            a--; b--;
            x.emplace_back(a);
            y.emplace_back(b);
        }

        bool f = 0;
        rep(i,q){
            pushBall(c,top,x[i],y[i],i % 2);
            int tmp = check(c,top,n,m);
            if(tmp == 0){
                cout << "Black" << ' ' << i + 1 << endl;
                f = 1;
                break;
            }else if(tmp == 1){
                cout << "White" << ' ' << i + 1 << endl;
                f = 1;
                break;
            }
        }
        if(f == 0){
            cout << "Draw" << endl;
        }
    }
}

AOJ - 2170 Marked Ancestor

Marked Ancestor | Aizu Online Judge

問題概要

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

  • 頂点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;
    }
}

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の各章を1行でまとめた

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の内容を各章ごとに1行で表した。
章を要約するつもりで書いたが、上手くできているかはわからない。

第1部

02. 自分自身はソフトウェアを作れる能力を提供する事業である
03. キャリアの目的を決めよう
04. 人との付き合い方は大切
05. 職を得るためには人脈も大切
06. 雇用形態を理解しよう
07. どの程度専門特化すれば有利になるか考えよう
08. 自分会う環境はどんな会社にあるだろう
09. 出世するには、責任、主張、勉強が大事
10. プロとして正しい習慣を身につけよう
11. 仕事をやめるなら十分な準備をしてからにしよう
12. フリーランスになるなら、準備をきちんとしよう
13. 必要とされている製品を開発しよう
14. スタートアップを起業するなら上手に支援してもらおう
15. 在宅勤務にも課題がある
16. わざと困難な環境に身を置き、技術を身につけよう
17. 履歴書にこだわろう
18. テクノロジーに対し宗教的な概念を持つのは無駄

第2部

19. 自分自身をマーケティングするために、何らかのブランドを作ろう
20. 自分を表す良いブランドを作ろう
21. ブログは様々な点で役にたつ
22. 他人に本物の価値を与えることは成功への近道である
23. ソーシャルメディアを活用しよう
24. 人前で話すことで様々なチャンスを作れる
25. 本や記事を書けば自分の評価を高められる
26. 勇気を出して挑戦しよう

第3部

27. 学び方を学ぼう
28. 身につけたいスキルのうち、本当に重要な20%を学ぶ
29. 勉強する前に計画を立てる
30. 学んだことを自由に実践し、誰かに教えよう
31. 師匠を見つけよう
32. 弟子をとろう
33. 教えることでより深く理解できる
34. 成功に学位は必要ないが、あれば選択肢が広がる
35. 知識の隙間を埋めよう

第4部

36. 集中すれば生産性が上がる
37. タスクをスケジューリングしよう
38. ポモドーロテクニックを使おう
39. ノルマを設定し、タスクを処理しよう
40. モチベーションを保てる環境を作ろう
41. マルチタスクに向いているタスクとそうでないタスクを分けよう
42. 燃え尽き症候群を乗り越えることでモチベーションと興味は再び湧いてくる
43. 時間を浪費するのは止めよう
44. 目標を達成するためのルーチンを毎日組み込もう
45. 良い習慣を身につけよう
46. タスクは細かく分解しよう
47. ハードワークは問答無用で手をつけよう
48. 行動しないことで人生に大きな影響を及ぼす

第5部

49. 広い視点を持って給料を運用しよう
50. 自分の価値を把握しよう
51. オプション取引の仕組みを知ろう
52. 不動産投資の方法を知ろう
53. 引退の計画を立てよう
54. 利益を生まない借金はやめよう
55. 早期引退はできるよ

第6部

56. 健康に気を配ろう
57. 健康に関する目標を立てよう
58. 消費、摂取カロリーを元に、体重を増減するための計画を立てよう
59. 健康へのモチベーションを高めよう
60. 筋トレの正しい知識を身につけよう
61. 体脂肪率に気を配ろう
62. ランニングのメリットはたくさんある
63. スケジュールやフィットネスプランを改善しよう
64. ガジェットを活用しよう

第7部

65. 思考は自分自身に強く影響を与える
66. プラス思考を身につけよう
67. 自己イメージを変えよう
68. 恋愛ゲーム戦略を考えよう
69. 優れた本を読もう
70. 失敗を恐れない
71. 他人が言ったことを鵜呑みにしてはいけない

書籍

ジョン・ソンメズ 『SOFT SKILLS ソフトウェア開発者の人生マニュアル』 長尾高弘訳、日経BP社、2016年

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

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

lo0
ループバックアドレス

gif0
トンネリングを行う

en0
Ethernet

en1
有線のEthernet

en1
Air Mac

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

p2p0
Air Dropの機能用

awdl0
Handoffの機能用

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

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だけ長くなったので省略。

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