# # AtCoder Beginner Contest 176 Tutorial

## # Problem A - Takoyaki (opens new window)

The time needed equals to $\left\lceil\frac{N}{X}\right\rceil\cdot T$.

Code (Python3)
n, x, t = map(int, input().split(' '))
print(((n - 1) // x + 1) * t)

1
2

## # Problem B - Multiple of 9 (opens new window)

Let $n=\sum a_i\times10^i$, since $\forall i,10^i\equiv1(\mod9)$, we have $n\equiv\sum a_i(\mod 9)$ . So we just need to check the sum of all the digits of $n$.

Code (Python3)
print('Yes' if sum(map(int, input())) % 9 == 0 else 'No')

1

## # Problem C - Step (opens new window)

Just greedily increase current number to the maximum to its left, and then update the maximum if current number is larger than it.

Code (C++)
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
int hi = 0;
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += max(0, hi - a[i]);
hi = max(hi, a[i]);
}
cout << ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem D - Wizard in Maze (opens new window)

It's a very typical $0$-$1$ BFS, since the cost is $0$ if we go along the roads, while the cost is $1$ if we cast a magic spell.

Compared to ordinary BFS, we need to use a deque instead of a single-ended queue. For relaxations that cost $0$, we do push_front, while for those cost $1$, we do push_back. In this way, the elements in the deque are kept in an non-decreasing order, which means we will happily take the current value as the optimal value when we first reach the target position.

Code (C++)
#include <deque>
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int h, w, sx, sy, ex, ey;

int main() {
cin >> h >> w >> sx >> sy >> ex >> ey;
sx--, sy--, ex--, ey--;
vector<string> a(h);
for (int i = 0; i < h; ++i)
cin >> a[i];
vector<vector<int>> dist(h, vector<int>(w, INF));
vector<vector<bool>> vis(h, vector<bool>(w, false));
deque<pair<int, int>> q;
q.push_back({sx, sy});
dist[sx][sy] = 0;
while (!q.empty()) {
auto f = q.front();
q.pop_front();
int ci = f.first, cj = f.second;
if (ci == ex && cj == ey) {
cout << dist[ci][cj];
return 0;
}
if (vis[ci][cj])
continue;
vis[ci][cj] = true;
for (int k = 0; k < 4; ++k) {
int ni = ci + dy[k], nj = cj + dx[k];
if (ni < 0 || ni >= h || nj < 0 || nj >= w ||
dist[ni][nj] <= dist[ci][cj] || a[ni][nj] == '#')
continue;
dist[ni][nj] = dist[ci][cj];
q.push_front({ni, nj});
}
for (int ni = ci - 2; ni <= ci + 2; ++ni)
for (int nj = cj - 2; nj <= cj + 2; ++nj) {
if (ni < 0 || ni >= h || nj < 0 || nj >= w || a[ni][nj] == '#' ||
dist[ni][nj] <= dist[ci][cj] + 1)
continue;
dist[ni][nj] = dist[ci][cj] + 1;
q.push_back({ni, nj});
}
}
cout << -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

## # Problem E - Bomber (opens new window)

First, we can simply count how many targets there are in each row and each column.

Supposing the maximum of rows is $R_{max}$, and $C_{max}$ for columns. It is obvious that we can never achieve any value greater than $R_{max}+C_{max}$. In addition, we may not achieve $R_{max}+C_{max}$ because there might be a target at the crossing point of the row and the column, in which case this target is counted twice. So our worst case value is $R_{max}+C_{max}-1$ if we choose a row from those having $R_{max}$, and a column from those having $C_{max}$. Since all other choices cannot give better results, we only need to consider these rows and columns.

There might still be a log of combinations (worst case $O(NM)$). However, we do not need to check these combinations one by one. We can consider it from the perspective of targets. Say there are $n$ rows of $R_{max}$ and $m$ columns of $C_{max}$, if the number of target is smaller than $nm$, then it is ensured than there is at least one combination which will give us $R_{max}+C_{max}$. Otherwise, there are not so many combinations, so we can check them one by one, until we find a combination giving $R_{max}+C_{max}$, or we finish all the combinations and none is suitable, then we will have $R_{max}+C_{max}-1$ instead.

Code (C++)
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
int main() {
int h, w, m;
cin >> h >> w >> m;
vector<int> hc(h + 1), wc(w + 1);
vector<pair<int, int>> p(m);
for (int i = 0; i < m; ++i)
cin >> p[i].first >> p[i].second, hc[p[i].first]++, wc[p[i].second]++;
set<pair<int, int>> s(p.begin(), p.end());
int hm = *max_element(hc.begin(), hc.end());
int wm = *max_element(wc.begin(), wc.end());
vector<int> vh, vw;
for (int i = 1; i <= h; ++i)
if (hc[i] == hm)
vh.emplace_back(i);
for (int i = 1; i <= w; ++i)
if (wc[i] == wm)
vw.emplace_back(i);
int sh = vh.size(), sw = vw.size();
if (sh * sw > m) {
cout << hm + wm;
return 0;
}
for (int i : vh)
for (int j : vw)
if (!s.count({i, j})) {
cout << hm + wm;
return 0;
}
cout << hm + wm - 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

## # Problem F - Brave CHAIN (opens new window)

There is an obvious $O(N^3)$ DP idea, in which we maintain states $dp[i][j]$, meaning the maximum we can get when we choose to keep numbers (not indices) $i$ and $j$. But this is not enough to pass.

Do we always need to update all the states? For each segment of length $3$, only a few of all states can be updated, because we are only given at most $3$ different numbers, which means we do not have many choices.

So, how to do state transitions? Supposing we are considering $a,b,c$.

• If $a=b=c$, then we should choose them all. In this case, instead of updating states, we should keep the number of such triplets in a separate variable. So the transition is $O(1)$.
• We change the current reserved numbers to two of $a,b,c$, e.g., $(a,b)$. In this case, we have two further choices
• Make no triplets, and update $dp[a][b]$ to current global optimal value $opt$.
• Make a triplet using two reserved $c$ and current $c$, then update $dp[a][b]$ to $dp[c][c]+1$. The transition is $O(1)$.
• We change one of the reserved number to one of $a,b,c$, e.g., $a$. In this case, we need to enumerate the other reserved number $x$, and we have two further choices
• Make no triplets, and update $dp[a][x]$ to local optimal value $local\_opt[x]$, which means the best value we can get when we reserve at least one $x$.
• Particularly, if $b=c$, then we can update $dp[a][x]$ to $dp[b][x]+1$ The transition is $O(N)$

So the overall time complexity becomes $O(N^2)$, which is acceptable. It should be noted that all these updates should not be applied instantly. Instead, we store them and apply them at last.

During the update $dp[i][j]\rightarrow val$, we need to update

• Global optimum $opt\rightarrow\max\{opt,val\}$
• Local optimum $local\_opt[i]\rightarrow\max\{local\_opt[i],val\}$, and $local\_opt[j]\rightarrow\max\{local\_opt[j],val\}$
• State $dp[i][j]\rightarrow\max\{dp[i][j],val\}$, and $dp[j][i]\rightarrow\max\{dp[j][i],val\}$

After all these, we still have not handled the last number $last$. So we need to compare $opt$ and $dp[last][last]+1$. After that, we add to $opt$ the number of natural triplets $triplets$, and now we have the answer.

Code (C++)
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;
typedef pair<int, int> pii;
int main() {
int n;
cin >> n;
vector<int> a(3 * n);
for (int i = 0; i < 3 * n; ++i)
cin >> a[i];
vector<vector<int>> f(n + 1, vector<int>(n + 1, -INF));
vector<int> local_opt(n + 1, -INF);
f[a[0]][a[1]] = f[a[1]][a[0]] = 0;
local_opt[a[0]] = 0, local_opt[a[1]] = 0;
int triplets = 0, opt = 0;
for (int i = 2; i < 3 * (n - 1); i += 3) {
vector<int> b(3);
for (int j = 0; j < 3; ++j)
b[j] = a[i + j];
if (b[0] == b[1] && b[0] == b[2]) {
triplets++;
continue;
}
for (int p = 0; p <= 2; ++p) {
int q = (p + 1) % 3, s = (p + 2) % 3;
for (int x = 1; x <= n; ++x) {
if (b[q] == b[s])
}
}
for (const auto &u : updates) {
int x = u.first.first, y = u.first.second, val = u.second;
if (f[x][y] < val) {
f[x][y] = f[y][x] = val;
opt = max(opt, val);
local_opt[x] = max(local_opt[x], val);
local_opt[y] = max(local_opt[y], val);
}
}
}
opt = triplets + max(opt, f[a.back()][a.back()] + 1);
printf("%d", opt);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50