プログラミング初心者の勉強日記

情報科学専攻です. 機械学習と競技プログラミングについて日々勉強しています.

MENU

パターン認識と機械学習 : グラフィカルモデル (準備編)

パターン認識と機械学習

パターン認識と機械学習 (Pattern Recognition and Machine Learning; PRML) のメイントピックの一つであるグラフィカルモデルについての記事を書いていきたいと思います.

1. 準備

加法定理と乗法定理

PRMLでは1章で確率論の基本事項を一通り紹介しています. ここではその中でも重要な二つ、加法定理と乗法定理について軽く紹介します.

  • 加法定理

    A \cap B = \phiのとき、 $$ P(A \cup B) = P(A) + P(B) $$ が成り立つことを加法定理と呼びます. 例えば、サイコロを投げて1が出る事象をAとし、3が出る事象をBとします. このとき、A \cap B = \phiであり、P(A) = P(B) = \frac{1}{6}です.

    したがって、加法定理より、サイコロを投げて1か3が出る確率は、P(A \cup B) = P(A) + P(B) = \frac{1}{6} + \frac{1}{6} = \frac{1}{3}となります.

    より一般系では、P(A \cup B) = P(A) + P(B) - P(A \cap B)となります. 上の加法定理はP(A \cap B) = 0 の場合の特殊なケースです.

  • 乗法定理

    他の事象Bを観測した下で、事象Aの起こる確率のことを、Bを条件とするAの条件付き確率と呼びP(A | B) = \frac{P(A \cap B)}{P(B)} と定義されます. この式の両辺にP(B)を掛けると、 $$ P(A | B)P(B) = P(A \cap B) $$ が得られ、これを乗法定理と呼びます. 条件付き確率の時は、P(B) = 0のとき分母に0が来てしまうため、定義できませんが、乗法定理の場合はP(B) = 0のときでも定義できます.

確率論はこの二つの定理から成り立っています.

2. グラフィカルモデルの特徴

確率的推論を用いた機械学習の分野では複雑なモデルも、加法定理と乗法定理を繰り返し適用しているだけです. したがって、純粋な代数的操作を行うだけで複雑なモデルも定式化して解く事ができるはず.

しかし、代数的操作をするをよりもモデルを図式的に表現し、グラフ上の操作をして解いた方が便利なケースもあります. ここで確率モデルの図式的表現を確率的グラフィカルモデルと呼びます.

3. 用語の説明

グラフはノードとリンクの集まりで形成されます. ここで確率的グラフィカルモデルでは、各ノードが確率変数を表し、リンクが変数間の確率的関係を表します. グラフは、「全確率分布が、一部の変数のみに依存する因子の席としてどのように分解可能か」という情報を表現します.

PRMLではまず、有向グラフで表現されるベイジアンネットワークについて議論していて、その後で無向グラフで表現されるマルコフ確率場について紹介しています.

  • ベイジアンネットワーク：確率変数間の因果関係を表現
  • マルコフ確率場：確率変数間の緩い束縛関係を表現

4. 参考文献

  • パターン認識と機械学習 下 第8章

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

  • 作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/02/29
  • メディア: 単行本
  • 購入: 6人 クリック: 14回
  • この商品を含むブログを見る

AtCoder Beginner Contest 110に参加しました

競技プログラミング

AtCoder Beginner Contest 110に参加したので記録を残しておきたいと思います.

問題のタイトルは以下のようになっています.

A. Maximize the Formula

問題の概要
  • 1以上9以下の整数1つが書かれた整数パネル3枚と'+'が書かれた演算子パネル1枚がある
  • これら4枚を横一列に並べてX + Yの形を作る.
  • 作れる数式から得られる値のうち最大となるものを出力
解法

3つの整数で2つの整数XとYを作ることを考える. 例えば1, 4, 6と与えられたら、X = 64、Y = 1としたとき65となり最大値をとる. またX = 61、Y = 4としてもよい.

要は2桁の数字の10の位に与えられた3つの整数の最大値を割り当ててあげればよい.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a;
    int A, B, C;
    cin >> A >> B >> C;
    a.push_back(A);
    a.push_back(B);
    a.push_back(C);
    vsort(a);
    int tmp = a[2] * 10 + a[1];
    int rsl = tmp + a[0];
    cout << rsl << endl;
}

B. 1 Dimensional World's Tale

問題の概要

(テストケースに不具合があった問題です.)

  • 一次元世界の中に帝国Aと帝国Bがあり、それぞれ座標X、Yに位置している.
  • A帝国は座標x_1, x_2, \cdots, x_N、B帝国は座標y_1, y_2, \cdots y_Mに支配下を置きたい.
  • 以下の3つの条件をすべて満たすZが存在すれば、合意が成立して戦争は起きないが、存在しない場合には戦争が起こる.
    • X < Z \leq Y
    • x_1, x_2, \cdots x_N < Z
    • y_1, y_2, \cdots y_M \geq Z
解法

2つ目の制約と3つ目の制約からmax(x_1, x_2, \cdots, c_N)はZ未満、min(y_1, y_2, \cdots y_M)はZ以上であるという制約を満たせばよい.

したがって、もし3つの制約を満たすZが存在するならば、Z=max(x_1, x_2, \cdots, x_N) + 1とし、このZがmin(y_1, y_2, \cdots y_M)より小さいことが必要である.

最後に、この選んだZが1つ目の制約を満たしているかを確認し、満たしていれば戦争が起きず、満たさないとき戦争が起きてしまう.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x, y;
    rep(i, 0, N) {
        int tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    rep(i, 0, M) {
        int tmp;
        cin >> tmp;
        y.push_back(tmp);
    }

    vsort(x);
    vsort(y);
    int rsl = x[N - 1] + 1;
    if(X < rsl and rsl <= Y) {

        if(y[0] < rsl) {
            cout << "War" << endl;
            return 0;
        }

        cout << "No War" << endl;
        return 0;
    }

    cout << "War" << endl;
}

余談ではありますが、'No War'と出力しなければいけないところ'Not War'として提出してしまい一度WAになってしまいました...

C. String Transformation

問題の概要
  • 英小文字のみからなる文字列S, Tが与えられる.
  • Sに対して次の操作を何度でも行うことができる.
    • 操作：2つの異なるc_1, c_2を選び、Sに含まれるすべてのc_1をc_2に、c_2をc1に置き換える.
  • 0回以上の操作で、SをTに一致させられるか？
解法

入力例にもある通り、'azzel' は、 c_1 = e、c_2 = lとすると'azzle'になり、c_1 = z、c_2 = pとすると、'apple'になるので、'apple'と一致させることができるということになります.

ここで、各文字列に含まれる英小文字の出現回数に着目してみます.

上の例でいうと、Sは「a =1回、z = 2回、e = 1回、l = 1回」であり、Tは「a = 1回、p = 2 回、l = 1回、e = 1回」です.

このときSの'z'をpに、'e'を'l'に、'l'を'e'に対応付けしてあげれば一致させることができます.

このように各英小文字の出現回数を数え、その出現回数がSとTで等しいとき（順不同）一致させることができ、それ以外は一致させることができないということになります.

実装では、出現回数を連想配列で求め、それをソートしたあとに等しいかどうか調べています.

すみません、嘘解法です.

例えば、S=aab、T=bccのときにYesと出力してしまいますが、SをTにすることは無理です.

実は、S中の同じ文字が違う文字に変換されることはありません. またT中の同じ文字に対しても同じことが言えます.

したがって、SやTの文字を先頭から見ていき、対応関係を確認していきます.

一致していればそのまま次の文字を確認し、異なる文字に変換されていることが確認できた時点でNoを出力するようにします.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S, T;
    cin >> S >> T;

    int used1[26], used2[26];
    rep(i, 0, 26) {
        used1[i] = -1;
        used2[i] = -1;
    }

    rep(i, 0, S.size()) {
        int tmp1 = int(S[i]) - 'a';
        int tmp2 = int(T[i]) - 'a';

        if(used1[tmp1] >= 0) {
            if(used1[tmp1] != tmp2) {
                cout << "No" << endl;
                return 0;
            }
        } else used1[tmp1] = tmp2;
        if(used2[tmp2] >= 0) {
            if(used2[tmp2] != tmp1) {
                cout << "No" << endl;
                return 0;
            }
        } else used2[tmp2] = tmp1;
    }

    cout << "Yes" << endl;
}

D. Factorization

問題の概要

a_1 \times a_2 \times \cdots a_N = Mとなる長さNの数列aあ何通りあるか、10^{9} + 7で割った余りを求める.

解法

Mを素因数分解するところで思考停止してしまい、時間内に解くことができませんでした...

それはさておき、やはりまずは、Mを素因数分解します.

そうすると、 $$ p_1^{b_i} \times p_2^{b_2} \times \cdots \times p_m^{b_m} = M $$

となります. ただし、ここでp_i (i = 1, 2, \cdots m)は素数です.

さらに、問題で与えられている数列aの各項に対しても素因数分解します.

そうすると、 $$ p_{i, 1}^{c_{i, 1}} \times p_{i, 2}^{c_{i, 2}} \cdots \times p_{i, m}^{c_{i, m}} = a_{i} $$

と表すことができます.

したがって、 $$ b_i = \sum_{k = 1}^{N} c_{k, i} $$ を満たすような選び方の場合の数を考える問題に帰着できます.

各iに関しては重複組み合わせの公式を用いて、{}_{N} H_{b_{i}} = {}_{N + b_i - 1} C_{b_{i}}で計算することができます.

これらの場合の数を、すべてのiについてかけ合わせてあげれば答えが求まります.

この組み合わせを求める方法については以下の記事がものすごく参考になりますのでリンクを貼っておきます. qiita.com

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

const ll mod = 1e9 + 7;

#define MAX_V 1000000
const int MAX = 510000;

ll fac[MAX], finv[MAX], inv[MAX];

void comInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    rep(i, 2, MAX) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

ll comb(ll n, ll k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}


map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    comInit();
    ll N, M;
    cin >> N >> M;
    map<ll, ll> m = prime_factor(M);
    ll rsl = 1;
    for(map<ll, ll>::iterator itr = m.begin(); itr != m.end(); itr++) {
        rsl *= (comb(itr->second + N - 1, N - 1) % mod);
        rsl %= mod;
    }

    cout << rsl << endl;
}

感想

今回C問題までを17分で解くことができました (ペナルティ抜きで). (B問題の出力する文字列を確認せずに提出してしまうというケアレスミスがあったのが非常に悔しいです...)

たまたま相性の良かった問題だったのかもしれませんが、少しばかり成長を確認することができたコンテストだったと思います.

C問題は嘘解法でのACだったので実質2完ですね... 精進します.

D問題は今回も時間内に解くことができませんでしたので、とりあえずD問題埋めを頑張ろうと思います. それに加えて、整数論をからめた問題をいつも落としているイメージなので、整数論についても学習しなおそうと思います.

統計学の基礎知識 : 変動係数、相関係数、偏相関係数

数学

今回は変動係数、相関係数、偏相関係数についての記事です.

最後に簡単なプログラムをpythonで書いたのでそちらも載せておきます.

1. 変動係数

標準偏差の他にデータの散らばり具合を測る指標を紹介します. 標準偏差について知りたい方は下の記事も参照してください.

www.tatsumiya-blog.tokyo

さて、例えばセンター試験の英語(200点満点)と学校の小テスト(30点満点) の平均と標準偏差が以下のように得られたとします. (平均や標準偏差は適当に設定しています.)

  • センター試験の英語 : 平均 = 160点、 標準偏差 = 12点
  • 学校の小テスト : 平均 = 23点 、標準偏差 = 2点

この時、標準偏差を参考にすると、学校の小テストの方がセンター試験の英語の標準偏差に比べて小さいので、散らばり具合は学校の小テストの方が小さいことになります.

しかし、学校の小テストは30点満点なのでセンター試験の英語に比べて値が散らばらないのは当然です. これは平均が大きく異なることに起因します.

したがって、平均が大きく異なるデータ群同士の散らばり具合を比較した時には単純に標準偏差の比較では間違った解釈となってしまいます.

そこで用いられる指標が変動係数 (CV, coefficient of variation) です. 変動係数は次のように定義されます.

$$ CV = \frac{s}{\overline{x}} $$

ここで、sは標準偏差、\overline{x}は平均です.

標準偏差を平均で標準化することにより異なる平均同士でも比較することができます. 平均に対して標準偏差がどの程度になるかを算出していることに等しいです.

変動係数を用いると、

  • センター試験の英語における変動係数 : \frac{12}{160} = 0.075
  • 学校の小テストにおける変動係数 : \frac{2}{23} = 0.087

となるので、標準偏差の大小関係と逆になっていることが確認できます.

2. 相関係数

例えば、経験的に駅の近さと家賃は関係していると考えられます. (駅から遠いほど家賃が高く、遠いほど家賃が安い)

このように2つの変数がどのような関係にあるかを知りたい時があります. また、このような互いの関係のことを相関 (correlation) と呼びます.

今、(駅までの所要時間、家賃）のデータを(1, 10), (1, 8), (2, 9), (2, 10), (3, 8), (5, 6), (8, 5), (10, 5), (15, 3), (20, 2)とします.

このデータの駅までの所要時間をx、家賃をyとし、二次平面上にプロットすることを考えます. この時できた図を散布図 (scatter diagram)と呼びます.

上の駅までの所要時間と家賃の関係をプロットした散布図を以下に示します.

f:id:linearml:20180922174831p:plain

散布図を見ると、駅から近い物件ほど家賃が安い傾向にあることがわかります.

このように片方の変数が大きくなるともう片方の変数が小さくなることを、負の相関があると呼びます.

逆に片方の変数が大きくなると、もう片方も大きくなる関係のことを、正の相関があると呼びます.

そのどちらでもないものを無相関と呼びます.

また、相関にもはっきりと正または負の関係が現れているものとそうでないものがあります. 前者を強い相関、後者を弱い相関と呼びます.

この強い相関、弱い相関を表す指標が相関係数です. 散布図やその他の表では視覚的に考察できましたが、定量的な評価には向いていませんでした.

そこで、相関係数を用いて定量的な評価をすることを考えます.

相関係数を求めるためには、共分散が必要なので、まず共分散について説明します.

共分散

2変数データ(x_1, y_1), \cdots, (x_n, y_n)が与えられたとします. このとき共分散は以下で定義されます.

$$ s_{xy} = \frac{1}{n} \sum_{i = 1}^{n} (x_i - \overline{x}) (y_i - \overline{y}) $$

(x_i - \overline{x})(y_i - \overline{y}) > 0のとき、x_i, y_iはそれぞれの平均より共に大きいか小さいことになります. 逆に(x_i - \overline{x})(y_i - \overline{y}) \lt 0のときは、どちらかが平均より大きくもう片方が小さいか、その逆となります.

これらを全ての観測値に対して計算し平均をとったものが共分散となります.

相関係数に話を戻します

共分散が正の値を取るならば、正の相関が、負の値を取るならば負の相関があることがわかります.

しかし、共分散は単位によって大きさが異なるため、2つの標準偏差で割ります. 2つの標準偏差で割ることで、相関係数の値は単位によらず、-1から1の間の値を取ることになります.

$$ r_{xy} = \frac{s_{xy}}{s_x s_y} $$

相関係数の値の絶対値が大きいほど強い相関となります.

3. 偏相関係数

相関がそんなに強くなくても上の相関係数の絶対値が大きくなることがあります.

例えば、ある県における各市の喫茶店の数とゲームセンターの数の2変数について考えます.

このとき、相関係数を計算すると0.86となったとします. 0.86は十分強い相関であると言えますが、経験的に喫茶店の数とゲームセンターの数の間に直接強い相関があるようには思えません.

f:id:linearml:20180922201811p:plain

これは、人口密度という第三の変数が、喫茶店の数とゲームセンターの数のそれぞれと強い相関があるため、見かけ上の相関が生じた可能性があります. (第3の変数によって現れる2変数の相関を見かけ上の相関と呼びます.)

ここで、x=喫茶店の数、y= ゲームセンターの数、z=人口密度の数とし、それぞれの相関係数を以下のように得られたとします.

  • 喫茶店の数とゲームセンターの数　0.86
  • 喫茶店の数と人口密度 0.87
  • ゲームセンターの数と人口密度 0.98

f:id:linearml:20180922201826p:plain

ここで、考えるのは、喫茶店の数とゲームセンターの数の間に強い相関があるように見えたのは、人口密度が影響していると考え、人口密度の影響を覗いた後の喫茶店の数とゲームセンターの数の間の相関を考えます. この第3の変数の影響を取り除いた後の2変数の相関係数を偏相関係数 (partial correlation coefficient)と呼び、r_{(xy\cdot z)}と書きます.

偏相関係数は以下のように定義されます.

$$ r_{(xy\cdot z)} = \frac{r_{xy} - r_{xz}r_{yz}}{\sqrt{1 - r_{xz}^{2}}\sqrt{1 - r_{yz}^{2}}} $$

この偏相関係数を用いると喫茶店の数とゲームセンターの数の偏相関係数は、 $$ r_{(xy\cdot z)} = \frac{0.80 - 0.87 \times 0.98}{\sqrt{1 - 0.87^{2}}\sqrt{1 - 0.98^{2}}} = 0.08 $$

となり、実際には相関が強くないことがわかります.

4. 実装例

最後に簡単ではありますが、pythonで書いたプログラムを載せておきます.

import math

A = [0.39, 0.72, 1.00, 1.52, 5.20, 9.54, 19.19, 30.07]
B = [0.24, 0.62, 1.00, 1.88, 11.86, 29.46, 84.01, 164.79]

def calMean(d) :
    sum_v = 0.0
    for di in d :
        sum_v += di
    rsl = sum_v / len(d)
    return rsl

def calVariance(d) :
    sum_v = 0.0
    mean_d = calMean(d)
    for di in d :
        sum_v += pow(di - mean_d, 2)
    rsl = sum_v / len(d) 
    return rsl

def calStandardDeviation(d) :
    variance_d = calVariance(d)
    rsl = math.sqrt(variance_d)
    return rsl

def calCovariance(x, y) :
    mean_x = calMean(x)
    mean_y = calMean(y)

    sum_v = 0.0
    for xi, yi in zip(x, y) :
        sum_v += (xi - mean_x) * (yi - mean_y)
    rsl = sum_v / len(x)
    return rsl

def calCorrelationCoefficient(x, y) :
    covariance_xy = calCovariance(x, y)
    sd_x = calStandardDeviation(x)
    sd_y = calStandardDeviation(y)

    rsl = covariance_xy / (sd_x * sd_y)
    return rsl

def calPartialCorrelationCoefficient(x, y, z) :
    r_xy = calCorrelationCoefficient(x, y)
    r_xz = calCorralationCoefficient(x, z)
    r_yz = calCorrelationCoefficient(y, z)

    rsl = (r_xy - r_xz * r_yz) / (math.sqrt(1 - pow(r_xz, 2)) * math.sqrt(1 - pow(r_yz, 2)))
    
    return rsl

calCovariance(x, y)

で共分散を、

calCorrelationCoefficient(x, y)

で相関係数を、

calPartialCorrelationCoefficient(x, y, z)

で偏相関係数、r_{(xy\cdot z)}を計算できます.

応用情報に最短で合格するためには

資格試験

1. 本記事について

本記事では、応用情報に最短で合格するにはどうしたら良いかについて、個人的な意見をだらだら述べていこうと思います.

2. 対象読者

あくまでも最短で合格するための個人的な意見ですので、

「仕事や研究に直接役立つための知識を身に付けたい」

「応用情報で満点(もしくはそれに近い点数)で合格したい」

といった方はこれ以降記事を読み進めていっても時間の無駄だと思います.

本記事は、

「就活の時に履歴書に書ける資格が今すぐ欲しい」

「会社でとりあえず取れと言われた (もしくは取ったらお金がもらえるからとりあえず取りたい）」

「まだまだ本番まで時間があると思って何も対策をしていなかったが流石に焦ってきた」

「苦手分野が多すぎて受かる気がしない... 何か戦略を立てないと」

など、「合格」に重きを置いていて、その先は受かってから考えようという方には何か少しでも情報提供ができるかもしれません.

また、ITパスポートや基本情報を受けたことがない方、もしくは過去に受験したことあるが納得のいく点数が取れなかった or 落ちてしまった方でも応用情報は十分受かることができる試験だと思っています.

3. こんな記事を読む時間すら惜しい方

オススメの勉強法を簡単にまとめましたので、これだけ読んであとはひたすら実践すれば良いと思います.

  1. 参考書を何か1冊読み切る. (分からない分野があっても良い. 私の場合「ネットワーク」、「データベース」はほぼ流し読み.)
  2. 午前 : 「過去問道場」を5年×2回(春、秋)
  3. 午後 : 「午後問題の重点対策」という本をやる

これだけです.

一つ注意して欲しいのが、午前対策を終えてから午後対策に入ろうと思っていてはダメです.

はっきり言って午前の対策が終わるのを待っていては時間の無駄です.

午前は過去問をひたすらやるだけですので、同時並行で「午後問題の重点対策」を進めてください.

4. 合格までに必要な勉強時間

こればっかりは個人差があるので断言できません.

普段から情報処理に慣れ親しんでいる人とそうでない人では必要な勉強時間が違ってくるのは当たり前ですのでそこは注意しておくべきです.

良く、「合格までに必要な勉強時間は○○時間」と言ったツイートや記事、また「○○日で受かる勉強法」といったブログを見かけますが、具体的な時間を気にしてはいけません.

同じ 「○○時間で受かる応用情報」という記事を参考にしても皆が○○時間で受かるわけではありません.

私は「○○時間やれば合格できる！」と断言はできませんが、合格するためにやることやらなくていいことは全員に共通すると思いますので、それを共有できたら良いなと思っています.

5. 応用情報とは

まずは応用情報試験がどのような形式で行われているかを知る必要があります.

応用情報試験は「午前」と「午後」に分かれていて、午前は「四肢択一」、午後は「記述式」です.

また制限時間はそれぞれ150分間です.

午前は80問中80問すべて解答しなければいけないのに対し、午後は大問11問中1問必須、4問選択です.

午前 午後
9 : 30 ~ 12 : 00 (150分) 13 : 00 ~ 15 : 30 (150分)
四肢択一 記述式
80問中80問解答 11問中5問解答

午前、午後それぞれで6割取れれば合格なので、少し多く見積もっても午前で50問、午後で大問3問分解ければ合格です.

また、午後は

  1. 情報セキュリティ (必須)
  2. ストラテジ
  3. プログラミング
  4. システムアーキテクチャ
  5. ネットワーク
  6. データベース
  7. 組込みシステム開発
  8. 情報システム開発
  9. プロジェクトマネジメント
  10. ITサービスマネジメント
  11. システム監査

の中から選択して解答しますので、どの問題を選択するかが合格の鍵を握っています.

6. 午前、午後に共通してやること

まずなんでも良いので参考書を一冊読みましょう.

このとき、一回で全部覚えようとしてはダメです.

どの参考書も分野ごとにセクション分けされていると思いますので、時間がかかりそうだと思った分野は後回しにして、とにかく1冊読み切ります.

ちなみに私は「応用情報技術者 合格教本」という非常に有名な物を購入しましたが、「ネットワーク」と「データベース」のところは、流し読みをしただけです. (1周目はしっかり読もうとしたのですが、興味があまりなかったので頭に入ってきませんでした.)

平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)

平成30年度【春期】【秋期】応用情報技術者 合格教本 (情報処理技術者試験)

これ以降私はこの2分野については完全に切ることにしました.

「ネットワーク」と「データベース」なくして情報処理を語るなんてと思いますが、合格するだけなら必要ないのです. これらの分野は合格した後ゆっくりと勉強すれば良いのですから.

この合格教本は非常に分かりやすく、買って損はないのですが、(本屋や図書館で手に取ってもらえれば分かりますが)分厚すぎて、全部理解するのはかなりのハードワークです.

資格試験勉強の他に、仕事や研究をやらなくてはならないはずなので、全部を読んでいる時間はありません.

なので、大抵の参考書では1章に「基礎知識のまとめ」が書いてあると思うので、それはやるとして、その他の細かい知識については、なんか見たことある程度でも良いと自分に言い聞かせます.

むしろ2分野ぐらいだったら全く見たことなくても受かります (それがネットワークとデータベースだったとしても).

7. 午前対策

参考書を1冊とりあえず一周してみたら、午前は過去問をひたすら解きます.

午前は過去問の量で決まります. 正直参考書を読まずに過去問を解き続けるだけでも午前だけなら合格点を超えることは可能です.

そのとき皆が使用しているのは「過去問道場」というサイトでしょう.

これを私は、5年分 × 2回 (春、秋)やりました. (具体的には平成23年 ~ 平成27年です. )

なので、最新の試験から5年さかのぼれば午前に関しては十分すぎると思います.

「過去問道場」では問題に対して答えるとすぐに正解不正解がわかる一問一答式です. (以下に一例を示します.)

f:id:linearml:20180918045405p:plain

f:id:linearml:20180918045429p:plain

各問題に対して簡単な解説が載っているので、間違えたときはその解説を見てすぐに復習をすることができます.

このとき、わからない単語があれば、参考書に戻ってそのことが書いてあるところだけを読むようにします.

ですから、1周目以降は辞書がわりに使うことをオススメします.

過去問を解き続ければわかるのですが、体感でも半分近くは同じ問題が出題されています.

これが午前問題は過去問の量で決まるという大きな理由です. 計算問題も選択肢まで同じなので、本番は計算時間短縮にもなります. 逆に見たことない計算問題は捨て問だと思っても十分受かります.

半分近くは過去問で出題された問題なのだから、過去問を完璧にしたら40問近く正解することができるということになります. 合格には多く見積もっても50問正解すれば良いので、後40問中10問を解くことができれば午前クリアです.

なので、午前はとにかく過去問をやりましょう. 参考書を1周するより過去問1年分解いた方が圧倒的に得点が伸びます.

1年分解き終わったら間違えた問題だけ解き直しをする機能も付いていますので、復習を行ってください.

私は、理解していない問題があっても良いからとりあえず全問正解するまで解き直し続けました. (この単語があるから答えはこれだ！といった思考で正解しても良しとしていました.)

10回分なんて多すぎ...と思うかもしれませんが、1日1回分でも10日で終わるのでそんな身構える必要はないと思います. しかも、最初は時間がかかっても4回分を解き終わった頃には見たことある問題がかなりあるはずなので、短い時間で1回分時終えることができます.

8. 午後対策

午後は記述式ですので、こちらは少し本格的に対策や戦略を練る必要があります.

まず、午後対策には「午後問題の重点対策」を購入することをオススメします. (午後はこれだけやっていれば十分です.　過去問を別で用意してやる必要はありません.)

毎年出版されますが、対して内容が変わってないので、気にならない方は中古で購入するのも良いでしょう.

2018 応用情報技術者 午後問題の重点対策 (午後問題対策シリーズ)

2018 応用情報技術者 午後問題の重点対策 (午後問題対策シリーズ)

この本は、まず、午後をどのように対策したら良いかについて紹介していて、その後各分野について、確認事項をまとめてくれています. その後に問題演習とその解説が載っています.

各分野の確認事項は、参考書で得た知識の確認にもなりますし、抜けているところがあれば、そのまとめを読むことで補うことができます.

なお、先ほども記載しましたが、午後は11の分野から1つが必須で4つ選択して解答します.

  1. 情報セキュリティ (必須)
  2. ストラテジ
  3. プログラミング
  4. システムアーキテクチャ
  5. ネットワーク
  6. データベース
  7. 組込みシステム開発
  8. 情報システム開発
  9. プロジェクトマネジメント
  10. ITサービスマネジメント
  11. システム監査

情報セキュリティは必須で解かなければいけないのであまり苦手意識を作りたくないところです.

情報セキュリティについては確認事項のまとめを読んであとは演習に入ることをオススメします.

この分野をまた参考書で一から読み直すなんて時間は勿体無いです. あくまでも2周目以降は、参考書は辞書がわりに使うべきで勉強するものではありません.

さて、問題は残りの10問のうち4問、何を選択するかです.

よく「オススメの分野はこれだ！」みたいな記事を見かけますが、こちらも勉強時間同様、人それぞれなので、参考程度に見るだけにして、自分で考える必要があると思います.

アドバイスできることとしては、

  • 理系で、計算問題なら得意という方は組み込みシステム開発がオススメです. ほぼ前提知識なしで、文章に沿って計算問題を解くことができます.

  • 文系の方はストラテジやマネジメントの問題を中心に勉強するのが良いかと思います. たくさんのブログで言われていることですが、これらの分野はほぼ国語の問題です. なので、「計算は苦手」、「プログラミングわからない」という方には取り組みやすいと思います. しかし、試験によって難易度に差がかなりあるように感じますので、そこは注意しておく必要がありそうです.

さて、それらを踏まえて、4問選択しなければいけないのですが、4分野だけに絞って勉強するのは非常に危険です.

結論から言いますと、4分野 + 2分野は保険で勉強して行くことをオススメします. 最低でも1分野は余分に対策しましょう.

そのうちほぼ確実に満点取れる分野を1つ作れるとかなり余裕が生まれます.

具体的には、そこで20点取れれば、残りの4分野で40点取れれば良いことになります.

つまり、1つの大問で20点、残りの全ての大問で半分解ければ合格です. (私自身、本番で2 ~ 3割ぐらいしか解けなかった分野がありましたが20点取れた分野があったおかげで助かっています.)

例としては、 (18 + 6 + 16 + 14 + 6 = 60)で合格ですので、8割以上取れる分野を2つ、もしくは20点取れる分野を1つもっておくとほぼ間違いなく合格できます.

なので6分野の勉強はするんだけれども、そのうちの2つは得意分野になるように、参考書を読んで問題演習を繰り返すのが良いと思います.

「11分野をやらなきゃいけない... 辛い...」

ではなく

「たった2分野で良いのか！」

という思考に変えるべきです.

もう一つ午後対策で注意すべき点は、午前対策を終えた後で午後対策をしようとしないことです.

応用情報は圧倒的に午後の対策に時間をかけるべきですので、午前の対策の完成を待っていては時間が足りません.

ですから、参考書を1周したら、午前対策で「過去問道場」をやると同時に「重点対策」に取り組むべきです.

9. 前日やること

まず午前ですが、今まで解いた問題のうち間違えた問題を解き直しましょう.

別に全部やる必要はありませんが、できるだけ多くやると安心でしょう.

午後は、「重点問題集」の自分が選んだ6分野についての確認事項のまとめを読むだけで良いでしょう.

前日に午後の問題を解いても疲れるだけですので...

10. 当日

過去問道場を解いた方なら、半分ぐらいは同じ問題に出くわすので、時間が足りないということはまずないでしょう.

落ち着いて、マークミスをせずに解くだけです.

午後問題は、まず、どの問題なら解けそうかを確認しておくと良いと思います. ある程度解く問題を決めたら実際に問題に取り掛かる方法が私にはあっていました.

また、どうしてもわからない問題に出くわした場合でも、文中のそれっぽい長さの文を適当に書いておくともしかしたら部分点がくるかもしれません. 特にストラテジ、マネジメント系の問題は答えは文中に隠されているので、当てずっぽうでも当たる可能性は十分にあります.

11. まとめ

オススメの勉強の流れをまとめておきます.

  1. 参考書を一読
  2. 午前は過去問道場をひたすら解く
  3. 午後は重点対策の確認事項->問題演習

これだけです.

あくまでも私個人の意見ですので、人それぞれ合う合わないがあると思いますが、少しでも役に立つ情報が提供できていれば良いなと思っております.

AtCoder Beginner Contest 104に参加しました

競技プログラミング

久しぶりにリアルタイムでAtCoderに参加したのでその感想でも書いておこうかと思います.

今回参加したコンテストはAtCoder Beginner Contest 104です

問題のタイトルは以下のようになっています.

  • A . Rated for Me
  • B . AcCepted
  • C . All Green
  • D . We Love ABC

A. Rated for Me

問題の概要

  • 次に開催されるコンテストABCではレートが1200未満の人のレートが変動する.

  • その次に開催されるコンテストARCではレートが2800未満の人のレートが変動する.

  • そのさらに次に開催されるコンテストAGCでは全ての人のレートが変動する.

  • Q . レートがRの人のレートが変動する次のコンテストは何でしょう?

解法

単純な条件分岐で解けます.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
// ascending order
#define asort(array, N) sort(array, array + N)
// descending order
#define asort_r(array, N) sort(array, array + N, greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r;
    cin >> r;
    if(r < 1200) cout << "ABC" << endl;
    else if (r < 2800) cout << "ARC" << endl;
    else cout << "AGC" << endl;
}

B. AcCepted

問題の概要

  • 英大文字か英小文字からなる文字列Sが与えられる
  • Sが次の条件を全て満たすかどうかを判定する
    • Sの先頭の文字は'A'である.
    • Sの先頭から3文字目と末尾から2文字目の間に'C'がちょうど1個含まれる.
    • それ以外のSの文字は全て小文字である.
  • 以上の条件を満たすとき'AC'、そうでなければ'WA'と出力

解法

条件を上から順に辿っていき、全部満たしたら'AC'を、どれか一つでも条件に反していたら'WA'を出力すれば良いです.

ただ、焦ってしまい正しく条件分岐ができておらず、2回も間違ったソースコードを提出してしまいました...

少し複雑ですが、焦らず一つ一つ条件を書いていけば通せます. (物凄く汚いソースコードですがあげておきます.)

ちなみに、急にfor文をそのまま書いてあるのは、用意していたテンプレートファイルとは違うものをコピーしてしまい、ずっとrepの行で怒られていたからです.

コンテスト中に repが無いファイルを使っていたことに気づかず物凄く焦っていました.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
// ascending order
#define asort(array, N) sort(array, array + N)
// descending order
#define asort_r(array, N) sort(array, array + N, greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int n = s.size();
    if(s[0] != 'A') {
        cout << "WA" << endl;
        return 0;
    }

    int count = 0;
    int idx = 0;

    for(int i = 2; i < n - 1; i++) {
        if(s[i] == 'C') { 
            count++;
            idx = i;
        }
    }
    if(count != 1) {
        cout << "WA" << endl;
        return 0;
    }

    for(int i = 1; i < n; i++) {
        if(i == idx) continue;
        if('A' <= s[i] && s[i] <= 'Z') {
            cout << "WA" << endl;
            return 0;
        }
    }
    cout << "AC" << endl;
}

C. All Green

問題の概要

  • 問題集があって、それぞれの問題には難易度に応じて点数がつけられている.
  • i \leq i \leq Dであるiに対して、100i点をつけられた問題がp_i問存在.
  • 問題集を解いて得られるスコアは以下の2つの要素の和で与えられる.
    • 基本スコア : 解いた問題全ての配点の合計.
    • ボーナス : 100i点の問題p_i問を全て解いた場合、ボーナスとして、基本スコアとは別にc_i点獲得できる.
  • 目標スコアがG点以上の人は少なくとも何問の問題を解く必要があるか.

解法

Twitterとかで見ると本問題はいつものC問題より少し難しめみたいですね.

私は、まだ競プロをはじめてまもないため、いつものコンテストとの比較ができないので、Twitterではこういった情報が手に入って楽しいなと感じました.

さて、公式での解答やTwitterでの解答とは違うのですが、一応紹介しておきます.

私は、最近勉強していたDPを用いて解きました.

今回は、どこまでの問題を解いたのかと、それらの問題で何問解いたのかという状態を考えました.

つまり、dp[i][j] : 100i点がつけられている問題までを使ってj問解いたときに獲得できる最大得点

としました.

こうしたとき、最終出力はdp[D][i] \geq Gを最初に満たすiとなります.

(問題は全部で100D点がつけられているものまであり、はじめて目標スコアであるGを超える問題数が答えです.)

ここから漸化式を立てるのですが、今回の問題で気をつけたいのは基本スコアとは別でボーナスがあることです.

このボーナスを考慮に入れながら値を更新していく必要があります.

$$ dp[i + 1] = \begin{cases} max(dp[i + 1][j], dp[i][j - k] + 100 (i + 1) \times k + c[i]) & j \geq k かつ k = p[i]\\ max(dp[i + 1][j], dp[i][j - k] + 100 (i + 1) \times k) & j \geq k かつ k \neq p[i] \\ max(dp[i + 1][j], dp[i][j]) \end{cases} $$

としました. ただし、0 \leq k \leq p[i]で、100i点の問題のうち解いた数を表しています.

100i点が付いている問題の問題数より多くは解くことが許されていないため、kには条件がついています.

1つめの式は、100i点が付いている問題を全部解いたときに相当します.

2つめの式は、100i点が付いている問題を何問か解いたときに相当します.

3つめの式は、100i点が付いている問題を解かないときに相当します.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int d, g;
    cin >> d >> g;
    int p[d], c[d];
    int num = 0;
    rep(i, 0, d) {
        cin >> p[i] >> c[i];
        num += p[i];
    }
    int dp[d + 1][num + 1];
    rep(i, 0, d + 1) rep(j, 0, num + 1) dp[i][j] = 0;

    rep(i, 0, d) {
        rep(j, 0, num + 1) {
            rep(k, 0, p[i] + 1) {
                if(j >= k) {
                    if(k == p[i]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k] + 100 * (i + 1) * k + c[i]);
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k] + 100 * (i + 1) * k);
                } else dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            }
        }
    }
    
    rep(i, 0, num + 1) {
        if(dp[d][i] >= g) {
            cout << i << endl;
            return 0;
        }
    }
}

D. We Love ABC

問題の概要

  • 文字列TのABC数を以下の条件を全て満たす整数の組み(i,j,k)の個数と定義
    • 1 \leq i < j < k \leq |T|
    • T_i = 'A'
    • T_j = 'B'
    • T_k = 'C'
  • 与えられる文字列は'A','B','C','?'のいずれか.
  • '?'をそれぞれ'A','B','C'に置き換えて新しい文字列が作られる.
  • これらの文字列全てのABC数を求めよ.

解法(解けませんでした)

コンテストではTLEで終わってしまったので、正解の解法をここで紹介できませんが、記録として残しておきたいと思います.

正解のアルゴリズムが知りたいという方はこれより下を見ても何も得られないので、ブラウザバックしてください.

さて、私はTLE覚悟で深さ優先探索を使って実装しました.

どうせDP何だろうなと思ってはいたのですが、とりあえず手は動かそうと思い、深さ優先探索で解きました. (もちろん結果はTLEでした.)

各'?'に対して'A','B','C'の3通りで置き換えることができるので、ひたすらどんどん置き換えて全パターン列挙していきます.

'?'の数と置き換えた回数が一致したら一番深くまで探索したということにし、一つ前に戻って別の文字に置き換えていきます.

例えば、'??'に対しては、'A?' -> 'AA'('?'の数と置き換えた回数が一致したのでABC数を求めて一つ前に戻る) -> 'AB' -> 'AC' -> 'BA' -> ... -> 'CC'となります.

これは単純な深さ優先でかけます.

一応書いたのであげておきます.

8問ACで残りはTLEでした...

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int checkABC(string s) {
    int count = 0;
    rep(i, 0, s.size()) {
        rep(j, i + 1, s.size()) {
            rep(k, j + 1, s.size()) {
                if(s[i] == 'A' && s[j] == 'B' && s[k] == 'C') count++;
            }
        }
    }
    return count;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int Q;
    rep(i, 0, s.size()) {
        if(s[i] == '?') Q++;
    }

    if(Q == 0) {
        cout << checkABC(s) << endl;
        return 0;
    }
    queue <string> q;

    char dx[3] = {'A', 'B', 'C'};
    string init[3] = {"A", "B", "C"};

    int ans = 0;
    int mod = 1e9 + 7;
    rep(i, 0, 3) {
        q.push(init[i]);

        string tmpString;
        while(q.size()) {
            tmpString = q.front();
            q.pop();
            if(tmpString.size() == Q) {
                string tmp = s;
                int k = 0;
                rep(j, 0, s.size()) {
                    if(s[j] == '?') {
                        tmp[j] = tmpString[k];
                        k++;
                    }
                }
                ans += checkABC(tmp) % mod;
                continue;
            }
            rep(i, 0, 3) {
                string newString = tmpString + dx[i];
                q.push(newString);
            }
        }
    }
    cout << ans << endl;
}

感想

久しぶりのリアルタイムでのコンテスト参加だったのですが、いつもより少し難しめと言われているC問題を解けたのでとても嬉しいです.

少し前までDPなんて一生できるようにならないと思ってたのですが、こうやってリアルタイムでのコンテストでもDPを使えるようになりました. (今回たまたまできただけですが...)

なので、まだDPってなに？って思っている方は、こちらの記事を一通り実装して見るといいと思います. qiita.com

今回のD問題は私には無理でした...

公式解説や他の人の解答を見てしっかり勉強します.