B - Line Sensor Editorial by Nyaan
この問題の原案はキーエンスから提供されました。
この問題は for 文をうまく使いこなせば解くことができます。この問題を解けなかった方は、この問題の解法を理解して for 文の使い方を理解しましょう。
for 文とは、ループ構造、すなわち同じ処理を所定の条件を満たすまで繰り返し行うアルゴリズムを記述するための構文です。
特に for(int i = 0; i < N; i++)
(Python では for i in range(N)
) という文は for 文の中でも良く使われます。これを利用すると \(i=0, 1, \dots, N-1\) すべての場合について同じ処理を適用することができるので、長さ \(N\) の配列に何らかの処理を行う場合に用いることができます。例えば ABC272A のように「\(A_0, A_1, \dots, A_{N-1}\) の総和を求める」という問題は for 文を利用して次のように解くことができます。
// A : 長さ N の int 型の配列
int s = 0;
for(int i = 0; i < N; i++){
s += A[i];
}
for 文の少し応用的な使い方として、 for 文を入れ子のように組み合わせて、 2 重ループや 3 重ループなどのループが入れ子になった構造のアルゴリズムを記述するというものが挙げられます。
この問題は \(C_{i,j}\) が #
であるような整数 \(i\) の個数を数える問題でした。これは変数 \(i, j\) に対して 2 重ループを回せば計算することができて、これは以下のコードのように先の for(int i = 0; i < N; i++)
という形の for 文を入れ子状に組み合わせれば記述することができます。
// C : サイズ H x W の char 型の 2 次元配列
vector<int> ans(W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (C[i][j] == '#') ans[j]++;
}
}
計算量は \(\mathrm{O}(N^2)\) で、これは十分高速です。よってこの問題を解くことができました。
for
文の入れ子を作るのをテーマとした問題は過去の B 問題でも何度か登場しています。この問題を解くのに苦労した方は次の過去問も解いてみるとよいでしょう。過去問その1 その2
- 実装例 (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: