読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest 039:C ピアニスト高橋君

問題内容

abc039.contest.atcoder.jp

高橋君が白鍵の上に立っている。そこから右に20個分の鍵盤の色が与えられるので高橋君がどこにいるのか当てる問題。

解法

全探索で解ける。
(高橋君がドの上にいたと仮定して、入力とマッチしているか確かめる。
違っていたらレの上に立っていると仮定して・・・をシまで確かめる。)

右20個の情報が与えられるのでド~シまでの鍵盤(WBWBWWBWBWBW)をたくさんとっておくことに注意

C++のコード

#include<iostream>
#include<string>
 
int main() {
	std::string s;
	std::string pos[] = { "Do", "Re","Mi","Fa","So","La","Si" };
 
	std::cin >> s;
 
	
	std::string kenban = "WBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBWWBWBWWBWBWBW";
 
	int white = 0;
 
	for (int i = 0; i < kenban.length(); i++) {
		if (kenban.substr(i, 20) == s) break;
		if (kenban[i] == 'W') white++;
	}
 
	std::cout << pos[white] << std::endl;
 
	return 0;
}

AtCoder Beginner Contest 039:D 画像処理高橋君

問題

abc039.contest.atcoder.jp

2値画像を一回収縮した2値画像が与えられるので元の画像としてありえるものを出力する。

解法

黒画像(#)がどこにあるのかを探すのは面倒な感じなので白画像(.)のところを求めていくと楽にできる。

C++のコード

6重ネストがあるのでもうしわけない

#include<iostream>
#include<string>
#include<vector>
 
bool inside(int x, int y, int h, int w) {
	if (0 <= x && x < h && 0 <= y && y < w) return true;
	return false;
}
 
int main() {
	int h, w;
 
	std::cin >> h >> w;
 
	std::vector<std::string> s(h);
	for (int i = 0; i < h; i++) {
		std::cin >> s[i];
	}
 
	// 元の画像
        // 真っ黒な画像から確実に白なところを白にしてく方式
	std::vector<std::string> ans(h);
    
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			ans[i].push_back('#');
		}
	}
 
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == '.') {
                                // 収縮した画像で白のところの周りは確実に白
				for (int k = -1; k < 2; k++) {
					for (int l = -1; l < 2; l++) {
						if (inside(i + k, j + l, h, w)) {
							ans[i + k][j + l] = '.';
						}
					}
				}
			}
		}
	}


	std::vector<std::string> temp = ans;
        // 暫定元画像を収縮してみる
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (temp[i][j] == '#') {
				for (int k = -1; k < 2; k++) {
					for (int l = -1; l < 2; l++) {
						if (inside(i + k, j + l, h, w)) {
							ans[i + k][j + l] = '#';
						}
					}
				}
			}
		}
	}
 
 
        // 暫定元画像を収縮した結果が同じならpossible!!!!!!!!!!
	if (s == ans) {
		std::cout << "possible" << std::endl;
		for (int i = 0; i < h; i++) {
			std::cout << temp[i] << std::endl;
		}
	} else {
		std::cout << "impossible" << std::endl;
	}
	return 0;
}

AtCoder Regular Contest 019:こだわりの名前

問題

文字列 s が与えられる。
s を一文字だけ変更した文字列 t を作る。しかし t が回文にならないようにしなければならない。
そのような変更の仕方は何通りあるか求める。

解法

length(s) == 1 ならばどのように文字を変更しても回文になってしまうので、そのような変更の仕方は0通りとなる。

s が既に回文ならば1文字変更すると回文でなくなるのでそのような変更の仕方は 25 \times length(s) となる。
しかし、length(s) が奇数で回文の時には、真ん中の文字を他の文字に変更しても回文になってしまうので注意が必要。f:id:Matchald:20160608115224p:plain

あとは、s が回文でない状態を考えれば良い。
s を1文字変更して回文になってしまうのは1つのペアのみが違う文字の時である。2ペア以上違う文字ならばどのように文字を1文字変更しても回文にはならない。
f:id:Matchald:20160608122328p:plain

C++のコード

#include<iostream>
#include<string>
#include<algorithm>

// 文字列 s が回文かどうかの判定
bool isPalindrome(std::string s) {
	std::string rev = s;
	std::reverse(rev.begin(), rev.end());

	return rev == s;
}

// 何ペア違うところがあるか
int changeCharNo(std::string s) {
	int start = 0, end = s.length() - 1, count = 0;
	while (start <= end) {
		if (s[start] != s[end]) count++;
		start++;
		end--;
	}
	return count;
}


int main() {
	std::string s;

	std::cin >> s;

	if (s.length() == 1) {
		std::cout << 0 << std::endl;
		return 0;
	}

	if (isPalindrome(s)) {
		long long ans = 25 * s.length();
		if (s.length() % 2 == 1) ans -= 25;
		std::cout << ans << std::endl;
		return 0;
	}

	long long ans;
	if (changeCharNo(s) == 1) {
		ans = 24 * 2 + (s.length() - 2) * 25;
	} else {
		ans = 25 * s.length();
	}

	std::cout << ans << std::endl;
	return 0;
}

ディビジョン・ナイン

問題概要

1 から 4 の数字を使って n 桁の整数を作ります。このとき、9 の倍数となるものを考えましょう。
例えば n = 3 であれば、234、333、441、などが 9 の倍数です。必ずしも 1 から 4 の全ての数字を使う必要はありません。



1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。
例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 20)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

解法

n 桁で表すことができる値 i を書き出していけば以下のようにパスカルの三角形みたいになる。
f:id:Matchald:20160319174858p:plain

n 桁で値 m を表す個数は、(1桁目を1として(n-1)桁で(m-1)を表す個数)+(1桁目を2として(n-1)桁で(m-2)を表す個数)+・・・(1桁目を4として(n-1)桁で(m-4)を表す個数)であるので、
value[桁][値] = value[桁 - 1][値 - 1] + value[桁 - 1][値 - 2] + value[桁 - 1][値 - 3] + value[桁 - 1][値 - 4]
である。

Python3によるコード

n = int(input())
l = [[0 for i in range(4*n + 1)] for j in range(n + 1)]

# l[桁数][値]
l[1][1] = l[1][2] = l[1][3] = l[1][4] = 1

count = 0
for i in range(2, 4*n+1):
    for j in range(2, n + 1):
        l[j][i] = sum(l[j - 1][i - 4 if i - 4 >= 0 else 0:i])
        if i % 9 == 0 and j == n:
            count += l[j][i]

print(count)


このコードはnが大きくなるとメモリ効率が悪い。

私のコードでは、ある値 i から i -4 までの5つの値を n 桁ぶん覚えていればよいので、最低限必要な配列は n \times 5 でよい。

the art of computer programming 1.2.5 を読む

置換と階乗

非負整数に関してn の階乗は以下のように定義される。
n! = 1 \times 2 \times ... \times n = \prod_{k=1}^nk

しかし、n が整数でない時にはn! という記法は余り使われない。
その代わり、以下の記法を用いる。
n! = \Gamma(n + 1) = n\Gamma(n)

この関数はガンマ関数と呼ばれ、次のように定義される。
\Gamma(x)=\frac{x!}{x}=\lim_{m \to \infty}\frac{m^xm!}{x(x+1)(x+2)...(x+m)}

Chokudai Contest 001

問題概要

30 \times 30 のマスがあり、あるマスには1以上100以下の整数が書かれている。
すべてのマスを0にするまで以下の動作を続ける。
①あるマスの値を1減らす
②そのマスの上下左右いずれかのマスが今いるマスの値と同じ時、そのマスに移動し①を実行する。そのようなマスがなければその手は終了。

このときに、手数がなるべく少なくなるような選び方をする。

1回目のコード

すべてのマスの中で一番大きい数のマスを選び①を実行していく戦法。
これで、758559点。

#include<iostream>
#include<vector>
#include<algorithm>
 
void re(std::vector<int> &table, int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1<< std::endl;
	table[pos]--;
	if (pos - 30 >= 0 && table[pos - 30] != 0 && table[pos - 30] == table[pos]) re(table, pos - 30);
	if (pos + 30 < 900 && table[pos + 30] != 0 && table[pos + 30] == table[pos]) re(table, pos + 30);
	if (pos % 30 > 0 && table[pos - 1] != 0 && table[pos - 1] == table[pos]) re(table, pos - 1);
	if (pos % 30 < 29 && table[pos + 1] != 0 && table[pos + 1] == table[pos]) re(table, pos + 1);
}
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				re(table, i);
			}
		}
	}
}

2回目のコード

1回目のコードの関数内でelse ifにするべきところをifにしていたので修正。
この修正で、809699点。

#include<iostream>
#include<vector>
#include<algorithm>
 
void output(int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1 << std::endl;
}
 
void re(std::vector<int> &table, int pos) {
	output(pos);
	table[pos]--;
	if (pos - 30 >= 0 && table[pos - 30] != 0 && table[pos - 30] == table[pos]) re(table, pos - 30);
	else if (pos + 30 < 900 && table[pos + 30] != 0 && table[pos + 30] == table[pos]) re(table, pos + 30);
	else if (pos % 30 > 0 && table[pos - 1] != 0 && table[pos - 1] == table[pos]) re(table, pos - 1);
	else if (pos % 30 < 29 && table[pos + 1] != 0 && table[pos + 1] == table[pos]) re(table, pos + 1);
}
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				re(table, i);
			}
		}
	}
}

最終的なコード

1回目の戦法に加えて、1手のうちでたくさんのマスの値を減らすことができる方法を探索して、それを実行するコードに変更
これで、815109点。

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
 
void output(int pos) {
	std::cout << pos / 30 + 1 << " " << pos % 30 + 1 << std::endl;
}
 
int max_nest = 0;
std::vector<int> order;
void re(std::vector<int> table, int pos, int nest, std::vector<int> o) {
	o.push_back(pos);
	if (max_nest < nest) {
		max_nest = nest;
		order = o;
	}
	if (table[pos] == 1) return;
	table[pos]--;
 
	if (pos - 30 >= 0 && table[pos - 30] == table[pos]) {
		re(table, pos - 30, nest + 1, o);
	} 
	if (pos + 30 < 900 && table[pos + 30] == table[pos]) {
		re(table, pos + 30, nest + 1, o);
	}
	if (pos % 30 > 0 && table[pos - 1] == table[pos]) {
		re(table, pos - 1, nest + 1, o);
	}
	if (pos % 30 < 29 && table[pos + 1] == table[pos]) {
		re(table, pos + 1, nest + 1, o);
	}
}
 
 
int main() {
	std::vector<int> table(900);
 
	for (int i = 0; i < 900; i++) {
		std::cin >> table[i];
	}
 
	while (std::count(table.begin(), table.end(), 0) != 900) {
		const int max = *std::max_element(table.cbegin(), table.cend());
		for (int i = 0; i < table.size(); i++) {
			if (table[i] == max) {
				std::vector<int> o;
				re(table, i, 1, o);
				for (int j : order) {
					output(j);
					table[j]--;
				}
				max_nest = 0;
			}
		}
	}
}

結果と感想

6時半ごろに参戦して最終結果は815109点で97位でした。

30行程度でも750000点位だせたので、モチベ高く取り組むことができた。
コードを修正して良くなった、悪くなったがすぐにわかるので点数が上がった時の喜びで
もっと良いコードにするぞ感がまして初心者にはとっつきやすかったのではないかと思う。

the art of computer programming 1.2.4 を読む

1.2.4 整数関数と初等整数論

modについて

 (a) y \gt 0 なら 0 \le x \bmod y \lt y

    (b) y \lt 0 なら 0 \ge x \bmod y \gt y

    (c) x-(x \bmod y)y の整数倍

 となる。例えば、

 5 \bmod 3 = 2

    18 \bmod 3 = 0

    -2 \bmod 3 = 1

   となる。最後の式は

   5 \bmod 3 = 2

   4 \bmod 3 = 1

   3 \bmod 3 = 0

   2 \bmod 3 = 2

   1 \bmod 3 = 1

   0 \bmod 3 = 0

 を考えると、あまりは2,1,0,2,1,0となっているので-1を3で割った余りはその順序に従って2となる。なので、-2を3で割った余りは1となる。

 

modの法則

 法則A.\pmod ma \equiv b かつ x \equiv y なら a \pm x \equiv b \pm y かつ ax \equiv byである。

    法則B.\pmod max \equiv by かつ a \equiv b で、なおかつ a \perp m なら x \equiv y である。

    法則C.n \neq 0 とするとき、a \equiv b \pmod m必要十分条件an \equiv bn \pmod {mn} である。

    法則D.r \perp s なら a \equiv b \pmod {rs} になる必要十分条件a \equiv b \pmod r かつ a \equiv b \pmod s である。

 

a \perp bab が互いに素であることを表す。

 

    フェルマーの小定理は法則AとBから導き出される。

フェルマーの小定理

 p素数なら、すべての整数 a に対して a^p \equiv a \pmod p になる。

 

 証明

  p素数なので、a \perp p である。そこで以下の数値について考える。

   0 \bmod p, a \bmod p, 2a \bmod p, ... , (p - 1)a \bmod p

  これら p 個の値は異なる値である。なので、非負で p より小さい数は、0,1,2,3,4,...,p-1と続く。そこで、法則Aより、次の式が成り立つ。

  (a)(2a) ... ((p-1)a) \equiv 1 \cdot 2 ... (p-1) \pmod p

  この合同式の両辺に a を掛けると次のようになる

  a^p(1 \cdot 2 ... (p-1) ) \equiv a(1 \cdot 2 ... (p-1) ) \pmod p

  これを法則Bに当てはめると、

  a^p(1 \cdot 2 ... (p-1) ) \equiv a(1 \cdot 2 ... (p-1) ) \pmod p かつ (1 \cdot 2 ... (p-1) ) \equiv (1 \cdot 2 ... (p-1) ) で、なおかつ (1 \cdot 2 ... (p-1) ) \perp p なので  a^p \equiv a である。

  これで定理は証明された。

 

    この定理を応用すると、

    a^{p-1} \equiv 1 \pmod p

    となり、さらに

    a^{p-2} \equiv a^{-1} \pmod p

    となる。この式は a で割ることは a^{p-2}p で割った余りと等しいということである。

    a で割ることをa^{p-2} \bmod p にすることの何が嬉しいのかというと、小数の精度を気にしなくても良くなることである。

    有理数でない限り(有理数であっても)少なからず誤差が発生する。しかし、掛け算の場合はオーバーフローの問題を考えなければ、メモリを食い尽くさないかぎりコンピュータで表現が可能である。

 この問題の例としてAtcoder Beginner Contestがある。この問題では

    a^{p-2} \equiv a^{-1} \pmod p

 を使用して問題を解く。

 

演習問題

16.[M10]

 \frac{x-z}{y}=0 ということは x-zy の倍数であり、(x-z) \bmod y =0 である。

 式を変形すると、

 x \bmod y - z \bmod y = 0

 x \bmod y = z \bmod y

 z \bmod y は、z0 \le z \lt y なので、\bmod をとってもとらなくても結果は変わらない。よって、

 x \bmod y = zとなる。