B - Line Sensor Editorial by en_translator
The idea of this problem was originally proposed by Keyence.
This problem can be solved with a for statement. If you didn’t manage to solve it, let’s understand the solution of this problem to grasp the for statement.
A for statement is a statement to describe a loop structure, that is, an algorithm of repeating a specific process until a specific condition is satisfied.
Especially, the statement for(int i = 0; i < N; i++)
(or for i in range(N)
in Python) is the commonly used one. With this statement, one can apply the same process for all \(i=0, 1, \dots, N-1\), so we can use it to perform some operation on an array of length \(N\). For example, in ABC272A, you are asked to “find the sum of \(A_0, A_1, \dots\), and \(A_{N-1}\),” which can be solved with a for statement as follows:
// A : array of type int of length N
int s = 0;
for(int i = 0; i < N; i++){
s += A[i];
}
A bit advanced use of the for statement is to nest for statements to describe an algorithm with nested loops, like a double or triple loop.
In this problem, you are asked to find the number of integers \(i\) such that \(C_{i,j}\) is #
; this can be solved by iterating a double loop over the variables \(i\) and \(j\), which can be described by combining for statements in the form for(int i = 0; i < N; i++)
in a nested manner as follows:
// C : two-dimensional array of type char of size H x W
vector<int> ans(W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (C[i][j] == '#') ans[j]++;
}
}
The complexity is \(\mathrm{O}(N^2)\), which is fast enough. Therefore, the problem has been solved.
The idea of nested for
statement can be found in the past Problems B several times. If you struggled with this problem, try solving the following past problems as well. Past Problem 1 Past problem 2
- Sample code (C++)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int H, W;
cin >> H >> W;
vector<string> C(H);
for (int i = 0; i < H; i++) cin >> C[i];
vector<int> ans(W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (C[i][j] == '#') ans[j]++;
}
}
for (int j = 0; j < W; j++) cout << ans[j] << " \n"[j == W - 1];
}
posted:
last update: