AtCoder ABC430 振り返り #C++

はじめに

こんにちは、Juna1013です。
今回は11月01日（土）に開催されたABC430に参加したため、振り返っていきたいと思います。
結果は2完でした（コンテスト成績証）。
本番で解けたA・B問題について振り返っていきたいと思います。

A - Candy Cookie Law

簡単な条件分岐の問題でした（問題文読みまちがえてsampleで出力違くて焦りました...）。

abc430_a.cpp

#include <iostream>
using namespace std;

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    if (A <= C) {
        if (B <= D) {
            cout << "No" << endl;
            return 0;
        } else {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

B - Count Subgrid

N × NのグリッドからM × Mを抜き出して異なるパターンが何種類あるのかカウントする問題でした。

各処理の流れについてまとめていきます。

1.入力

入力であるN, M, Sについて入力していきます。Sはグリッドであるため多次元配列を用います。

// 入力
int N, M;
cin >> N >> M;

char S[10][10];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        cin >> S[i][j];
    }
}

2.準備

同じ模様を重複して数えないために、今まで見た模様を保存する配列patternsを準備します。また、異なるパターンを変数patternCountとして数えます。

// パターンを記録するための変数を準備する
char paterns[100][100];
int patternCount = 0;

3.探索

すべてのM × Mの領域を探索します。

3.1 部分領域の文字列化

S[top + i][left + j]の要素を1行ずつ連結してtempに保存します。

// M×M領域を1次元文字列に変換
char temp[100];
int idx = 0;

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        temp[idx++] = S[top + i][left + j];
    }
}
temp[idx] = '\0'; // 文字列の終端を追加

3.2 既出パターンとの比較

これまで保存した全パターンpatterns[p]とtempを1文字ずつ比較します。完全に一致したらsame = trueとなり、処理が終了します。

bool same = false; // 同じ模様があるかどうかのフラグ

for (int p = 0; p < patternCount; p++) {
    bool equal = true; // 一致していると仮定

    for (int k = 0; temp[k] != '\0'; k++) {
        if (patterns[p][k] != temp[k]) { // 1文字でも違えば別パターン
        equal = false;
        break;
        }
    }

    // 完全に一致したら同じパターンとして処理終了
    if (equal) {
        same = ture;
        break;
    }
}

3.3 新しいパターンならカウント

1度も一致しなかったらpatternsの末尾にtempをコピーしてpatternCountをインクリメントします。

if (!same) {
    // tempをpatterns[patternCount]にコピー
    int k = 0;
    while (true) {
        patterns[patternCount][k] = temp[k];
        if (temp[k] == '\0') break;
    }
    patternCount++; // 新しい模様を登録したため加算
}

以下に示すのがコード全文になります。

abc430_b.cpp

#include <iostream>
using namespace std;

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    
    char S[10][10];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> S[i][j];
        }
    }

    // パターンの保存
    char patterns[100][100];
    int patternCount = 0; // 現在保存されている異なるパターンの数

    // すべての部分領域を探索
    for (int top = 0; top <= N - M; top++) {
        for (int left = 0; left <= N - M; left++) {
            // M×M領域を1次元化して保存
            char temp[100]; // 一時的に保存
            int idx = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < M; j++) {
                    temp[idx++] = S[top + i][left + j]; // 領域のマスを順に記録
                }
            }
            temp[idx] = '\0';

            // 既存のパターンと同じかチェック
            bool same = false;
            for (int p = 0; p < patternCount; p++) {
                bool equal = true;
                for (int k = 0; k < idx; k++) {
                    if (patterns[p][k] != temp[k]) { // 異なるパターンの条件
                        equal = false;
                        break;
                    }
                }
                // 同一パターンと判断
                if (equal) {
                    same = true;
                    break;
                }
            }

            // 新しいパターンの保存
            if (!same) {
                // tempの内容をpatterns[patternCount]にコピー
                for (int k = 0; k <= idx; k++) {
                    patterns[patternCount][k] = temp[k];
                }
                patternCount++; // 新しい模様
            }
        }
    }

    // 出力
    cout << patternCount << endl;
    return 0;
}

おわりに

B問題で使用した全探索について理解が浅いと感じたため、精進頑張りたいです。