ABC 346 D/E

久々に練習したらそれなりに時間を費やしてしまったのでなぜ費やしたのか考察しながら解法を残す

D - Gomamayo Sequence

与えられた文字列 S となるべく似た文字列 T を作成する問題。 S 異なる場合には、文字ごとにc[i]のコストが発生するため、c[i] で発生するコストの最小化問題とも言える。
Tは基本的に"0101"と同じ文字が隣り合わない文字列だが、一ヶ所だけ隣り合う場所がある、つまり"010101"の文字列の中に一ヶ所 "00" or "11" が存在する。

検討

文字列の長さが $10^5$ のため、コスト計算に$O(N)$消費する。都度コスト計算を行う場合、比較は最大でも $Log(N)$ 回数しかできないが、おそらく足りないことが想定される。

メモリーにコストを保存することを考える場合、T は $2^N$ 通りあるが、実際には殆どの部分が "010101"の文字列で構成されていることから T が取りうるパターンは少ない。したがって、順序だってTの候補を辿ることができれば、累積和を用いることができそうだと思われる。

条件を考えると、前の計算結果を使い回す場合の初期値は "00" / "11"　の 2 パターンを検討する必要がある。
さらに、Tのi 番目が0で始まる場合,1で始まる場合で場合わけが必要なため、愚直に記述する場合4パターンの初期値が必要となる。

実際に記述してもいいが、4パターン分記述するとミスが生じるので、スッキリしたいところ。
最終的には以下のように分類することで "00","11"を同時に網羅探索した。

• 0101...と '...010' が i, i+1 で結合

  • 探索コストは i = k の時, i = k-1 のコストから導出可能
  • ( i: 0-> n -2 : i ≡ 0 mod 2 の場合 "00", i ≡ 1 mod 2 の場合 "11")

• 1010...と '...101' が i, i+1 で結合

  • 探索コストは i = k の時, i = k-1 のコストから導出可能
  • ( i: 0-> n -2 : i ≡ 0 mod 2 の場合 "11", i ≡ 1 mod 2 の場合 "00")

Code

#include <bits/stdc++.h>
using namespace std;

const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;


void reverse_char(int i, string &s) {
    s[i] = (s[i] == '1')?'0':'1';
}

int main()
{
    // input
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<ll> c(n);

    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }


    // calc
    ll ans = LLINF;
    string base_head1, base_head0;

    for (int i = 0; i < n - 1; ++i) {
        base_head1 += (i % 2 == 0)?"1":"0";
        base_head0 += (i % 2 == 0)?"0":"1";
    }

    //110101 -> 100101 -> 101101 -> 101001 -> 101011
    //001010 -> 011010 -> 010010 -> 010110 -> 010100
    string base_head11 = "1" + base_head1;
    string base_head00 = "0" + base_head0;


    ll base_head11_initcost = 0;
    ll base_head00_initcost = 0;
    for (int i = 0; i < n; ++i) {
        if (base_head11[i] != s[i]) 
            base_head11_initcost+=c[i];
        if (base_head00[i] != s[i]) 
            base_head00_initcost+=c[i];
    }
    ans = min(ans,  base_head11_initcost);
    ans = min(ans,  base_head00_initcost);


    // i -1 と i を反転する
    for (int i = 1; i < n - 1; ++i) {
        reverse_char(i, base_head11);
        base_head11_initcost = ((base_head11[i] == s[i]) ? base_head11_initcost - c[i] : base_head11_initcost + c[i]);

        reverse_char(i, base_head00);
        base_head00_initcost = ((base_head00[i] == s[i]) ? base_head00_initcost - c[i] : base_head00_initcost + c[i]);

        ans = min(ans, base_head11_initcost);
        ans = min(ans, base_head00_initcost);
    }

    cout << ans <<endl;

}

E - Paint

H 行 W 列のグリッドに対して m 個のクエリを実行し、最後に集計する問題。
H, W ともに $10^5$ オーダーで、クエリも $10^5$ オーダーとなり、基本的に数え上げは困難

検討

m 個の各クエリはマスの塗りつぶしを行うため、前半のクエリは上書きされる可能性があり、後半のクエリが重要。
したがって、逆順に処理していくのがよい。

H 行、W 列のうち、行もしくは列のどちらか全てにクエリが実行されたタイミングで、逆順で考える場合それ以前のクエリは意味をなさなくなるため終了することができる。
したがって、見るべきクエリの数は $max(H,W)$

この時点ですでに $O(N)$の計算量が発生するため、独立計算する場合集計処理は最大でも O(LogN)である必要がある。したがって、以下要件を満たす必要がありそう。

• クエリ毎に状態を更新 : $O(1)$から$O(LogN)$
• 更新した状態からマス数の導出 : $O(1)$から$O(LogN)$

ここで最終的に残る色は、$あるクエリで塗られた領域 - その後クロスするユニークなクエリの数$で求められる。

したがって、逆順にクエリを計算する場合には以下で条件を満たすことができる。

• 行、列ごとにこれまで適用されたクエリの数を管理 :更新は　$O(1)$
• 行もしくは列のサイズ - そのクエリ以降に適用されるクエリの数 = 将来的に残るマス目 : $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;

const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;


int main()
{
    ll h,w,m;
    cin >> h >> w >> m;
    vector<tuple<ll,ll,ll>> query;
    for (ll i = 0; i < m; ++i) {
        ll t,a,x;
        cin >> t >> a >> x;
        a--;
        query.push_back(make_tuple(t,a,x));
    }

    ll remainRows = h;
    ll remainColumns = w;

    vector<bool> isPaintedRow(h,false);
    vector<bool> isPaintedColumn(w,false);
    map<ll,ll> BlocksperColor;

    // 
    for (int i = m -1 ; i >= 0 ; --i) {
        int type = get<0>(query[i]);
        ll a = get<1>(query[i]);
        ll x = get<2>(query[i]);

        if (type == 1) {
            if (isPaintedRow[a] == true)
                continue;
            isPaintedRow[a] = true;
            if (BlocksperColor.find(x) != BlocksperColor.end()) {
                BlocksperColor[x] += remainColumns;
            } else {
                BlocksperColor[x] = remainColumns;
            }
            remainRows--;
        } else {
            if (isPaintedColumn[a] == true)
                continue;
            isPaintedColumn[a] = true;
            if (BlocksperColor.find(x) != BlocksperColor.end()) {
                BlocksperColor[x] += remainRows;
            } else {
                BlocksperColor[x] = remainRows;
            }
            remainColumns--;
        }

        if (remainRows ==0 || remainColumns ==0)
            break;
    }


    ll sum = h * w;
    for (auto v:BlocksperColor) {
        if (v.first != 0) {
            sum-= v.second;
        }
    }
    if (sum > 0)
        BlocksperColor[0] = sum;


    vector<pair<ll,ll>> ans;
    for (auto v:BlocksperColor) {
        if (v.second > 0) {
            ans.push_back(make_pair(v.first,v.second));
        }
    }
    std::sort(ans.begin(), ans.end(),[]( pair<ll,ll> &left,pair<ll,ll> &right ){
        return left.first < right.first;
    });


    cout << ans.size() << endl;
    for (auto v:ans) {
        cout << v.first << " " << v.second << endl;
    }

}