AtCoder Beginner Contest 298 に参加しました＆反省会

AtCoder Beginner Contest 298 の振り返り

• コンテストがunratedになり正直助かった。A問題しか解けなかった。
• A問題：一文字ずつ条件を満たすかを確認する
• B問題：回転させる際に発生したエラーの原因がわからず。回転の処理も回数や中止する条件がわからなかった
• C問題：二重のvectorがTLEになったためvectorにmultiset,setを格納して高速化するはずが、それらの集合型にinsertする処理ができなかった

B問題

atcoder.jp

解説*1から

• 一度操作すると行列が回転するので回操作すると元の状態に戻ります。
• を回転して得られる行列としてあり得るものすべてに対し、[tex: A{i,j} = 1 ]のとき[tex: B{i,j} = 1 ]が成り立っているかを調べればよいです。
• 添字については配列の左下から始まり上方向にアクセスするためN-1から0まで1ずつ減らしながらアクセスします。次の記事がわかりやすいです。
  daeudaeu.com

実装例

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> rotate(vector<vector<int>> a) {
    int n = a.size();
    vector<vector<int>> res(n, vector<int>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[j][n - 1 - i] = a[i][j];
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
    vector<vector<int>> b(n, vector<int>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> b[i][j];
    for (int _ = 0; _ < 4; _++) {
        bool ok = true;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] == 1 && b[i][j] == 0) ok = false;
        if (ok) {
            cout << "Yes\n";
            return 0;
        }
        a = rotate(a);
    }
    cout << "No\n";
}

C問題

atcoder.jp

解説*2から

• 配列および をもっておきます。では箱に入っているカードの多重集合、ではが書かれたカードが入っている箱の番号の集合を管理します。
• クエリではにを追加し、にを追加します。これは各クエリで行えます。
• クエリではに対し昇順にをし出力、クエリではそれに加えて重複要素の削除を行えばよいです。これは出力する数の個数の合計をとするとすべてのクエリで合わせてで行うことができ、より十分高速です。 実装例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200010;
const int M = 200010;
vector<vector<int>> box(N, vector<int>());
vector<vector<int>> card(M, vector<int>());

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> ans;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, j;
            cin >> i >> j;
            card[i].push_back(j);
            box[j].push_back(i);
        }
        else if (t == 2) {
            int i;
            cin >> i;
            sort(box[i].begin(), box[i].end());
            for (int j = 0; j < box[i].size(); j++) {
                cout << box[i][j] << "\n "[j + 1 != box[i].size()];
            }
        }
        else {
            int i;
            cin >> i;
            sort(card[i].begin(), card[i].end());
            card[i].erase(unique(card[i].begin(), card[i].end()), card[i].end());
            for (int j = 0; j < card[i].size(); j++) {
                cout << card[i][j] << "\n "[j + 1 != card[i].size()];
            }
        }
    }
}

• 重複要素の削除について std::unique関数を利用する。

  この関数は、隣り合った重複要素を除いた要素を、範囲の先頭に集める。この関数によってコンテナから直接要素が削除され、コンテナの要素数が減るようなことはない。コンテナから実際に要素を削除する場合は、この関数の戻り値として、先頭に集められた重複なし範囲の末尾の次を指すイテレータが返るため、そのイテレータを介してコンテナのerase()メンバ関数などを呼び出し、削除を行うこと。

unique - cpprefjp C++日本語リファレンス

*1:https://atcoder.jp/contests/abc298/editorial/6215

*2:https://atcoder.jp/contests/abc298/editorial/6215