2016-03-19

lay_contest beta round 00001 (in Japanese) B問題月日

問題概要

m月d日をm/dとする。2016年においてa月b日からc月d日まで異なる有理数はいくつあるか。

解答内容

本来は分子と分母の組ををsetに突っ込んでいくのが想定解答かと思うけど、自分は小数で保持しました

コード

#include<iostream>
#include<set>

int main() {
	int n;
	std::cin >> n;

	int month[13] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };


	for (int i = 0; i < n; i++) {
		int sm, sd, em, ed;
		std::set<double> s;
		std::cin >> sm >> sd >> em >> ed;
		for (int j = sm; j <= em; j++) {
			for (int k = sd; k <= month[j] && (j != em || k <= ed); k++) {
				s.insert(1.0 * j / k);
			}
			sd = 1;
		}
		std::cout << s.size() << std::endl;
	}
	return 0;
}

2016-03-19

lay_contest beta round 00001 (in Japanese) A問題勝者

競技プログラミング HackerRank

問題概要

自分とライバル、どちらの点数が高いのか勝負！

A問題は4点、B問題は7点、C問題は17点、D問題は22点。

自分が解いた問題とライバルが解いた問題が与えられるので自分がライバルに勝てば”WIN"を出力、負ければ”LOSE"を出力、引き分けなら”DOTEN"を出力する

コード

#include<iostream>
#include<map>

int main() {
    int n;
    std::cin >> n;

    std::map<char, int> m;
    m['A'] = 4;
    m['B'] = 7;
    m['C'] = 17;
    m['D'] = 22;

    for (int i = 0; i < n; i++) {
        int score[2] = { 0 };
        for (int j = 0; j < 2; j++) {
            int solved;
            std::cin >> solved;
            for (int k = 0; k < solved; k++) {
                char q;
                std::cin >> q;
                score[j] += m[q];
            }
        }
        if (score[0] > score[1]) std::cout << "WIN" << std::endl;
        else if (score[0] < score[1]) std::cout << "LOSE" << std::endl;
        else std::cout << "DOTEN" << std::endl;
    }
    return 0;
}

2016-03-16

the art of computer programming 1.2.3 を読む

taocp the_art_of_computer_programming

1.2.3 総和と乗積

式(13)について

$\sum_{i=0}^n\sum_{j=0}^ia_ia_j=\frac{1}{2}((\sum_{i=0}^na_i)^2+(\sum_{i=0}^na_i^2) )$

この式の左辺の計算量は $O(n^2)$ で、右辺は $O(n)$ である。

この2つの計算量の違いは大きく、左辺は $n=10000$ で、1億回の計算することになる(実際は5千万回ほど)。

しかし、左辺は同じ $n=10000$ でも計算回数は1万回(実際は1万回の計算が2回あるので2万回の計算が必要)で終わる。

演習問題

6.[HM20]

ベン図で考えれば以下の式が導き出せる。

$\sum_{S(j)}a_j+\sum_{R(j)andS(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{R(j)}a_j$

$\sum_{R(j)}a_j+\sum_{R(j)andS(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{S(j)}a_j$

$\sum_{R(j)}a_j+\sum_{S(j)}a_j-\sum_{R(j)andS(j)}a_j=\sum_{R(j)orS(j)}a_j$

$\sum_{R(j)}a_j+\sum_{S(j)}a_j-\sum_{R(j)orS(j)}a_j=\sum_{R(j)andS(j)}a_j$

上の4つの式は左辺、つまり3つの総和が分かれば右辺の1つの総和がわかることを表している。

2016-03-13

the art of computer programming 1.2.2　を読む

taocp the_art_of_computer_programming

対数を使う場合コンピュータの分野では2進対数が用いられるが、

その最大の理由は、コンピュータアルゴリズムが2方向の分岐を多用するから。

if-elseに代表されるように大なり小なりの判定や、ある文字列sとtが同じ文字列かどうかの判定などはyesかnoの2方向の分岐だから。

$log_{10}x$ の答えを2進表現で表現する方法の例

ここでは $x=27$ とする。

① $1 \le \frac{27}{10^1} \lt 10$

$x_0 = 2.7$ $b_0=1$ $b_0$ は上記式の $\frac{x}{10^n}$ の $n$

② $2.7^2 \lt 10$ なので

$x_1=2.7^2=7.29$ $b_1=0$

③ $7.29^2 \ge 10$ なので

$x_2=5.314$ $b_2=1$

④ $5.314^2 \ge 10$ なので

$x_3=2.8238$ $b_3=1$

これを⑧まで続けた結果、 ${b_0,b_1,...,b_7} = {1,0,1,1,0,1,1,1}$ となった。

これを10進数に変換すると $1.4296875$ となり、

$log_{10}27 = 1.43136$ なので、 $0.0016...$ の誤差となった。

回数を増やしたり、6桁で丸めるなどの工夫を行えばより正確な値をだせる。

演習問題

解いたもので回答がなかったものを書く。

5.[05]

$n=a_k*2^k+...a_2*2^2+a_1*2^1+a_0*2^0, m=b_k+2^k+...b_2*2^2+b_1*2^1+b_0*2^0$ とする。

ただし、 $a_i, b_i$ は0か1である。

2進数での有理数は $\frac{n}{m}$ である。

整数は $\frac{n}{2^0}$ で表現でき、小数は $\frac{2^0}{m}$ で表現できる。

ただし、 $\frac{n}{m}$ で表現できない値(0.1など)は2進数で表現できない。

また、数字の列の末尾が無限に続く1にならないもの。

(2)に変わる表現は

$n+\frac{d_1}{2}+\frac{d_2}{4}+...+\frac{d_k}{2^k} \le x \lt n+\frac{d_1}{2}+\frac{d_2}{4}+...+\frac{d_k}{2^k}+\frac{1}{2^k}$

2016-03-09

the art of computer programming 1.2.1 を読む

taocp the_art_of_computer_programming

1.2.1 数学的帰納法

数学的帰納法は以下の方法で証明を行う。

P(n)を整数nについての何らかの言明だとする。

(a) P(1) が真であることを証明する。

(b) [P(1), P(2), ... , P(n)が全て真なら、P(n + 1)も真である。]ことを証明する。

ただし、nを適当な数にしないと、nの分解の例(3は1+1+1=1+2=3というふうに分解できる。よってp(3)=3)のようにp(6)まで試してp(n)は素数になるという仮説をたてるとp(7)=15で泣くことになるので、注意が必要。

アルゴリズムI（証明の構築）

I1.[P(1) を証明する] k ← 1を行い、 $P(k)$ の証明を出力する。

I2.[k = n?] k = n なら、アルゴリズムを終了する。必要な証明は出力されている。

I3.[P(k + 1)を証明する] $P(1), ... , P(k)$ のすべてが真なら、 $P(k + 1)$ は真であることの証明を出力する。また、 $P(1), ... , P(k)$ をすでに証明したので、 $P(k + 1)$ は真であると出力する

I4.[k に 1 を加える]k に 1 を加え、ステップI2に進む。

このアルゴリズムは上記の(a)(b)をアルゴリズム的に表したものである。

この数学的帰納法は視点を少しずらすと任意のアルゴリズムの正しさを証明できる方法を構想できる。

クヌース先生によると、ある問題に対してあるアルゴリズムが正しい理由を本当に理解するためには頭の中がすべての表明で一杯になるところまで到達しなければならないらしく、その表明を頭のなかで組み立てる上で役に立つのがアルゴリズムのサンプル実行である。

演習問題

1.[05]

(a) P(0) が真であることを証明する

(b) P(0), P(1), ..., P(n) についてすべて真なら、P(n + 1)も芯になることを証明する。

2.[15]

$n = 2$ のときの証明がされていない。

実際に $n = 2$ のときはの $a^{n-1}$ は $a$ であり、 $n = 3$ のときは $a^2$ となる。 $a = 1$ のときのみこの定理は正しい。

3.[18]

n = 1のときに左辺が成り立たない。 $\frac{1}{0 \times 1}$ だが、初項が $\frac{1}{1 \times 2}$ なので、左辺は0になる。

4.[20]

n = 1 のとき、 $\phi^-1$ = 0.61803398なのでステップ(a)は証明される。

n = 2 のとき、 $\phi^0$ = 1なのでf(2)も証明される。

よって、次の式が得られる

$F_{n+1} = F_{n-1}+F{n} \le \phi^{(n-1)-2)}+\phi^{n-2}=\phi^{n-3}(1+\phi)=$

$\phi^{n-1}=\phi^{((n+1)-2)}$

ステップ(b)が終了したので、この式は数学的帰納法によって証明された。

5.[21]

n > 1で、nが素数の場合はそれ自身の積である。

nが素数でない場合はn = mk と分解でき、mが素数でなければm = abと分解でき、...とすると、n を素数の積に分解できる。

6.[20]

A5の $am + bn = d$ はE4でc ← d, a' ← a, b' ← b となっているのでA6の $a'm + b'n = c$ が成り立つ。

A6の $am + bn = c$ は $(a'-qa)m+(b'-qb)n=(a'm+b'n)-(qam+bqn)$

$=qd+r-q(am+bn)=qd+r-qd=r=a'm+b'n$ となりA5の $a'm+b'n$ が成り立つ。

7.[23]

$1^2=1$

$2^2-1^2=3$

$3^2-2^2+1^2=6$

$4^2-3^2+2^2-1^2=10$

$5^2-4^2+3^2-2^2+1^2=15$

$6^2-5^2+4^2-3^2+2^2-1^1=21$

となる。これは1からnまでの総和に等しい。よって、 $f(n)=\frac{n(n+1)}{2}$ であると仮定する。

$f(1) = 1$ であり、成り立つ。 $f(2) = 3$ で成り立つ。f(n)が成り立つと仮定すると、

$f(n + 1) = (n+1)^2-\frac{n(n+1)}{2}$

これが

$\frac{(n+1)(n+2)}{2}$

となれば、題意は $f(n)=\frac{n(n+1)}{2}$ で計算できることが証明できる。

左辺は、

$(n^2+2n+1)-\frac{n(n+1)}{2}$

通分して、

$\frac{2n^2+4n+2-n^2-n}{2}$

$=\frac{n^2+3n+2}{2}$

$=\frac{(n+2)(n+1)}{2}$

となり、左辺と右辺が一致するので、 $f(n + 1) = (n+1)^2-\frac{n(n+1)}{2}$ が成り立ち、証明ができた。

8.[25]

Nicomachusの定理が

$f(n) = (n^2-n+1)+(n^2-n+3)+...+(n^2-n+2n-1)$

で成り立つことを証明する。

$f(1) = 1^2-1+2-1=1$ で成り立つ。

これが、 $f(n)$ で成り立つとすると、 $f(n)$ の各項に2nをたせばよいので、

$f(n + 1) = 2n^2+f(n)+(n^2-n+2n+1)+2n$

となり、この式が $(n+1)^3$ となれば、証明できたこととなる。

右辺について整理する。

$2^n+n^3+n^2-n+2n+1+2n$

$=n^3+3n^2+3n+1$

$=(n+1)^3$

$f(n+1)=(n+1)^3$ となったので、証明終了。

(b)

$f(n) = 1+3+5+...+(n^2-n+1)+...+(n^2-n+2n-1)$

$=\frac{\frac{n(n+1)}{2}(1+n^2+n-1)}{2}$

$=\frac{(n^2+n)^2}{4}$

$=(\frac{n(n+1)}{2})^2$

この式は、1からnまでの総和の2乗なので、

$1^3+2^3+...+n^3=(1+2+...+n)^2$ が証明された。

9.[20]

この問題は別の方に託す。

2016-03-05

the art of computer programming 1.1 を読む

taocp the_art_of_computer_programming

1.1アルゴリズム

　アルゴリズムは単に特定のタイプの問題を解決するための一連の作業手順を定める有限個の規則という以上に、5種類の重要な特徴をもっている。

(1)有限性

　アルゴリズムは有限回のステップを実行したあと、必ず終了しなければならない。

　以下の4つの特徴を持つが有限性がない、つまり無限回のステップは計算方法とよばれる。

(2)明確性

　アルゴリズムの各ステップは正確に定義されていなければならない。

　人によって異なる解釈ができるものであってはならない。

(3)入力

　アルゴリズムは0個以上の入力を持つ。

(4)出力

　アルゴリズムは1個以上の出力を持つ。

　出力がないアルゴリズムはない。(何らかの処理をしたのにもかかわらず結果を教えてくれないというのは意味が無い）

(5)実効性

　アルゴリズムは一般に実効性を持つことも期待される。

　つまり、有限の時間のうちに処理が終了するということ。

　アルゴリズムは何でもかんでも実用的かと言われるとそうでもない。結果を得るまでに何年も、何十年もかかっていたのでは意味がないので、実用的なアルゴリズムは非常に限られた数のステップで終了しなければならない。

文字列のやつはWikipediaを見るとわかりやすい

演習問題 (問題難易度はthird editionのもの)

1.[10]

t ← a

a ← b

b ← c

c ← d

d ← t

2.[15]

m = qn + r

であり、rはnより小さいのでn > r。

　ステップE3でm ← n, n ← rを行うので m > n となり、ステップE1では必ず m > n となる。

3.[20]

　F1.[剰余を見つける]mをnで割り、余りをmとする。

　F2.[0か?]m=0ならアルゴリズム終了。nが答えである。

　F3.[剰余を見つける]nをmで割り、余りをnとする。

　F4.[0か?]n=0ならアルゴリズム終了。mが答えである。そうでなければF1へ戻る。

4.[16]

m ← 2166, n ← 6099

m = 0 × 6099 + 2166

m ← 6099, n ← 2166

m = 2 × 2166 + 1767

m ← 2166, n ← 1767

m = 1 × 1767 + 399

m ← 1767, n ← 399

m = 4 × 399 + 171

m ← 399, n ← 171

m = 2 × 171 + 57

m ← 171, n ← 57

m = 3 × 57 + 0

2166と6099の最大公約数は57

5.[12]

18.にて「ステップ3に戻ること」と書いてあり、終了しないため有限性がない。

15.にて「眠る」とあるが、何時間寝るのか書かれておらず曖昧であるため明確性がない

どれが入力かは分からないが、入力は0個でも良いので入力はある。

流れ図を見るかぎり、出力がなさそう。

今までに行く人ものチャレンジャーを闇に葬っている本だと思うので実効性はないと思う。

よって、有限性、明確性、実効性がない。

(出力については解答例でも有耶無耶な感じなので・・・）

アルゴリズムEとの違いは、識別用の文字(Eなど)がない、などなど

6.[20]

n = 5 なので r は0,1,2,3,4のどれかになる。よってこの5通りを試せば良い。

m = qn + 1 (r = 1) の場合は2回、 m = qn + 2 (r = 2) の場合は3回、m = qn + 3 (r = 3) の場合は4回

m = qn + 4 (r = 4)の場合は3回、 m = qn (r = 0) の場合は1回E1が実行される。

よってT₅は(2 + 3 + 4 + 3 + 1) / 5 = 2.6回となる。

　ただしqは正整数。

7.[M21]

T_nはnを固定しmは自由に選べる。 U_mはmを固定しnは自由に選べる。

m = 5 とするとT_m = 2.6 である。U_mは計算すると3.6となる。各計算について1回づつE1の実行回数が増えているのでU_m = T _m + 1 である。

8.[M25]

j θ Φ b a

1 ab c 1 2 (文字列中にabがある限りcに変換する)

2 a b 2 3 (文字列中のaをすべてbに変換する)

3 c a 3 4 (文字列中のcをすべてaに変換する)

4 b b 1 end (文字列中のbをbに変換し1へ。bがなければ終了)

感想

入力が0個のアルゴリズムがわからないので、そこは研究課題。