ペンキ

一次元DPが大好きなので,ペンキ問題について書きます。

ペンキ問題は

おいおい,使いかけのペンキの缶を放っておいたら中のペンキが乾いてしまうよ。 | OJ

板がn枚あり,i番目の板の面積はsiです。

ペンキの缶がたくさん(加算無限個)あり,1缶分のペンキで面積Sを塗ることができます。

板のうち何枚かを選んで全てペンキで塗り残しなく塗りたいのですが,一度ペンキの缶を開けたら,中身を全て使い切らなければいけません。

塗れる面積の最大値を求めて下さい。

という問題です。

この問題を見て全探索とか考えてる人はね,DPの威力を思い知れよ。

はい,動的計画法は,値が整数であることを利用して大きな表を作るのが特徴です。

今回は,大きさΣs+1の1次元配列を使います。塗れるかどうかにだけ着目するのでstd::bitsetでいいです。

i番目までから選んだものの和としてありうるものは,i - 1番目までから選んだものの和としてありうるものにi番目の値を足したものと足さなかったものなので,動的計画法でできます。計算量はΣisi(だと思う)。全探索O(2^n)に比べれば,はい。(制約によるけど)

コードはこうなります:

#include <iostream>
#include <bitset>

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)

int main(){
	int n, s[110], S, sum = 0, hoge = 0;
	std::bitset<1100000> able(1);
	std::cin >> n;
	REP(i, n){
		std::cin >> s[i];
		sum += s[i];
	}
	REP(i, n){
		RREP(j, hoge + 1) if(able[j]) able[j + s[i]] = 1;
		hoge += s[i];
	}
	std::cin >> S;
	for(int i = sum / S * S;; i -= S) if(able[i]){
		std::cout << i << std::endl;
		return 0;
	}
}

 いいですか,このやり方は強いですよ。std::bitset<1100000>をstd::array<int>(sum)に変えれば選び方を全て区別して,条件を満たすものが何通りあるかを調べることができます。似たような問題がatcoderで何度も出題されています。

 

強いので,普段使っていないという方は是非使って下さい。強くお勧めします。

 

ではまた。

スタックとレジスタ

関数呼び出しにおいて,実引数はスタックまたはレジスタで渡されます。

適当なコンパイラでは関数は「まずスタックを読み込み,読み切ったら今度はレジスタから読み込む」という方式を採用しているようです(Borland,EasyIDECなど)。

これを利用して,次のようなコードが書けます。

#include <stdio.h>

int main(void){
	int i = 3, j = 11, k = 36;
	printf("%d %d %d\n");
	printf("%d %d %d %d\n", j * k = i * j = 5);
}

これをEasyIDECで実行すると,

「36 11 3

75 15 5 3」

と出力されます。printf関数は,「%d」を見つけて次の引数を読み込もうとしますが,スタックに何も格納されていないので,レジスタから値を読み込んでいるのです。

というかそもそもこのコード,左辺値でないものに代入しています。これは本来コンパイルエラーになるはずですが,EasyIDECはアマアマですね,プロじゃない。

どうやらEasyIDECは右から計算するようです。「j = 5」「k = i * j」「j * k」の順に計算され,EAXレジスタには75,ECXレジスタには15が残されます。printf関数はこれを読み込んでいるわけです。

恐ろしいですね。

 

やっぱりgccやclangを使いましょう。

ポインタとconst

ポインタはアドレスを格納する変数。

constは変数を書き換えないようにする修飾子。

この2つを組み合わせると面倒です。

int main(){
	int a, b;
	const int *p = &a;
	a = 10;
	//*p = 10;	エラー
	p = &b;
}
int main(){
	const int a = 10, b = 0;
	int const *p = &a;
	//a = 10;	エラー
	//*p = 10;	エラー
	p = &b;
}
int main(){
	const int a = 10, b = 0;
	//int *p = &a;	エラー
	p = &b;
}

 const int *型(int const *と書いても同じ)は,const int型へのポインタです。

int main(){
	int a, b;
	int * const p = &a;
	*p = 10;
	//p = &b;	エラー
}

 int * const型は,int型へのconstポインタです。

int main(){
	int a, b;
	const int * const p = &a;
	//*p = 10;	エラー
	//p = &b;	エラー
}

const int * const型(int const * constと書いても同じ)は,const int型へのconstポインタです。

ポインタのポインタをとってみましょう。

int main(){
	int a;
	int *p1, *p2;
	int **pp = &p1;
	**pp = 10;
	*pp = &a;
	pp = &p2;
}

これにconstを付けてみます。

int main(){
	int a;
	int *p1;
	const int *p2;
	const int **pp;
	//pp = &p1;	エラー
	pp = &p2;
	*pp = &a;
	//**pp = 10;	エラー
}

const int **は,const int *型へのポインタです。int *型はconst int *型に変換されましたが,int **型はconst int **型に変換できません。

int main(){
	int a;
	int *p1;
	int * const * pp;
	pp = &p1;
	//*pp = &a;	エラー
	**pp = 10;
}

 int * const *型は,int * const型へのポインタです。int **型はint * const *型に変換できます。int * const *の参照先のポインタは変更できませんが,参照先の参照先は変更できます。

int main(){
	int a;
	int *p1, *p2;
	int ** const pp = &p1;
	//pp = &p2;	エラー
	*pp = &a;
	**pp = 10;
}

int ** const型は,int *型へのconstポインタです。

思考と言語

この記事は完全に僕の独自の考えであり,決して学術的なものではないということを最初に断っておきます。この内容は安易に信じないでください。

 

まず,一つの事例を見てみましょう。

一家の息子であるTさんは,普段から自然に人の求めていることを察知できる人間でした。ある日来客があり,Tさんは客人に対して数々の自然な気配りをしました。客人が帰った後,母親はTさんに対して「Tは気配り上手ね」と言いました。すると次の日から,Tさんは人に対する気配りの仕方が分からず,逆に人に迷惑をかけるようになってしまいました。一体どうしたのでしょう。

 

この事例には,言語と思考の関係が顕著に表れています。言語と思考の関係について見ていきましょう。

 

まず,言語が無い状態で思考はできるでしょうか。これに関しては野矢茂樹さん他たくさんの研究者が研究しています。結論から言うと,言語が無いと論理的思考はできません。なぜかというと,言語が無いと,現実にないことを仮定することができないからです。仮定ができないと,未来を見通すこともできないし,後悔も生まれない。つまり言語は高等な思考に必須だということです。

では,実際の思考において言語はどのような役割を果たしているのか。

簡単に言うと,言語とは「今と過去を結びつける」ものです。今起こっている出来事を言語で表して,過去起こった同じような出来事と結び付ける。それを繰り返して,思考というものは成り立っています。逆に言うと,言語を使っている限り,思考は「過去に縛られている」ということです。過去に無かったものを新しく考え出すことは容易ではありません。むしろ,言語を以て何かを考えるときには必ず過去に考えたこと,感じたことと照らし合わせながら考えているのです。

また,言語で表現することによって,思考を外側から観測することと記憶・記録することが可能になります。メタ認知は言語で表現してから生じるものです。

ここまでは多くの人が常識と捉えているでしょう。

 

問題は,「思考を言語で表現する」ことはできても,「言語で表現された通りに思考する」ことはできないということです。「思考→言語」の変換は不可逆であり,「言語→思考」の変換ができません。

ある思考を一度言語化して観測すると,その観測した記憶が残っている限り,その思考を再現することはできません。観測した記憶を思考の記憶よりも先に思い出してしまい,思考の記憶から思考を再現する余地を失うからです。これが,最初のTさんの事例で起こっていたことです。

 

この現象を防ぐことは,残念ながらできません。では,起こってしまったときにはどうすればいいのか。

かつての自分の思考がどんなものであったかを,少しずつ思い出していくより他はありません。無理に思い出そうとしてはいけません。あまり悩まずに過ごしていれば,そのうちふっと思い出すときが来るかもしれません。ただその時を待つのみです。

 

この記事はここで終わりです。読んで下さってありがとうございました。

期待値

 

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

 

 問題

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

 

 解法1

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

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

{\displaystyle 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)}}}

よって求める期待値は

{\displaystyle \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くんが落とし穴に落ちるまでに動く回数の期待値を求めよ。

 

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

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の数を確かめています。

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

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

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

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

 

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

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

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

 

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

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

 

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

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

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

 

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

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

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

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

 

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

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

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

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

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

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

これが「2諦」です。

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

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

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

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

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

 

以上です。

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