【c++】ABC363 A-E問題解説【ACコード付き】（毎日ABC day27）

AtCoder Beginner Contest 363

A,B,C,Dの4完。

レートは851→898の+47となり、+50のペースを維持することができた。

連続水色パフォを達成できたのも嬉しいポイント。

ただE問題もBFSであと一歩のところまで行けたので、幅優先探索や深さ優先探索の演習をもっと体に染み付かせたい。

9月中の入水が目標であったが、8月にはARCが3回も開催されることもあり、8月末の入水も視野に入れて精進していく。

A - Piling Up

399以下の正の整数が与えられる。X00 ~ X99のXがレートとなる時、次のレートになるための最小のレートはいくらか、という問題。

単純に余りから100を引けば良いものを、焦りすぎて条件分岐をべた書きしてしまった。
しかも1回条件のイコールを入れ忘れてWAを出してしまった。A問題のWAは痛い。

ll N;

int main()
{
	cin >> N;
	if (N >= 300) cout << 400 - N << endl;
	else if (N >= 200) cout << 300 - N << endl;
	else if (N >= 100) cout << 200 - N << endl;
	else cout << 100 - N << endl;
}

B - Japanese Cursed Doll

$N$ 人の人がおり、それぞれ今の髪の長さは $L_i$ である。全員1ずつ髪が伸びる時、 $T$ を超える長さの人が初めて $P$ 人以上になるのは何日後か、という問題。

全員同じスピードで髪が伸びるので、$N$ 人の髪の序列は変わらない。そのため、 $N-P$ 人目の人の髪の長さが $T$ を超えるのに何日かかるかで判断できる。

ll N, T, P;

int main()
{
	cin >> N >> T >> P;
	vector<ll> tmp;
	for (int i = 1; i <= N; i++)
	{
		cin >> L[i];
		tmp.push_back(L[i]);
	}
	sort(tmp.begin(), tmp.end());
	if (T - tmp[N - P] < 0) cout << 0 << endl;
	else cout << T - tmp[N - P] << endl;
	return 0;
}

C - Avoid K Palindrome 2

英小文字のみからなる長さ $N$ の文字列 $S$ が与えられます。$S$ の文字を並び替えて得られる文字列（ $S$ 自身を含む）であって、長さ $K$ の回文を部分文字列として 含まない ものの個数を求めてください。

以前順列全探索の過去問を解いた時にライブラリ化しておいた関数を使用。

ひたすら全ての文字列パターンを生成し、長さ $K$ の回文が含まれていないものをカウントする。

ll N, K;
string S;

// 順列全探索ライブラリ
namespace PermutationSearch {
    // 全ての順列を生成して処理する関数
    template <typename T>
    void generatePermutations(vector<T>& elements, void (*process)(const vector<T>&, ll&), ll& count) {
        // ソートして最初の順列を準備
        sort(elements.begin(), elements.end());

        do {
            // 現在の順列を処理する
            process(elements, count);
        } while (next_permutation(elements.begin(), elements.end()));
    }
}

// 長さ K の回文が部分文字列として含まれているかをチェックする関数
bool containsPalindrome(const string& str, int K) {
    for (int i = 0; i <= (int)str.size() - K; ++i) {
        bool isPalindrome = true;
        for (int j = 0; j < K / 2; ++j) {
            if (str[i + j] != str[i + K - 1 - j]) {
                isPalindrome = false;
                break;
            }
        }
        if (isPalindrome) {
            return true;
        }
    }
    return false;
}

// 順列を処理する関数
void processPermutation(const vector<char>& permutation, ll& count) {
    string permStr(permutation.begin(), permutation.end());
    if (!containsPalindrome(permStr, K)) {
        count++;
    }
}

int main() {
    cin >> N >> K >> S;

    vector<char> elements(S.begin(), S.end());
    ll count = 0;

    // 順列全探索を実行
    PermutationSearch::generatePermutations(elements, processPermutation, count);

    cout << count << endl;

    return 0;
}

D - Palindromic Number

非負整数 $X$ を 10 進表記(先行ゼロ無し)で表した文字列が回文である時、$X$ を回文数と呼びます。
例えば 363,12344321,0 はいずれも回文数です。小さい方から $N$ 番目の回文数を求めてください、という問題。

1桁の数字は0から9まで全て回文数に当てはまるので、10番目以下の回文数は $N-1$ を出力する。
2桁目以上の数字は、9個、90個、900個、というように桁数ごとに回文数が増えていく。
また、回文数を生成する際には、前半部分を生成し、後半部分を前半部分を反転させたものを結合することで回文数を生成する。

ll N;
ll power10[19];

void initialize_power10() {
    power10[0] = 1;
    for (int i = 1; i < 19; ++i) {
        power10[i] = power10[i - 1] * 10;
    }
}

string generate_palindrome(ll num, bool is_odd_length) {
    string half = to_string(num);
    string palindrome = half;
    if (is_odd_length) half.pop_back();
    reverse(half.begin(), half.end());
    palindrome += half;
    return palindrome;
}

int main() {
    cin >> N;
    initialize_power10();

    ll count = 10;
    if (N <= count) {
        cout << N - 1 << endl;
        return 0;
    }

    // N番目の回文数を探す
    for (int length = 2; ; length++) {
        ll half_length = (length + 1) / 2;
        ll start = power10[half_length - 1];
        ll end = power10[half_length];
        ll range_size = end - start;

        if (N <= count + range_size) {
            ll num = start + (N - count - 1);
            cout << generate_palindrome(num, length % 2 == 1) << endl;
            return 0;
        }

        count += range_size;
    }

    return 0;
}

E - Sinking Land

$H×W$ の大きさの島があり、島は周りを海で囲まれている。それぞれのマスの標高は $A_{i,j}$ であり、$1$ 年ごとに海面が $1$ 上昇する。海面が上昇した結果、海に沈むマスに隣接しており、海面以下の標高のマスも沈む。$Y$ 年後に海に沈まず残っている陸地の面積を求めよ、という問題。

BFSという​根本のアルゴリズムは間違えていなかったが、コンテスト中は海の場所をqueに追加しており、毎年重複処理が出てしまっていてTLEを出してしまった。

解説を見て海に接している海岸をqueに年度ごとに分けて追加することで、重複処理を防ぎ、ACを出すことができた。あっぱれ。

// コンテスト中に提出した TLE コード
ll H, W, Y;
ll board[1009][1009];
bool sinked[1009][1009];
queue<pair<ll, ll>> que;

int main()
{
    // 入力
    cin >> H >> W >> Y;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin >> board[i][j];
            sinked[i][j] = false;
        }
    }
    // 周囲の海を初期化
    for (int i = 0; i <= H + 1; i++)
    {
        sinked[i][0] = true;
        sinked[i][W + 1] = true;
    }
    for (int j = 0; j <= W + 1; j++)
    {
        sinked[0][j] = true;
        sinked[H + 1][j] = true;
    }

    ll area_island = H * W;

    // BFSのための方向ベクトル
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // 各年ごとの処理
    for (int year = 1; year <= Y; year++)
    {
        // 初期状態として、すでに沈んでいる区画をキューに追加
        for (int i = 0; i <= H+1; i++)
        {
            for (int j = 0; j <= W+1; j++)
            {
                if (sinked[i][j])
                {
                    que.push(make_pair(i, j));
                }
            }
        }

        // 幅優先探索
        while (!que.empty())
        {
            pair<ll, ll> p = que.front();
            que.pop();
            ll x = p.first;
            ll y = p.second;

            for (int d = 0; d < 4; d++)
            {
                ll nx = x + dx[d];
                ll ny = y + dy[d];

                if (nx > 0 && nx <= H && ny > 0 && ny <= W && !sinked[nx][ny] && board[nx][ny] <= year)
                {
                    que.push(make_pair(nx, ny));
                    sinked[nx][ny] = true;
                    area_island--;
                }
            }
        }

        // 各年ごとの結果を出力
        cout << area_island << endl;
    }

    return 0;
}

以下はコンテストが終了してから、queを修正してから提出したACコード。
標高よりも海面が低い時には絶対に沈まないことを利用し、それぞれの年度でqueを分けているのが賢い。

// コンテスト終了してから提出した AC コード。
ll H, W, Y;
ll board[1009][1009];
bool sinked[1009][1009];
queue<pair<ll, ll>> que[100009];

int main()
{
    // 入力
    cin >> H >> W >> Y;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin >> board[i][j];
            sinked[i][j] = false;
            if (i == 1 || i == H || j == 1 || j == W)
            {
                que[board[i][j]].push(make_pair(i, j));
                sinked[i][j] = true;
            }
        }
    }

    ll area_island = H * W;

    // BFSのための方向ベクトル
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // 各年ごとの処理
    for (ll year = 1; year <= Y; year++)
    {

        // 幅優先探索
        while (!que[year].empty())
        {
            area_island--;
            pair<ll, ll> p = que[year].front();
            que[year].pop();
            ll x = p.first;
            ll y = p.second;

            for (int d = 0; d < 4; d++)
            {
                ll nx = x + dx[d];
                ll ny = y + dy[d];

                if (nx > 0 && nx <= H && ny > 0 && ny <= W)
                {
                    if (!sinked[nx][ny])
                    {
                        que[max(board[nx][ny], year)].push(make_pair(nx, ny));
                        sinked[nx][ny] = true;
                    }
                }
            }
        }
        // 各年ごとの結果を出力
        cout << area_island << endl;
    }

    return 0;
}