C++でABC204のA~D問題を解説します。
本番では、A、B問題しかできませんでした。C問題は本番終了後に解くことが出来ました。D問題は何となく動的計画法を使うんだろうなとは思いましたが、どのように適用するのかがわからず撃沈。
では解説をしていきます。
A – Rock-paper-scissors
問題文はこちら。
解説
\( x=y\,\)の時は\( z\,\)も\(x\,\)と同じなので、\(x\,\)を出力する。\(\,x\neq y\,\)の時はすべての手が異なり、その合計値が\(3\)なので\(\,(3-x-y)\,\)を計算することで\(z\,\)の手を計算し、出力すればいいです。
ソースコード
#include <bits/stdc++.h>
int main() {
int x, y; std::cin >> x >> y;
int z;
if (x == y)
z = x;
else
z = (3 - x - y);
std::cout << z << std::endl;
return 0;
}B – Nuts
問題文はこちら。
解説
順番に木の実の数\(A_i\,\)を受け取り、\(A_i\,\)が10より大きい場合には適当な変数に\((A_i-10)\,\)を足しこみ答えを計算する。
ソースコード
#include <bits/stdc++.h>
int main() {
int n; std::cin >> n;
int ans = 0;
for (int i = 0; i < n; ++i) {
int a; std::cin >> a;
if (a > 10) ans += a-10;
}
std::cout << ans << std::endl;
return 0;
}C – Tour
問題文はこちら。
解説
入力をグラフとして受け取り、ある頂点\(A_i\)から到達できる頂点の数をdfsもしくはbfsで計算します。これをすべての頂点について行うことで問題の答えを得られます。
\(N\)を頂点数、\(M\)をエッジ数とするとdfsの計算量は\(O(N+M)\)でそれを\(N\)回繰り返すので最終的な計算量は\(O(N(N+M))\,\)になります。\(N,M \leq 2000\)なので\(10^6\)回となり制限時間内に計算できます。
\(A_i\,\)から\(B_i\,\)のみ通行ができるので、有効グラフで表現します。
dfsとbfsの両方のコードを載せておきます。
ソースコード
#include <bits/stdc++.h>
void dfs(
const int& v,
const std::vector<std::vector<int>>& graph,
std::vector<bool>& is_visited,
int& n_path)
{
is_visited[v] = true;
++n_path;
for (const int& v_adj : graph[v]) { // vから行ける頂点を探索
if (is_visited[v_adj]) continue; // 訪問済みなのでskip
dfs(v_adj, graph, is_visited, n_path);
}
}
int main() {
int n, m; std::cin >> n >> m;
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
int a, b; std::cin >> a >> b;
--a, --b; // 0-indexedにする
graph[a].push_back(b); // 辺 a->b
}
int n_path = 0; // v_startから到達できる都市の数
for (int v_start = 0; v_start < n; ++v_start) {
std::vector<bool> is_visited(n, false);
dfs(v_start, graph, is_visited, n_path);
}
std::cout << n_path << std::endl;
return 0;
}#include <bits/stdc++.h>
void bfs(
const int& v_start,
const std::vector<std::vector<int>>& graph,
int& n_path)
{
int n_ver = graph.size();
std::vector<bool> is_seen(n_ver, false); // 発見済みかどうか
std::queue<int> q; // 訪問予定頂点
q.push(v_start);
is_seen[v_start] = true;
// キューが空になるまで
while (!q.empty()) {
int v = q.front(); // キューの先頭から頂点を取り出し
q.pop();
++n_path;
// vに隣接する頂点で未発見の頂点を
for (int const v_adj : graph[v]) {
if (is_seen[v_adj]) continue; // 発見済みはskip
q.push(v_adj); // qに加える
is_seen[v_adj] = true;
}
}
}
int main() {
int n, m; std::cin >> n >> m;
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
int a, b; std::cin >> a >> b;
--a, --b; // 0-indexedにする
graph[a].push_back(b); // a->b
}
int n_path = 0;
for (int v_start = 0; v_start < n; ++v_start)
bfs(v_start, graph, n_path);
std::cout << n_path << std::endl;
return 0;
}D – Cooking
問題はこちら。
解説
料理を1つ目のオーブンで調理するか、2つ目のオーブンで調理するかをbit探索で計算すると\(2^{100}\)となり絶対に間に合わない。
料理をする順番は関係なく、オーブン1とオーブン2の調理時間で長いほうが答えになります。オーブン1の調理時間を\(C_1\)、オーブン2の調理時間\(C_2\)は、すべての料理の調理時間から\(C_1\)を引けばいいので、\(C_2=\sum_i T_i – C_1\)と書けます。すると答えは次のように書けます。\[max(C_1, \sum_i T_i – C_1)\]
N個中からいくつか選び、オーブン1で調理する時間\(C_1\)としてありうるものをすべて計算して上の式を計算し、最も小さくなる時間が答えです。次のように書けます。\[\underset{C_1}{min}(max(C_1, \sum_i T_i – C_1))\]
調理時間としてあり得るものを計算するときには部分和問題として動的計画法で解くことで、計算量は\(O(N\sum_i T_i)\)となり実行時間制限内に計算できます。
私はdp[i][j]を[0,i]番目までの料理で調理時間をjに出来るかどうか、としてbottomupで実装しました。
ソースコード
#include <bits/stdc++.h>
int main() {
int n; std::cin >> n;
int* t = new int[n];
for (int i = 0; i < n; ++i) std::cin >> t[i];
// dpテーブルの確保
// dp[i][j] := [0,i]までの料理を組み合わせて調理時間をjにできるか否か
bool** dp = new bool*[n];
for (int i = 0; i < n; ++i)
dp[i] = new bool[100001];
// 0番目の料理で調理時間を0、t[0](0番目の料理の調理時間)にできる
dp[0][0] = true;
dp[0][t[0]] = true;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= 100000; ++j) {
dp[i][j] = dp[i-1][j]; // [0,i-1]でjにできるなら、[0,i]でもjにできる(iを選ばない)
if (t[i] <= j) // t[i]を選べる場合 [0,i-1]でj-t[i]にできるならt[i]を選んだ時にjにできる
dp[i][j] = dp[i-1][j-t[i]] | dp[i][j];
}
}
// 調理の最短時間を計算する
int sum = 0;
for (int i = 0; i < n; ++i) sum += t[i];
int ans = sum;
for (int j = 0; j <= 100000; ++j)
if (dp[n-1][j])
ans = std::min(std::max(j, sum-j), ans);
std::cout << ans << std::endl;
// メモリの解放
for (int i = 0; i < n; ++i)
delete[] dp[i];
delete[] dp;
delete[] t;
return 0;
}部分和問題のわかりやすい解説記事