yukicoder No.385 カップ麺生活

考え方

 この問題でとりあえず必要なのは素数のリストが必要なので作っておいたものを用意しておく。(逐一素数判定をしても良いが素数のリストを先に作っておいたほうが楽だと思ったので素数のリストが必要ということにする。)
 あとはi円で買えるカップ麺の個数さえ分かれば楽に計算することができるため動的計画法で求める。

コード

#include <iostream> 
#include <vector>
#include <algorithm>

bool is_prime(int n, std::vector<int> primes) {
	for (int i = 0; i < primes.size(); i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}

void prime_list(int n, std::vector<int> &primes) {
	if (n == 1) return;
	primes.push_back(2);

	for (int i = 3; i <= n; i += 2) {
		if (is_prime(i, primes)) {
			primes.push_back(i);
		}
	}
}


int main() {
	int m, n;

	// dp[i] = i円で購入できるカップ麺の最大個数
        int dp[10000 + 1] = { 0 };

	std::cin >> m >> n;

	std::vector<int> value(n);
	for (int i = 0; i < n; i++) {
		std::cin >> value[i];
                dp[value[i]] = 1;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			if (dp[j] > 0 && j + value[i] <= m) {
				dp[j + value[i]] = std::max(dp[j] + 1, dp[j + value[i]]);
			}
		}
	}

	std::vector<int> primes;
	prime_list(m, primes);

	long long ans = 0;

        // 支払い後がprime円になるためには(m - prime[i])円支払えば良い
	for (int i = 0; i < primes.size(); i++) {
		ans += dp[m - primes[i]];
	}

        // もう金欠チャンスが使えないので買えるだけ買う
	ans += *std::max_element(dp, dp+m+1);

	std::cout << ans << std::endl;

	return 0;
}

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