THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）

5完1WA

各問題

A - Full Moon

N から M を引いて P で割って...、みたいなことをすればよさそうと今気づきましたが、実戦ではループを書いて一日ずつ条件に合っているかどうかを確認しました。

    int ans = 0;
    int x = 0;
    for (int i = 0; i < n; i++) {
        if (m + p * x == i) {
            ans++;
            x++;
        }
    }
    cout << ans << endl;

B - Overlapping sheets

vector<vector<bool>>(N, vector<bool>(N) を用意してシートごとに覆われている範囲を愚直に埋めていき、最後に覆われている領域を数えればよいです。

C - Blue Spring

任意のD日分の運賃を合計してP以上なら周遊パスを買っても損しません。

F を降順にソートして、上から順に D 日分ごとに区切ってそれぞれの区間で得するか損するかを確認していけばよいです。

D - General Weighted Max Matching

dp[選んだ辺の数][どの辺を選んだか（ビットで管理）] で BIT DPをすればよいです。

（追記）選んだ辺の数は不要でした。

E - Sandwiches

map<int, vector<int>> で同じＡが存在する位置を管理します。それぞれについて間にA以外の数がいくつあるかを数えます。

入力例1なら 1 について [1, 3] なので [1]、2 について [2, 5] なので [2] です。

入力例3の 11 についてだと [3, 9, 10, 11] なので [6, 0, 0, 0] です。

で、これらの数が何回使われるかですが、実験すると [c * 1, (c - 1) * 2, (c - 2) * 3, ... , 1 * c] （c は区間の数）となることがわかります。

というわけで、集計した区間の数と掛け合わせることで使われた回数がわかります。（雑

まとめ

D は BIT DP にたどり着くまでに時間をかけてしまったし、E は手計算が間違ってて法則を見つけるのに手間取るしで、いまいちでしたがなんとか水パフォはキープということで。