ABC198 C - Compass Walking

■考えたこと
制約的に何歩で(X,Y)に行けるかを愚直に
シミュレーションする方針で解けると推測。

ACしたコードは下記。

using ll = long long;

int main() {
	int r, x, y;
	cin >> r >> x >> y;
	ll l = (ll)x * x + (ll)y * y;
	ll r2 = (ll)r * r;
	ll ans = 1;
	
	while (r2 * ans * ans < l) ans++;
	if (ans == 1) {
		if (r2 * ans * ans > l) ans++;
	}
	cout << ans << endl;
}

ABC317 C - Remembering the Days

■考えたこと
制約的に全探索と思った。
再帰で実装した。

ACしたコードは下記。

struct Edge {
	int to; ll cost;
	Edge(int to, ll cost) : to(to), cost(cost){}
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<Edge>> g(n);
	for (int i = 0; i < m; i++) {
		int a, b; ll c;
		cin >> a >> b >> c;
		--a; --b;
		g[a].push_back(Edge(b, c));
		g[b].push_back(Edge(a, c));
	}

	vector<bool> visited(n);
	ll ans = 0;
	auto dfs = [&](auto dfs, int v, ll c) -> void {
		visited[v] = true;
		ans = max(ans, c);
		for (auto nv : g[v]) {
			if (visited[nv.to]) continue;
			dfs(dfs, nv.to, c + nv.cost);
		}
		visited[v] = false;
	};

	for (int i = 0; i < n; i++) {
		dfs(dfs, i, 0);
	}
	cout << ans << endl;
}

ABC243 C - Collision 2

■考えたこと
y座標が同じ座標ごとにまとめれば見通しが良くなる。
まとめ後はx座標とR/Lのペアでデータを持ち、昇順でソートしてRLのペアが
存在するか判定すればOK。

ACしたコードは下記。

int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	string s;
	cin >> s;
	map<int, vector<pair<int, char>>> mp;
	for (int i = 0; i < n; i++) {
		mp[y[i]].push_back(make_pair(x[i], s[i]));
	}
	for (auto e : mp) {
		auto ps = e.second;
		sort(ps.begin(), ps.end());
		for (int i = 0; i < ps.size() - 1; i++) {
			if (ps[i].second == 'R' && ps[i + 1].second == 'L') {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
}

ABC341 C - Takahashi Gets Lost

■考えたこと

全探索をすると計算量O(HWN) = O(125 x 10^6)であり間に合うか心配だったが
この方針で実装してACした。

ACしたコードは下記。

int main() {
	int h, w, n;
	cin >> h >> w >> n;
	string t;
	cin >> t;
	vector<string> s(h);
	for (int i = 0; i < h; i++) cin >> s[i];

	int ans = 0;
	for (int hi = 0; hi < h; hi++) {
		for (int wj = 0; wj < w; wj++) {
			if (s[hi][wj] != '.') continue;
			int i = hi, j = wj;
			bool ok = true;
			for (int v = 0; v < n; v++) {
				if (t[v] == 'L') j -= 1;
				if (t[v] == 'R') j += 1;
				if (t[v] == 'U') i -= 1;
				if (t[v] == 'D') i += 1;

				if (i < 0 || i > h || j < 0 || j > w) ok = false;
				if (s[i][j] != '.') ok = false;
				if (!ok) break;
			}
			if (ok) ans++;
		}
	}

	cout << ans << endl;
}

ABC245 C - Choose Elements

■考えたこと
dpのような気がしたので入力例1の値で以下の表を書いてみた。

9	1
8	6
3	2
7	9
2	5

i \ j	0	1
0	true	true
1	true	true
2	true	true
3	true	false
4	false	true

dpの定義は以下。
dp[i][j] = A[i][j]が条件を満たすかどうか。
dp[0][0] = dp[0][1] = true
dp[n - 1][0] または dp[n - 1][1] がtrueならYes。

以下はACしたコード。

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> a(n, vector<int>(2));
	for (int i = 0; i < n; i++) cin >> a[i][0];
	for (int i = 0; i < n; i++) cin >> a[i][1];

	vector<vector<bool>> dp(n, vector<bool>(2, false));
	dp[0][0] = dp[0][1] = true;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < 2; j++) {
			if (!dp[i][j]) continue;
			for (int l = 0; l < 2; l++) {
				if (abs(a[i + 1][l] - a[i][j]) <= k) {
					dp[i + 1][l] = true;
				}
			}
		}
	}
	
	for (int j = 0; j < 2; j++) {
		if (dp[n - 1][j]) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

ABC318 C - Blue Spring

■考えたこと

問題文を読んでも解法が思いつかなかった。

とりあえず入力例1で周遊パスを買っていったときの様子を紙に書いてみた。

1日周遊パスは2枚セットで10円で販売されているので各セット購入したとすると

・0セット：7 + 1 + 6 + 3 + 6 = 23円

・1セット：(10 x 1) + (0 + 1 + 0 + 3 + 6) = 20円 ← 料金が高い日順に周遊パスを割り当て

・2セット：(10 x 2) + (0 + 1 + 0 + 0 + 0) = 21円

・3セット：(10 x 3) + (0 + 0 + 0 + 0 + 0) = 30円

となる。

ここまで書き出すと3セット以降は料金が高くなっていくだけなので

試す必要がないことが分かった。

つまり5日間すべてを周遊パスで割り当てするためには3セットで十分。

これは N / D の切り上げ (以降k) で計算できる。 

制約的にkセット試せば間に合うと推測。

後はkセット購入した場合の合計料金をどう計算するかだが、下記を書いて

累積和でいけそうと推測。

f : 1   3   6     6    7

s : 0   1   4   10  16  23

以下はACしたコード。

using ll = long long;

int main() {
  int n, d, p;
  cin >> n >> d >> p;
  vector f(n);
  for (int i = 0; i < n; i++) cin >> f[i];
  sort(f.begin(), f.end());

  vector s(n + 1);
  for (int i = 0; i < n; i++) {
    s[i + 1] = s[i] + f[i];
  }

  int sd = (n + d - 1) / d;
  
  const ll INF = 1e18;
  ll ans = INF;
  for (ll i = 0; i <= sd; i++) {
    ll sum = 0;
    if (n - i * d > 0) sum += s[n - i * d];
    sum += p * i;
    ans = min(ans, sum);
  }
  cout << ans << endl;
}

ABC325 C - Sensors

■考えたこと

蟻本のLake Counting (POJ No.2386) と同じ問題。

とりあえずdfsで連結しているセンサーをなめていき

(訪れたセンサーはtrueにしておく) 再帰終了後、カウントを足すという方針で解いた。

ACしたコードは下記。

const int di[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dj[] = { 0, 1, 0, -1, 1, -1, 1, -1 };

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	for (int i = 0; i < h; i++) cin >> s[i];

	vector<vector<bool>> visited(h, vector<bool>(w));
	auto dfs = [&](auto dfs, int i, int j) -> void {
		visited[i][j] = true;
		for (int v = 0; v < 8; v++) {
			int ni = i + di[v];
			int nj = j + dj[v];
			if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
			if (visited[ni][nj]) continue;
			if (s[ni][nj] != '#') continue;
			dfs(dfs, ni, nj);
		}
	};

	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] != '#') continue;
			if (visited[i][j]) continue;
			dfs(dfs, i, j);
			ans++;
		}
	}

	cout << ans << endl;
}