SRM 539 Div2 500 Over9000Rocks

問題概要

n個の箱がある。この中からいくつかの箱を選んで石を入れたい。

ただしそれぞれの箱には入れる石の下限と上限が決められており、その箱を選んだ場合は[下限, 上限]の個数の石を入れないといけない。

• X > 9000
• いくつかの箱を選んで石をいれたときに、入れた石の合計個数がXになる

という条件を満たすようなXの個数を求めよ。

ただし、入力値は以下の条件を満たす。

1 <= n <= 15

1 <= 下限値 <= 1,000,000

対応する下限値 <= 上限値 <= 1,000,000

解き方

まず選ぶ箱の集合を全列挙する。

箱の集合が決まれば、選んだ集合にいれることのできる石の合計値の下限、上限が求まる。あとは、この下限から上限までの範囲の値が選べるということを記憶するためのデータ構造があればよい。

div2 500で遅延セグ木書かせるのか。もっと楽な方法があるはず。と思って、そういば「いもす法」ってやつがあるのを思い出して書いてみた。

コード

「いもす法」便利。

上位陣の人は+/-されるところの点をmapで管理して書いていた。
自分のはint16_tでメモリ制限ぎりぎりセーフ解。

int16_t imos[15000010];

class Over9000Rocks {
  public:
  int countPossibilities(vector<int> lb, vector<int> ub) {
    memset(imos, 0, sizeof(imos));

    int n = lb.size();
    REP (mask, 1<<n) {
      if (!mask) continue;
      int l = 0;
      int r = 0;
      REP (i, n) {
        if (mask & 1 << i) {
          l += lb[i];
          r += ub[i];
        }
      }
      imos[l]++;
      imos[r+1]--;
    }

    int ret = 0;
    int cur = 0;
    FOR (i, 1, 15000010) {
      cur += imos[i];
      if (cur > 0 && i > 9000)
        ++ret;
    }
    
    return ret;
  }
};

EMアルゴリズムの分かりやすい資料

　EMアルゴリズムの分かりやすい資料を見つけた。半年くらい前に混合ガウス分布を例にした資料をもとに勉強してだいたい理解したつもりでいたが、いまいちしっくりきていない部分があったのでもう一度別の資料で勉強しなおした。

What is the expectation maximization algorithm?

これを読むと以下のことが理解できる。EMアルゴリズムの復習をしたいときは読み直すとよい。

• やりたいことのイメージ
• コイントスを用いたシンプルな例
• Eステップ、Mステップの名前の由来
• Eステップでは、潜在変数の確率分布を求める。実際には分布そのものではなく、十分な情報をもつ統計量の期待値を求める。
• Mステップでは、対数尤度を最大化するようにモデルを再構築する。
• EMアルゴリズムの応用例
• バイオインフォマティクス領域でよく使われるらしい
• DNAシーケンスのクラスタリング（多次元正規分布）
• よくあるEMアルゴリズム更新のイメージ図の理解（*注）
• Eステップで出した凹関数が求めたい真の関数の下限になっているのは何故か？
• Eステップで出した凹関数と真の関数が接するのは何故か？
• EMアルゴリズムでなぜ局所解に到達するのか？

注) 数学的に厳密な説明は載ってないが、イメージ的に分かる。

関数の括弧の中のセミコロン

　関数の定義で f(x; θ) のような表記があった。

xとθの関数なので f(x, θ) でいいのではと思ったが、セミコロンで区切られている。
セミコロンで区切ると、セミコロンの前は変数、セミコロンの後はパラメータという意味らしい。

f(x; θ)はパラメータθによって特徴付けられる、xを変数として受け取る関数fみたいなイメージ。
θは変数ではなく、fを定義するときに決定する固定値というふうに考える。

データ圧縮してscpする

　4.5GBあるファイルをscpで転送していて中々終わらずイライラしていたら、

「Dash! C Capital!」

という声が隣から聞こえた。
最初は何のことか分からなかったが、「-Cをつけるとデータ圧縮とscp同時にしてくれて速くなるよ。」ということだった。

$ scp -C source user@server:/path/to/backup

scpが遅い場合は、-Cをつける。今日もまた一つ新しい学びがあった。

生成モデルと識別モデルの違い

生成モデル（generative model）と識別モデル（discriminative model）の違いが理解できたのでメモっておく。

よくある定義
生成モデルは

識別モデルは

のようにyを予測する。
これだけ聞いても何のことやらよく分からん。

直感的な説明
識別モデルはクラスの境界を学習する。与えられたデータxが生成される確率は特に考慮せず、単に境界面のみを学習するモデル。SVM、決定木などは識別モデル。

生成モデルは、それぞれのクラスにおけるデータの分布を学習するモデル。生成モデルはグラフィカルモデルを使って表される。

これは分かりやすい。これ聞いた後だと式の意味も分かる。

直感的な説明と式を結びつけて考える
識別モデルは、

のように予測を行うモデル。例えば決定木の場合はデータxが与えられると、終端nodeのクラス分布を見ることで、そのxがクラスyに属する確率が分かる。そして尤もらしいクラスを予測値として用いる。このようにp(y|x)を最大化しているが、データxが生成される過程や確率に関しては何もモデリングしていない。

これに対して生成モデルは、

のように予測を行う。例えばベイジアンネットワークやマルコフ確率場などを用いたモデルの場合はp(y)、p(x|y)を定義し、ベイズの定理を使って事後確率が最大となるようなyを予測値として用いる。つまり、データxの生成過程やクラスごとのxの分布というものをモデリングすることで、結果を予測するようなモデルになっている。

SRM 531 Div2 600 NoRepeatPlaylist

問題概要
スマホにN曲の歌が入っている。
これらの曲を組み合わせてP曲のプレイリスト を作りたい。ただしプレイリストは以下の条件を満たす必要がある。
1) すべての曲は最低でも1回はプレイされなければならない
2) 同じ曲をプレイする場合は、最低でも間に別の曲をM曲プレイしなければならない
プレイリストの構成方法のパターン数を求めよ。

解法
よく分からななかったのでとりあえずDPしてみた。

const long long MOD = 1e9 + 7;
int N, M, P;
long long dp[124][124][124];

long long solve(int pos, int cnt, int ng) {
  if (pos == P)
    return cnt == N;
  if (cnt > N)
    return 0;
  if (ng >= N)
    return 0;
  
  long long &ret = dp[pos][cnt][ng];
  if (ret == -1) {
    ret = 0;
    ret += (cnt-ng) * solve(pos+1, cnt, min(ng+1, M));
    ret += (N-cnt) * solve(pos+1, cnt+1, min(ng+1, M));
    ret %= MOD;
  }
  return ret;
}

class NoRepeatPlaylist {
 public:
  int numPlaylists(int N, int M, int P) {
    ::N = N;
    ::M = M;
    ::P = P;
    memset(dp, -1, sizeof(dp));
    return solve(0, 0, 0);
  }
};

より高速な解法
(1)の条件がなければ簡単に計算できることに注目して包除原理する。
N曲以下を使って(2)を満たすパターン数を数える。
これには、N-1曲しか使ってないパターンがあるのでそれを引く....
という感じに足して引いてを繰り返す。

const long long MOD = 1e9 + 7;
long long comb[128][128];

class NoRepeatPlaylist {
 public:
  int numPlaylists(int N, int M, int P) {
    comb[0][0] = 1;
    for (int i = 1; i < 128; i++) {
      comb[i][0] = comb[i][i] = 1;
      for (int j = 1; j < i; j++)
        comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
    }

    int sign = 1;
    long long ret = 0;
    for (int i = N; i > 0; i--) {
      long long pat = 1;
      for (int j = 0; j < P; j++)
        pat = pat * max(i-j, i-M) % MOD;
      ret += sign * pat * comb[N][i];
      ret = (ret % MOD + MOD) % MOD;
      sign = -sign;
    }
    return ret;
  }
};

/usr/bin、/usr/sbin、/usr/local/binなどの違い

　自分が作ったスクリプトをどこに置くべきか迷っていたら、これらの違いについて気になったので調べてみた。違いは以下のとおり。

ディレクトリ名	説明	中に入っているバイナリ例
/bin	single user modeでも利用できるバイナリ。	date、cat、ls、bash、cdなど
/sbin	single user modeでも利用できるバイナリ。 supervisor権限が必要なもの。	fsck、mount、ping、dmesgなど
/usr/bin	システム全体で一般的に利用されるバイナリ。	make、awk、java、ccなど
/usr/sbin	システム全体で一般的に利用されるバイナリ。 supervisor権限が必要なもの。	sshd、syslogd、httpdなど
/usr/local/bin	システム全体で一般的に利用されるバイナリ。 システムパッケージに管理されていないもの。	tmux、subl、spark-shellなど
/usr/local/sbin	システム全体で一般的に利用されるバイナリ。 supervisor権限が必要なもの。 システムパッケージに管理されていないもの。	logrotateなど

ということで、自作のバイナリは/usr/local/bin、または、/usr/local/sbinに入れるのが正しいらしい。
ちなみに、システム全体ではなく自分が使うだけのバイナリであれば、~/binに入れるらしい。

参考
Differences between /bin, /sbin, /usr/bin, /usr/sbin, /usr/local/bin, /usr/local/sbin [duplicate]