【競プロ精進ログ】【2021/03/07】ABC194: E ABC159: D

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC194: E – Mex Min
ABC159: D – Banned K
まとめ

ABC194: E – Mex Min

ABC194 より、ABC194: E – Mex Minを解きました。
難易度は緑上位！

昨日のコンテスト中は、TLE 3つで AC できなかったこの問題、余計なコードを一行削除したら普通に AC できました。
緑Diff上位、ほぼ解けてたと思うと悔しいですが、それも含めて実力だと思って精進しましょう。

なお、解法としては、毎回 mex を計算すると O(N^2) になってしまうので、一回 mex を計算して以降は、追加＆削除される値について評価していく形で最小値を求めました。
要は、削除されてバケットが空になった値が、すでに持っている mex の最小値よりも小さいときのみ、 mex の最小値を更新していくイメージです。

提出コードはこちら。

import collections
N, M = map(int,input().split())
A = list(map(int,input().split()))

"""
NOTE: 

・バケットを作って、0 から N-M までの値を順に引いていく
  → 毎回ソートしなくていいはず
・4sec なら N^2 の全探索でいける・・・？
  → TLE
・区間の移動ごとにO(1)の計算量で評価
"""

bkt = collections.Counter(A[:M])
ans = 1500010

def mex(bkt):
    for i in range(N+1):
        if bkt[i] == 0:
            return i

ans = min(ans, mex(bkt))
mincount = 0
for i in range(N-M):
    bkt[A[i]] -= 1
    bkt[A[M+i]] += 1

    if A[i] < ans and bkt[A[i]] == 0:
        ans = A[i]
    elif bkt[ans] == 0:
        continue
    
print(ans)

ABC159: D – Banned K

ABC159 より、ABC159: D – Banned Kを解きました。
難易度は茶色。

一つの要素も隠さない状態の組み合わせの和を sum として、個々のパターンの差分を O(1) で考えていく解法自体はすぐわかったものの、実装バグで WA を出しまくってしまった。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 200010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・各番号のボールの個数のバケットを作成し、一つも消さない状態での組み合わせ数を計算する
・各番号を消したときの個数の変化を、O(1) で計算する 
*************************************************************************************/

vector<lint> A(MAX, 0);
vector<lint> bkt(MAX, 0);

int main()
{
    lint N;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        lint a;
        cin >> a;
        bkt[a]++;
        A[i] = a;
    }

    lint sum = 0;
    for (int i = 1; i <= N; i++)
    {
        lint b = (bkt[i] * (bkt[i] - 1)) / 2;
        sum += b;
    }

    for (int i = 1; i <= N; i++)
    {
        lint tmp = (bkt[A[i]] * (bkt[A[i]] - 1)) / 2;

        bkt[A[i]]--;
        lint c = (bkt[A[i]] * (bkt[A[i]] - 1)) / 2;
        cout << (sum - (tmp - c)) << endl;
        bkt[A[i]]++;
    
    }
    return 0;
}