【AtCoder】ABC 482 B - Blank Bingo

2026-11-04

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/6Q AtCoder/アルゴリズムの基礎/forループ競技プログラミング

B - Blank Bingo

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 65 / NoviSteps: 6Q / 配点: 200 点

問題概要

$5\times 5$ のマス目があり、現在のマス目の様子が、oと.からなる長さ $5$ の $5$ つの文字列 $S_1,S_2,S_3,S_4,S_5$ によって与えられる。上から $i$ 行目、左から $j$ 列目のマスには $S_i$ の $j$ 文字目がoのとき印が付いており、.のとき印が付いていない。

ビンゴを達成するために追加で付ける必要のある印の個数の最小値を求めよ。

制約

$S_1,S_2,S_3,S_4,S_5$ はoと.からなる長さ $5$ の文字列

考察

各行・列・斜めのラインにそれぞれについて、.の個数を数え、その最小値が答えとなる。

斜めのラインについては、

$S_{i, i} \: (i=1,2,3,4,5)$ : 左上から右下のライン
$S_{i, 6-i} \: (i=1,2,3,4,5)$ : 右上から左下のライン

の2つのラインがあることに注意。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr int INF = 1e+9;
7. 
8.template <typename T>
9.inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
10. 
11.// ======================================== //
12. 
13.int main()
14.{
15.    vector<string> S(5);
16.    rep(i, 0, 5) cin >> S[i];
17. 
18.    int ans = INF;
19.    rep(i, 0, 5) {
20.        int cnt = 0;
21.        rep(j, 0, 5) {
22.            if (S[j][i] == '.') cnt++;
23.        }
24.        chmin(ans, cnt);
25.    }
26. 
27.    rep(j, 0, 5) {
28.        int cnt = 0;
29.        rep(i, 0, 5) {
30.            if (S[j][i] == '.') cnt++;
31.        }
32.        chmin(ans, cnt);
33.    }
34. 
35.    int cnt = 0;
36.    rep(i, 0, 5) {
37.        if (S[i][i] == '.') cnt++;
38.    }
39.    chmin(ans, cnt);
40. 
41.    cnt = 0;
42.    rep(i, 0, 5) {
43.        if (S[i][4 - i] == '.') cnt++;
44.    }
45.    chmin(ans, cnt);
46. 
47.    cout << ans << endl;
48. 
49.    return 0;
50.}