えんじにあ備忘録

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

AtCoder Beginner Contest 278にバーチャル参加しました＆反省会

競技プログラミング

AtCoder Beginner Contest 278の振り返り

  • A、B問題は解けた。
  • A問題：配列の先頭の要素を削除するメソッドが分からず検索に時間がかかった。
  • B問題：実装に時間がかかったが考え方は正しかった。
  • C問題：連想配列でフォロー、被フォロー関係を管理していくのだろうが、相互のフォローをどう確認するかがわからなかった。
  • D問題：愚直に配列の要素を変更するクエリを実行する実装にしたが、２ケースでTLEになった。要素数が一定以上になると制限時間に引っかかるようだ。別の実装を思いつけず断念した。

A - Shift

atcoder.jp

考えたこと

  • 配列の先頭の要素を削除する
  • 末尾に0を挿入する
//aはvectorの変数  
a.erase(a.begin());   //aの先頭の要素を削除  
a.push_back(0);  //aの末尾に0を追加

erase関数は要素の位置・範囲を指定して削除できる

std::vector<int> v = {1, 2, 3, 4, 5};
// 2番目の単一要素(値3)を削除
v.erase(v.begin() + 2); // {1, 2, 4, 5}

std::vector<int> v = {1, 2, 3, 4, 5};
// 範囲[v.begin(), v.begin() + 2)の要素を削除
v.erase(v.begin(), v.begin() + 2); //{3, 4, 5}

https://cpprefjp.github.io/reference/vector/vector/erase.html (C++日本語リファレンス)

配列を出力する

for (int i = 1; i <= N; i++) {
    cout << A[i] << (i == N ? "\n" : " ");
}

B - Misjudge the Time

atcoder.jp

考えたこと

  • hの10の位Aと1の位Bを整数除算と剰余算を利用して求める
  • mの10の位Cと1の位Dも同様に求める
  • ACとBDを加算・乗算を利用して計算する
  • 0≤AC≤23 かつ 0≤BD≤59 が成り立つかを調べる
  • 成り立たない場合、ループ構造で1分ずつ加えて、繰り上がり処理に注意する

C - FF

atcoder.jp

考えたこと

  • 連想配列でフォロー、被フォロー関係を管理する

解説*1より

フォロー関係を集合Sに保持することを考える。与えられるクエリは次のように言い換えられる。はじめ、S=∅ 。
1. 集合 S に順序対 (A,B) を追加する。つまり、S←S∪{(A,B)} とする。
2. 集合 S から順序対 (A,B) を取り除く。つまり、S←S∖{(A,B)} とする。
3. 順序対 (A,B),(B,A) がいずれも S に含まれているかを判定する。

// フォロー関係を保持する集合
set<pair<unsigned, unsigned>> follows;
// 順序対 (A, B) を追加
follows.emplace(A, B);
// 順序対 (A, B) を削除
follows.erase({A, B});
// 順序対 (A, B), (B, A) がどちらも含まれるか判定
// count()は引数を要素に含む場合１、含まない場合０を返す。それぞれtrue/false
(follows.count({A, B}) && follows.count({B, A}) ? "Yes" : "No" )

D - All Assign Point Add

atcoder.jp

考えたこと

  • クエリ１を愚直に実行し、配列を初期化する
    →今回の要素数Nは2×105、クエリ１を実行するたびに最大2×105操作することになる
    →クエリ１も最大2×105なので計算量は4×1010
    →実行できる計算量の目安が108なのでTLEになる

対応

  • クエリ１で全要素を初期化するのではなく、初期化する値を保持するだけに留める
  • 変数baseだけで配列の情報を管理する
  • クエリ２で増加する値を差分diffsとする
  • クエリ３で出力されるのはbaseとdiffsの和となる
int main()
{
    int N;
    cin>>N;
 

    int base = 0;
    map<int, long long> diffs; //mapだと初期値が0になるので都合が良い
    for (int i = 1; i <= N; i++) cin >> diffs[i];  //クエリ実行前の入力値を保持

    int Q;
    cin>>Q;
    for (int q=0; q<Q; q++)
    {
        int query;
        cin >> query;
        if (query == 1)
        {
            int x;
            cin >> x;
            base = x;
            diffs.clear(); //baseに代入したため
        }
        if (query == 2)
        {
            int i, x;
            cin>>i>>x;
            diffs[i] += x;
        }
        if (query == 3)
        {
            int i;
            cin >> i;
            cout << base + diffs[i] << endl;
        }
    }
}

参考：https://youtu.be/NtrEpKBe5sg

*1:https://atcoder.jp/contests/abc278/editorial/5230