AtCoder ABC423 振り返り #C++

はじめに

ABC423に参加したので振り返ります。
結果は2完でした（コンテスト成績表）。
今回は本番で解けたA, B問題と解けなかったC問題についてまとめていきます。

A - Scary Fee

問題は手数料を含めて残高以内に収めつつ最大の引き出し額を求めるというものでした。
引き出し額を W (1000 円単位) とすると、手数料 = (W / 1000) * C 円となり、条件であるW + (W / 1000) * C <= Xを満たす最大の W を求めます。

abc423_a.cpp

#include <iostream>
using namespace std;

int main() {
    long long X, C;
    cin >> X >> C;

    long long k = X / (1000 + C);
    long long answer = 1000 * k;

    cout << answer << endl;
}

B - Locked Rooms

左右両端から到達できない部屋まで数え、そこから到達不可能な部屋数を数えます。

abc423_b.cpp

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N; 
    int L[105];
    int A[105];
    int B[105];

    // ドアの状態を入力
    for (int i = 1; i <= N; i++) {
        cin >> L[i];
    }

    // 配列の初期化（全て到達不可に）
    for (int i = 0; i <= N; i++) {
        A[i] = 0;
        B[i] = 0;
    }

    // 部屋0から行ける部屋を順にチェック
    A[0] = 1;
    for (int i = 1; i <= N; i++) {
        if (L[i] == 0 && A[i-1] == 1) {
            A[i] = 1;
        } else {
            break;
        }
    }

    // 部屋Nから行ける部屋を逆順にチェック
    B[N] = 1;
    for (int i = N; i >= 1; i--) {
        if (L[i] == 0 && B[i] == 1) {
            B[i-1] = 1;
        } else {
            break;
        }
    }

    // 両端から到達できない部屋の数を数える
    int count = 0;
    for (int i = 0; i <= N; i++) {
        if (A[i] == 0 && B[i] == 0) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

C - Lock All Doors

ドアは開閉状態が与えられ、開いているドアだけ移動可能。全閉なら操作0、全開なら全ドアを閉める操作n回、混在の場合は両端の連続閉ドアは触れず、それ以外のドアに操作が必要になります。最終操作回数は n - 2×cnt + sum で求められます。

abc423_c.cpp

#include <iostream>
using namespace std;

int main(){
    // n：ドアの数、r：開始する部屋、a[]：ドアの状態
    int n, r, a[200005], cnt, sum;
	cin >> n >> r;

	// 入力処理
    for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i]) sum++; // a[i]==1なら閉まっているから sum++
	}

	// 左端から連続して「閉まっているドア」を数える
    // ただし開始位置の右側のドア (r+1 番) はスキップ
    for(int i = 1; i <= n; i++){
		if(a[i] && i != r + 1) cnt++;
		else break;
	}

	// 右端からも同様に連続して「閉まっているドア」を数える
    // ただし開始位置の左側のドア (r 番) はスキップ
    for(int i = n; i >= 1; i--){
		if(a[i] && i != r) cnt++;
		else break;
	}

	// 場合分け
    if(sum == n) {
        // 全部しまっている → 何もする必要がない
        cout << 0 << "\n";
    } else if(sum == 0) {
        // 全部開いている → 全部閉めるだけなのでn回
        cout << n << "\n";
    } else {
        cout << n - cnt - cnt + sum << "\n";
    }
}

おわりに

今回は愚直に解き進める問題が多かった印象です。典型の探索系アルゴリズムもそうですが、基礎的なコーディングについても精進していきたいです。