2017-05-17

期待値

数学

期待値の計算は工夫の仕方がいろいろあります。次の問題を考えてみましょう。

問題

確率pで表が出るコインがあります。このコインを投げる操作を繰り返し，2回連続で表が出たらそこで操作を終了します。投げる回数の期待値を求めて下さい。

解法1

まずは，何も考えずに突き進むとどうなるかお見せいたします。

$n$ 回目で操作が終了する確率を $a_n$ とおくと， $a_n$ の一般項は

$a_n=\frac{p^2\left(\left(\frac{1-p+\sqrt{(1-p)(1+3p)}}{2}\right)^{n-1}-\left(\frac{1-p-\sqrt{(1-p)(1+3p)}}{2}\right)^{n-1}\right)}{\sqrt{(1-p)(1+3p)}}$

よって求める期待値は

$\sum_{k = 1}^\infty ka_k = \sum_{k=1}^\infty\frac{kp^2\left(\left(\frac{1-p+\sqrt{(1-p)(1+3p)}}{2}\right)^{k-1}-\left(\frac{1-p-\sqrt{(1-p)(1+3p)}}{2}\right)^{k-1}\right)}{\sqrt{(1-p)(1+3p)}} = \frac{1+p}{p^2}$

一般項を求めるために3項間漸化式を解き，級数の収束値を求めるために(1-x)S法(等差数列と等比数列の積の級数 $S=1+2x+3x^2+4x^3+\dots$ を求めるときにSをx倍してもとの級数Sから引く手法)を使いました。かなり面倒な計算でした。

でもなんとか答えは求まりました。 $\frac{1+p}{p^2}$ です。

実はこの問題には，工夫して解く方法があります。

期待値は，条件付き期待値の重み付き平均として表すことができます。つまり，全ての場合がA, B, …と場合分けされるとき，

$E(X) = P(A)E_A(X) + P(B)E_B(X) + \dots$

ということです。

簡単な例を出すと，サイコロを振ったとき

出た目が5以下である確率は $\frac{5}{6}$ 。出た目が5以下だったときの出た目の期待値は $\frac{1+2+3+4+5}{5}=3$ 。

出た目が6である確率は $\frac{1}{6}$ 。出た目が6であったときの出た目の期待値は $6$ (当たり前)。

出た目の期待値は $\frac{1+2+3+4+5+6}{6}=\frac{7}{2}$

です。出た目を確率変数Xでおき，出た目が5以下であった事象をA，6であった事象をBと表すと，これは

$P(A)=\frac{5}{6}$ ， $E_A(X)=3$

$P(B)=\frac{1}{6}$ ， $E_B(X)=6$

$E(X)=\frac{7}{2}$

という数式で表現することができます。そしてこのとき，

$P(A)E_A(X) + P(B)P_B(X) = \frac{7}{2} = E(X)$

が成り立っています。

このように，各平均の重み付き平均で全体の平均を求めるのと同じように，各場合の期待値の重み付き平均で全体の期待値を求めることができます。

コインの問題に戻ります。

この場合，場合分けして期待値を求めることはできませんが，いくつかの場合の期待値を，全体の期待値 $E(X)$ の式で表すことができます。すると， $E(X)$ の式で表された各場合の期待値の重み付き平均を左辺に，全体の期待値 $E(X)$ を右辺において方程式を立てて解くことで， $E(X)$ の値を求めることができます。

実際にやってみます。

解法2

投げる回数を確率変数 $X$ でおき，最初に2回連続で表が出る事象を $A$ ，最初に表が出て次に裏が出る事象を $B$ ，最初に裏が出る事象を $C$ と表すと，

$\displaystyle P(A)=p^2$

$\displaystyle E_A(X)=2$

$\displaystyle P(B)=p(1-p)$

$\displaystyle E_B(X)=E(X)+2$ 　(既に2回投げているが，この後いつ2回連続で表が出るかどうかについては最初の状況と変わらないので)

$\displaystyle P(C)=1-p$

$\displaystyle E_C(X)=E(X)+1$ 　(既に1回投げているが，この後いつ2回連続で表が出るかどうかについては最初の状況と変わらないので)

よって

$\displaystyle 2p^2 + p(1-p)(E(X)+2) + (1-p)(E(X)+1) = E(X)$

という方程式が立ちます。これを解くとなんと

$\displaystyle E(X)=\frac{p+1}{p^2}$

が得られるのです。

このように，期待値の計算においては工夫の仕方がいろいろあります。

それをうまく利用すれば，一見すると難しい問題も簡単に解けることがあります。

特にこの重み付き平均の考え方は強力です。

類題を上げておきます。

類題1

xy平面上の格子点のうち，x座標とy座標がともに偶数であるものが落とし穴になっている。落とし穴でないランダムな格子点に動く点Pくんが現れ，上下左右の格子点のどれかにランダムに移動することを繰り返す。動く点Pくんが落とし穴に落ちるまでに動く回数の期待値を求めよ。

この記事があなたの参考になれば幸いです。

2017-05-13

Numer0n

プログラミング

Numer0nは数当てゲームです。

コンピュータ戦のときは，コンピュータが決めた4桁の数をプレイヤーが当てようとします。

プレイヤーが何か4桁の数を一つ言うと，コンピュータはそれがどれくらい当たっているかを答えます。同じ桁に同じ数字があったら「EAT」，同じ数字があっても桁が違ったら「BITE」で，EATの数とBITEの数をコンピュータは教えてくれます。

例えば，コンピュータが決めた数が1493，プレイヤーの言った数が9471だった場合，「4」が同じ場所にあって，「9」と「1」はずれた場所にあるので，「1EAT 2BITE」となります。

これを繰り返してプレイヤーは最終的に答えに辿り着きます。

まずこのゲームをCで実装してみましょう。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(){
    int a, b;
    int eat, bite;
    srand((unsigned)time(NULL));
    do{
        a = rand()%9000 + 1000;
    }while(
        a%10 == a/10%10 
        || a%10 == a/100%10
        || a%10 == a/1000
        || a/10%10 == a/100%10
        || a/10%10 == a/1000
        || a/100%10 == a/1000
    );
    for(;;){
        scanf("%d", &b);
        if(a == b){
            printf("YES\n");
            return 0;
        }else{
            eat = bite = 0;
            if(a%10 == b%10) eat++;
            else if(a%10 == b/10%10) bite++;
            else if(a%10 == b/100%10) bite++;
            else if(a%10 == b/1000) bite++;
            if(a/10%10 == b%10) bite++;
            else if(a/10%10 == b/10%10) eat++;
            else if(a/10%10 == b/100%10) bite++;
            else if(a/10%10 == b/1000) bite++;
            if(a/100%10 == b%10) bite++;
            else if(a/100%10 == b/10%10) bite++;
            else if(a/100%10 == b/100%10) eat++;
            else if(a/100%10 == b/1000) bite++;
            if(a/1000 == b%10) bite++;
            else if(a/1000 == b/10%10) bite++;
            else if(a/1000 == b/100%10) bite++;
            else if(a/1000 == b/1000) eat++;
            printf("%dEAT %dBITE\n", eat, bite);
        }
    }
}

最初から4桁と決まっているのでこれでいいのでは？

…なんていう姿勢でいるといつか痛い目に遭います。綺麗なコードを心がけましょう。

今度はC++で実装することにします。

Number.h

#pragma once
#include <iostream>

const int Keta = 4, NMin = '0', NMax = '9';

class Ans {
	unsigned eat, bite;
public:
	Ans() : eat(0), bite(0) {}
	bool operator==(const Ans &ans) { return eat == ans.eat && bite == ans.bite; }
};

int check(char[]);

int judge(char[], char[], Ans &);

std::ostream &operator<<(std::ostream &os, const Ans &ans) {
	os << ans.eat << "EAT " << ans.bite << "BITE";
	return os;
}

Numer0n.cpp

#include "Number.h"
#include <cstdlib>
#include <ctime>

int constexpr factorization(int);

int main() {
	char a[Keta + 1], b[Keta + 1];
	Ans ans;
	srand((unsigned)time(NULL));
	do{
	    for(int i = 0; i < Keta; i++) a[i] = rand()%(NMax - NMin + 1) + NMin;
	}while(check(a));
	for(;;){
	    std::cin >> b;
	    if(!judge(a, b, ans)){
	        if(ans.eat == Keta) std::cout << "YES" << std::endl;
	        else std::cout << ans << std::endl;
	    }
	}
}

int constexpr factorization(int a) {
	return (a == 1) ? 1 : factorization(a - 1) * a;
}

int check(char a[]) {
	for (int i = 0; i < Keta; i++) if (a[i] < NMin || NMax < a[i]) return -1;
	for (int i = 1; i < Keta; i++)
		for (int j = 0; j < i; j++)
			if (a[i] == a[j]) return -1;
	return 0;
}

int judge(char a[], char b[], Ans &ans) {
	if (check(a) || check(b)) return -1;
	ans.eat = ans.bite = 0;
	for (int i = 0; i < Keta; i++)
		for (int j = 0; j < Keta; j++)
			if (a[i] == b[j]) {
				if (i == j) ans.eat++;
				else ans.bite++;
			}
	return 0;
}

綺麗になりました。めでたしめでたし。

最後に，aと比較した結果がansになるような数を全て出力する関数int search(char [], const Ans &);を作ります。例えば引数に「1928」と「2EAT 2BITE」を渡すと，「1298 1982 1829 8921 2918 9128」と出力する関数です。

この関数の実装は次のようになります。

int match(char a[], char b[]) {
	int count = 0;
	for (int i = 0; i < Keta; i++)
	    for (int j = 0; j < Keta; j++)
	        if (a[i] == b[j]) count++;
	return count;
}

int eat(char a[], char b[]) {
	int count = 0;
	for (int i = 0; i < Keta; i++) if (a[i] == b[i]) count++;
	return count;
}

int search(char a[], const Ans &_ans) {
	char b[Keta + 1];
	for (int i = 0; i < Keta - 1; i++) b[i] = NMin + i;
	b[Keta - 1] = NMin + Keta - 2;
	b[Keta] = '\0';
	char *cur = b + Keta - 1;
	char c[Keta];
	Ans ans;
	for (;;) {
		cur = b + Keta - 1;
		if (b + Keta + (*cur) <= cur + NMax) (*cur)++;
		else {
			do cur--; while (b + Keta + (*cur) > cur + NMax);
			if (b == cur + 1) return 0;
			for ((*cur++)++; cur < b + Keta; cur++) *cur = cur[-1] + 1;
		}
		if (_ans.eat + _ans.bite == match(a, b))
			for (int i = 0; i < factorization(Keta); i++) {
				for (int j = 0; j < Keta; j++) c[j] = b[j];
				int _i = i;
				for (int j = 2; j <= Keta; j++) {
					for (int k = 0; k < _i%j; k++) {
						int t = b[Keta - j];
						for (int l = Keta - j + 1; l < Keta; l++)
						    b[l - 1] = b[l];
						b[Keta - 1] = t;
					}
					_i /= j;
				}
				if (eat(a, b) == _ans.eat) std::cout << b << ' ';
				for (int j = 0; j < Keta; j++) b[j] = c[j];
			}
	}
}

ええ…5重ループですね。かいつまんで説明します。

まず0～9の10個の数字から4個選ぶ選び方は10C4=210通りあります。それぞれに対して，数の並べ替え方は4!=24通り。なんで初めから10P4=5040通りを試さないのかというと，並べ替えたときにeatとbiteの和が変わらないからです。

4個の数字を選んで，eatとbiteの和が合っているかどうかを確かめてから，それを並べ替えてeatの数を確かめています。

2017-05-13

何をやっても上手くいく人へ

世の中には神に呪われた人がいます。

呪われた人は，「何をやっても上手くいく」状態になります。

この記事はそういう人のために書いています。

まず，この呪いは自己暗示により解呪が可能です。

しかし僕はそのやり方を知りません。

自分で見つけてください。

でも呪われたままでも大丈夫です。

呪いの性質を知っていれば，困難無く生活できます。

まず，この呪いは「無意識にとった行動が常に最善となる」呪いです。

重要なのは，「悩んだ末の選択は最善とは限らない」ということです。

行動する前に少しでも悩んでしまったら，その後の選択は最善でない可能性が高いため，せめてできるだけ悪手を選ばないように自力で気を付けましょう。

次に，この呪いを利用しようとしてはいけません。

むしろ呪いに利用されていると考えるのがよいでしょう。

雲を掴もうとするのではなく，雲に乗ろうとするだけです。

利用しようとした瞬間，あなたの周囲の世界は崩れてゆきます。

最後に，「最善」のレベルを上げたい方のために，この呪いの効果を高める方法を教えます。

世の中には「した方がいいこと」と「しない方がいいこと」というものがあります。

行動が最善となるとはいえ，思ったことをそのまま行動に移しているよりは，ある程度自分を抑えた方がよりよい結果を生み出せます。

では，何が「した方がいいこと」で，何が「しない方がいいこと」なのでしょうか。

その判別方法となるのが「2諦」の考え方です。

何かをしようとして，何らかの理由で2回連続で失敗したら，それは「しない方がいいこと」であると諦める。

これが「2諦」です。

つまり，例えば少し離れたところにあるスマホを取りに行こうとして，1回目でつまづいて，2回目でスマホを取り落としたとします。その場合，スマホを開くと何か悪いことが起こるからと，スマホを開くことを諦めるのです。

2諦を心に決めると，全体の行動の約3割が制限されます。

これが「した方がいいこと」と「しない方がいいこと」の割合なのです。

神という存在を仮定すると，2諦は神が「何をするべきなのか」を我々に伝える手段として説明することもできます。

これによって同じ「最善」でもその結果をさらによいものにすることができます。

以上です。

お読みくださってありがとうございました。

2017-05-01

競プロ用語

プログラミング

twitter上の競プロerの文化や，erが使っている用語を紹介しようと思います。

・色

競プロのコンテストに出場すると，成績に応じてレートが変動します。レートは色分けされています。

例えばatcoderでは

色	レート
自由色	3200以上
赤	2800以上
オレンジ	2400以上
黄色	2000以上
青	1600以上
水色	1200以上
緑	800以上
茶色	400以上
灰色	0以上

と色分けされています。サイトによって少しずつ違いますが，どのサイトでも赤が一番強いというのは共通しているようです。

「○○コーダー」というのはこの色を指します。例えばレートが2000以上2400未満の人を「黄コーダー」と呼びます。

twitterのアイコンを自分の色に合わせておくと，どのくらい強いのか見た人がすぐに分かるので便利です。

赤コーダーの人が自分のtwitterアイコンをあえて灰色にすると，ハラスメント(後述)になります。

・リプライ

強いer同士の間では意味の分からないリプが常時飛び交っています。初めのうちは理解しようとしなくてもよいでしょう。いつか分かるときが来ます。

・ハラスメント

良い成績を取った人が「自分は頭が悪いので～」などと言っているとイラっとしませんか。このように謙遜によって相手に精神的攻撃を加える行為を「ハラスメント」と呼びます。また，格下の相手を過度に褒め称える行為もハラスメントに含まれます。

強いerはよくハラスメントをします。しかしこれは，ただ相手にダメージを与えて楽しんでいるわけではありません。ハラスメントをされた人が「なにくそ」と思って這い上がって来るのを待っているのです。つまりハラスメントは一種の優しさです。

ハラスメントをされたら，「自分は期待されているんだ」と思ってがんばりましょう。その努力はきっと報われます。

・なぞなぞ

一部のerは「クソなぞなぞ」をします。

「<クソなぞなぞ> ～～ってな～んだ？」の形式で出題され，リプで回答します。

その多くがくだらないダジャレによるものですが，このようななぞなぞを解くことは，人が何を言いたいのかを推察する能力の訓練となります。マヨ子さんという方とDEGwerさんという方がよくやっているので，見かけたら取り組みしましょう。

・575

俳句。それは，17文字で心を表現する日本の文化。

競プロerは，どうでもいいことをなぜか575調でツイートします。見かけたら「575」とリプして指摘しましょう。また，575の指摘に慣れ過ぎるあまり，「575」という指摘に対して「5」(「ごーしちご」が5音節なので)とリプを返すerもいるようです。そうしたら，「ご」は1音節なので，「1」と返しましょう。きっと「2」というリプが返ってきます。

typingwar

http://typingwar.trap.games/

タイピングゲーム。タイピング速度がレートに比例するという迷信があり，多くのerがこのゲームをやっています。

用語

競プロerの使う独特の用語をいくつか紹介しておきます。

「～完」…コンテストで何問完答したかを表す。「3完」で3問完答したという意味。この言い方は競プロに限らず，数学の試験においても使われているようである。

「プロ」…相手を褒める言葉。褒めるとはすなわち煽ることである。誰かが「～ができた」と呟いたらすかさず「プロ」とリプを飛ばすべし。また，「プロ」と言われたら，挨拶だと思って「趣味」と返すのがよい。

「はい」「いいえ」…感動詞。「はい」は肯定，「いいえ」は否定を表す。ネタツイの最後に「(いいえ)」と付けることで，それがネタツイであることを明確にすることができる。当たり前のことを言うときに最後に「(はい)」と付けることで，それが当たり前であることを明確にすることができる。「プロ」「趣味」と組み合わせて「はいプロ」「いいえ趣味」と使うこともできる。

「太陽」…0完，即ち一問も完答できなかったことを華々しく報告する際に使う言葉。「太陽をキメる」「太陽が生える」などと使う。

「罠」…一見正しいかのように思えるが実は間違っていること。間違ったことを言ってしまったとき，「これは罠で…」と訂正する。ネタツイとしてあえて間違ったことを言うときには，最後に「(これは罠)」とつけることで誤解を防ぐことができる。

「実質」…事実を誇張するときに使う。例えば，コンテストで簡単な問題が2問，難しい問題が3問出題されたとき，本当は3完したがそのうち2問はやるだけだったので実質1完，のように使う。誰かが「太陽」と言ったときは，その前に「実質」が省略されていることが多い。

「任意」…数学用語。「頭が悪いので任意の問題が解けない」とは，「どんな問題Pに対しても，『私はPが解けない』が成り立つ」，つまり「どんな問題も解けない」という意味である。「私以外の任意の人間がプロ」「任意のプロの成長速度が速い」など。

「頭」…頭脳。「頭がついていない」は，頭が悪いという意味。「頭が欲しい」は，頭が良くなりたいという意味。

「殴る」…やや強引に物事を解決すること。「頭で殴る」(頭脳を使ってやや強引に物事を解決する)，「セグ木で殴る」(セグメントツリーでやや強引にACする)など。

「うぃーん」…擬音語。歩く音，目を閉じる音，エゴサする音，ACする音など，何にでも使える万能の擬音語である。

「†」…ダガー。「†○○†」のように使い，○○の部分には悪魔的行為が入る。「†グローバル変数†みたいなウンコード」(C++でグローバル変数をむやみに使ってはいけない)など。

「ｷｬｯ///」…ｷｬｯｷｬｯ///ハラスメントは楽しいな！！ｷｬｯｷｬｯ////

「ア」…死。「～なのでア」「～してしまった(ア」など。

DEGwer構文…「はいプロ　世界一○○が上手　○○界のtourist　○○時代の終焉を告げる者　実質○○　○○するために生まれてきた男」の空欄を埋めることによって相手を煽る構文が完成する。touristはベラルーシ人の競プロer(強い)。例えば「起きた」というツイートに対して「はいプロ　世界一起床が上手　起床界のtourist　布団時代の終焉を告げる者　実質朝　起床するために生まれてきた男」などと使う。

双子構文…「僕は永遠にあなたの○○を抜かせません。どのようにして○○をしているのか教えていただけないでしょうか」と煽る。

「うぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。」…コピペ。とりあえずうぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。というリプを飛ばせばうぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。なのでうぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて間違いなし。うぃーんﾋﾞｰﾄﾋﾞｰﾄひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。の正しい発音の仕方はこちらで紹介されています。

うぃーんびーとびーと(セミのように)ひるど(勢いを殺さず滑らかに)うっくっく(大悪魔)えいえいえっと(前前前世)いずらいと(韻を踏んで勢い良く)いえい(後のらてとのギャップを作るように明るく)らて(神妙な面持ちで)
— "winj+i" (@wing3196) 2017年5月7日

私も練習してみましたが，「いえい」と「らて」のギャップが難しいようです。

これらの用語を使いこなせるようになるまでには時間がかかります。また，言語は生き物ですから，これらの用語も刻一刻と変化してゆきます。ただ，競プロの世界に飛び込んでいったとき，何も知らないのと基本的な単語を知っているのでは大きな差が生まれます。この記事が少しでもあなたの役に立てればと思います。

2017-05-01

競プロ

プログラミング

学校でパソコン同好会があり，僕はそのプログラミング部門で後輩に C/C++ を教えています。人にものを教えるというのは結構難しいんですね。

人にプログラミングを教えるにあたって最も苦労したのが「何を作ればいいのか分からない」ということ。

プログラムは書いた分だけ上手くなります。逆に言うと，自分で書かないと上達しません。

僕が小学生のときにプログラムが上達しなかったのも，作るべきものが特に無かったからです。

同好会でも，後輩たちはこれまで何をするともなく適当にコードを書いているだけでした。(ちなみに僕は自分が書いたバグだらけのコードを頑張って修正していました)

とにかく何かテーマが欲しい。何を作ればいいのかを提示して欲しい。

そんなとき僕が出会ったのが，競技プログラミングでした。

競技プログラミング。略して競プロ。

正しいプログラムをいかに早く書けるかを競う競技。

atcoder(https://atcoder.jp/) や codeforces(http://codeforces.com/)などのサイトで定期的にコンテストが開催されています。

例えば，「入力されたいくつかの数のうち，1が何個あるかを出力せよ」という問題が出たら，数を1つずつ読み込んで1の個数を数えるようなプログラムを書いて提出します。提出したら即座にジャッジ(正誤判定)が始まり，いくつかのテストケースが実行されます。プログラムが全て正しい出力をしたら「AC」(accepted)，出力が間違っていたら「WA」(wrong answer)，プログラムが重くて実行に時間がかかりすぎたら「TLE」(time limit exceeded)と表示されます。ACすると得点を得ます。

一回のコンテストでいくつかの問題が出題され，得点の合計を競います。

僕は今年1月に競プロを始め，その効果に驚きました。

競プロは実用的なプログラミング力をつけるのに適しています。

自分の書きたいものを書くより，与えられた問題を解くほうが，すぐに力がつきます。

というわけで，今年度からは同好会で競プロをやることにしたのです。

競プロをやる人のことを「競プロer」と呼びます。僕は単に「er」*1と呼びます。

日本人のerは，twitter上にたくさんいます。(僕が競プロを知ったのもtwitterを始めてからです)

twitter上のerは不思議な日本語を使います。「プロ」「はい」「いいえ」「これは罠」「太陽」などの言葉の使い方や，括弧の使い方が特徴的です。

また，過度な謙遜による煽りが多い世界なので，強くなるまでは会話に参加することができません。

ここら辺の詳しいことに関しては，また改めて記事を書きたいと思います。

ではまた。

…というかこの記事，書き方が下手だな。誰だこれ書いたやつ。

*1:口を半開きにして，「あー」と発音します。

2017-05-01

はじめての記事

初めまして。さちせにと言います。

「幸せに」と書いて「さちせに」と読みます。

高校生です。

考えることが好きだったのですが，色々なことを考えているうちに精神病になってしまいました。

このブログには，自分の考えていることや，勉強に関することなどを書きます。