えんじにあ備忘録

脱よわよわエンジニアを目指すブログ

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

競技プログラミング

AtCoder Beginner Contest 294 の振り返り

  • C問題まで解くことができた
  • A問題：入力値が偶数の場合のみ出力する
  • B問題：数値からアルファベットに変換する箇所でエラーが発生していると勘違いし時間を浪費した。実際には、ベクターの初期化を怠ったせいだ
  • C問題：A,Bの要素がそれぞれCでは何番目かを格納するベクターを用意したが、どちらかの列しか残されない状況で条件分岐させることを気づくのに遅れた
  • D問題：呼ばれていない人の集合を管理しようとしたので間違えた

B問題

atcoder.jp

方針

  • n 番目の大文字のアルファベットをchar c = 'A' + n - 1で変換する

解説*1から

  • 数字から文字への対応を自分で書くことで文字コードを直接使うことなくこの問題を解くことができる
    実装例
#include <iostream>
#include <string>
using namespace std;

string convert = ".ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  int H, W;
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int x;
      cin >> x;
      cout << convert[x];
    }
    cout << endl;
  }
}

C問題

atcoder.jp

解説*2から

  • C=(C_1, C_2,...,C_{N+M}) は、列を連結してソートすることで O( (N+M)log(N+M) ) 時間で求めることができる
  • Cが具体的に得られたら、 C_i の値から i を計算することが O(log(N+M)) 時間やexpected O(1)時間で可能

Cに対する二分探索の実装例

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<unsigned> A(N), B(M);
    for (auto &&a : A) cin >> a;
    for (auto &&b : B) cin >> b;

    vector<unsigned> C(N + M);
    merge(begin(A), end(A), begin(B), end(B), begin(C));

    for (const auto a : A)
        cout << lower_bound(begin(C), end(C), a) - begin(C) + 1 << " ";
    cout << endl;

    for (const auto b : B)
        cout << lower_bound(begin(C), end(C), b) - begin(C) + 1 << " ";
    cout << endl;

    return 0;
}
  • std::lower_bound関数：ソート済みイテレータ範囲に対して、任意の値を二分探索で見つけるために使用できる
    戻り値はイテレータ 計算量は最大で log2(last-first) + O(1) 回の比較を行う

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

D問題

atcoder.jp

解説*3から

  • std::setのような順序付き集合型を利用する。「受付に呼ばれたが、まだ受付に行っていない人」の集合を管理しながらイベントを処理する
    • calledを「受付に呼ばれたが、まだ受付に行っていない人」の集合とする。はじめ called は空である。
    • また、last を最後に呼ばれた人の番号とする。便宜上 はじめ last は 0 とする。
    • その後、イベントを順に処理する。イベントの種類に応じて次の処理を行う。
      • 1種類目のイベントの場合、次に呼ばれるのは last + 1 である。よって last に 1 を足したあとに called に last を追加する。
      • 2種類目のイベントの場合、x を called から削除する。
      • 3種類目のイベントの場合、called の最小の要素が答えである。よってこれを出力する。

上記の手順中、calledに関する操作は「要素の追加」「要素の削除」「最小の要素の出力」で、順序付き集合型を用いることで操作をすべて 1回あたり O(logN) で行うことができる。クエリ全体で O(QlogN)でこの問題を解くことができる。

実装例

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;

  set<int> called;
  int last = 0;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      called.insert(++last);
    } else if (event == 2) {
      int x;
      cin >> x;
      called.erase(x);
    } else {
      cout << *begin(called) << "\n";
    }
  }
}

*1:https://atcoder.jp/contests/abc294/editorial/6025

*2:https://atcoder.jp/contests/abc294/editorial/5989

*3:https://atcoder.jp/contests/abc294/editorial/6005