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

年中春休み

年中春休みじゃないです。

競技プログラミング 8(過去問 ABC 039)

abc039.contest.atcoder.jp


蟻本を図書館で借りて読んでみたのですが、初級編から深さ優先探索幅優先探索が出てきて焦りました…。
深さ優先探索幅優先探索の練習問題でも解かないと一生実装できなさそう。(コードを熟読してやっと何やってるか理解できるレベルなので)


そういえば横幅が狭いデザインが気に入らなかったのでブログデザイン変えてみました。
不評だったら戻します。


A問題
そのまま解きました。

#include<iostream>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
 
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << 2 * (a*b + b*c + c*a) << endl;
	return 0;
}


B問題
sqrtを使ったらコンパイルエラーを吐いたので悩んでいたら、math.hをincludeしたら解決しました。
VisualStudio上ではincludeしなくても動いたので油断(?)していました。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
 
int main() {
	ll n, x;
	cin >> x;
	n = sqrt(sqrt(x));
	cout << n << endl;
	return 0;
}


C問題
解法自体はすぐに思いついたのですが、aの初期値を設定していなかったせいで"Re"が答えになる場合にaが空となってしまい、if文でエラーを吐くということに気づかないで3回WA吐きました。
あと1回は"La"を"Ra"としていたせいでWA。問題文はよく読みましょう。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
 
int main() {
	string s, ans = "Re";
	int a = 100;
	cin >> s;
	for (int i = 0; i < 9; i++) {
		if (s.substr(i, 12) == "WBWBWWBWBWBW") {
			a = i;
			break;
		}
	}
	if (a == 0) ans = "Do";
	if (a == 1) ans = "Si";
	if (a == 3) ans = "La";
	if (a == 5) ans = "So";
	if (a == 7) ans = "Fa";
	if (a == 8) ans = "Mi";
 
	cout << ans << endl;
	return 0;
}


D問題
これも解法自体は思いついたのですが、条件文の使い方が下手なのでめちゃくちゃ読みづらくなってしまったし実装も遅くなってしまいました。
もっとしっかり考えて適切に場合分けしないとダメですね…。
半分はほとんどコピペコードだしこれなら関数にした方が良かった?のかなと思います。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
 
int main() {
	int h, w;
	string s[100], t[100], u[100];
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		cin >> s[i];
		t[i] =s[i];
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == '.') {
				if (j - 1 >= 0) {
					t[i][j - 1] = '.';
					if (i - 1 >= 0) t[i - 1][j] = t[i - 1][j - 1] = '.';
					if (i + 1 < h) t[i + 1][j] = t[i + 1][j - 1] = '.';
					if (j + 1 < w) {
						t[i][j + 1] = '.';
						if (i - 1 >= 0) t[i - 1][j + 1] = '.';
						if (i + 1 < h) t[i + 1][j + 1] = '.';
					} 
				} else {
					if (i - 1 >= 0) t[i - 1][j] = '.';
					if (i + 1 < h)t[i + 1][j] = '.';
					if (j + 1 < w) {
						t[i][j + 1] = '.';
						if (i - 1 >= 0) t[i - 1][j + 1] = '.';
						if (i + 1 < h) t[i + 1][j + 1] = '.';
					}
				}
				
			}
		}
		
	}
	for (int i = 0; i < h; i++) {
		u[i] = t[i];
	}
 
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (t[i][j] == '#') {
				if (j - 1 >= 0) {
					u[i][j - 1] = '#';
					if (i - 1 >= 0) u[i - 1][j] = u[i - 1][j - 1] = '#';
					if (i + 1 < h) u[i + 1][j] = u[i + 1][j - 1] = '#';
					if (j + 1 < w) {
						u[i][j + 1] = '#';
						if (i - 1 >= 0) u[i - 1][j + 1] = '#';
						if (i + 1 < h) u[i + 1][j + 1] = '#';
					}
				} else {
					if (i - 1 >= 0) u[i - 1][j] = '#';
					if (i + 1 < h)u[i + 1][j] = '#';
					if (j + 1 < w) {
						u[i][j + 1] = '#';
						if (i - 1 >= 0) u[i - 1][j + 1] = '#';
						if (i + 1 < h) u[i + 1][j + 1] = '#';
					}
				}
 
			}
		}
 
	}
 
	bool f = true;
	for (int i = 0; i < h; i++) {
		if (s[i] != u[i]) f = false;
	}
 
	if (f) { 
		cout << "possible" << endl;
		for (int i = 0; i < h; i++) {
			cout << t[i] << endl;
		}
	} else {
		cout << "impossible" << endl;
	}
	return 0;
}



結局深さ優先探索幅優先探索の練習問題を探すのも大変なので、ABCの過去問解きながら間違った問題を深く掘り下げていくのが一番良さそう…?
また詰まったら蟻本ちゃんと読んでみようと思います。図書館から借りたものではなくちゃんと買ったもので(どうせ貸出期間中に読み切れるものではないし)。