前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26707534

慣れていると、この問題がかなりフロー系で解けるのではないかという感じに思えてくる。
理由としてははっきり言えないのだが、

ペアを作る、マッチングをするような問題である
総和の最大値を求める
結構微妙な制約

みたいな所からフロー感が漂う。
コストが含まれるので最小費用流で考えていくと解ける。

なお、今回の問題はよりストレートに重み付き二部グラフ上での最大マッチングとして定式化できる。
やってることは変わらないような気もするが、自分は最小費用流の延長戦上として解いた。

最小費用流

もし、最小費用流について知らない場合はどこかで調べてこよう。
最小費用流は名の通り最小値を求めるアルゴリズムであるので、入門としては最小値を求めるような問題がいいだろう。
他の問題を入門として選ぶことを勧める。

さて、理解はできているものとして話を進めていこう。

「選択」を分岐で表現する

さて、選択を作っていく。
グラフは

始点と終点
オスpを表す頂点
メスqを表す頂点

のP+Q+2頂点を用意しよう。
ここでオスpとメスqがつがいになる場合は、

始点→オスp→メスq→終点

の経路で流量1だけ流れるという風に定義しよう。

(流量,コスト)
始点-(1,0)→オスp-(1,A[p]+C[q])→メスq-(1,0)→終点

という感じである。
逆につがいにならなかった場合は、その2匹間に流れないので、

始点-(1,B[p]+D[q])→終点

ということになる。これをすべてのペアについて作っていけばいいのだが、そうすると、
始点と終点の間に複数の辺で複数のコストのものが出来上がってしまう。
これでは、うまく選択されていないペアの所に流量を流すことができなくなってしまう。
ここで1工夫加えよう。

全部選択してないことをベースに考える。

選択によって幸福度を変化させるのではなく、すべてのオスとメスは最初は含まれない状態から始めて、
つがいを作ると、そのオスとメスの幸福度が変化するという風に考えることにしよう。

より具体的には、最初は幸福度はBの総和とDの総和ということにしておく。
そして、オスpとメスqがつがいになったとしたら、幸福度が+(A[p] - B[p] + C[q] - D[q])されるということにしておく。
こうすることで選択としては、つがいにならないなら幸福度は+0だし、
つがいになったら+(A[p] - B[p] + C[q] - D[q])されることになる。

フローとして考えると、オスpとメスqがつがいになるなら

始点-(1,0)→オスp-(1,(A[p] - B[p] + C[q] - D[q]))→メスq-(1,0)→終点

であり、つがいにならなかった場合は、

始点-(1,0)→終点

のようにする。こうすれば始点と終点の間の辺はすべて同じになるので1つにまとめることができるようになる。

まとめると

さて、まとめるとフローは以下のようになる

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,A[p] - B[p] + C[q] - D[q]) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), 0) の辺を張る

min(P,Q)と書いているのはペアが作れるのは最大min(P,Q)組だけだからである。
これで最大費用流みたいな感じで流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+(最大費用)が答えになる。
ここまで理解できていればほぼほぼ答え。

最小費用流ですよ…

最大ではなく最小なので、コストを逆転させて負の数にすることで最大値を負の数にしたものを答えとして
出させるようにする。

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,-(A[p] - B[p] + C[q] - D[q])) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), 0) の辺を張る

最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)-(最小費用)が答えになる。
最小費用流はコストが正になる必要があるので、これもちょっとだめで、下駄をはかせる必要がある。
MAXを2*10⁹くらいに設定しておいて、つがいを作った場合とそうでない場合についてMAX分だけ
コストに下駄をはかせることにする。つまり…

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,MAX-(A[p] - B[p] + C[q] - D[q])) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), MAX) の辺を張る

こんな感じにする。
最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+MAX×min(P,Q)-(最小費用)が答えになる。
このように下駄を履かせた分だけ引けば全体を正のまま保ちつつ正答が得られる。

int P, Q;
string S[101];
ll A[101], B[101], C[101], D[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> Q;
    rep(p, 0, P) cin >> S[p];
    rep(p, 0, P) cin >> A[p] >> B[p];
    rep(q, 0, Q) cin >> C[q] >> D[q];

    atcoder::mcf_graph<int, ll> mcf(P + Q + 2);
    int st = P + Q;
    int gl = st + 1;
    int maxflow = min(P, Q);

    ll MAX = inf * 2;
    rep(p, 0, P) mcf.add_edge(st, p, 1, 0);
    rep(p, 0, P) rep(q, 0, Q) if (S[p][q] == '1') mcf.add_edge(p, P + q, 1, MAX-(A[p] - B[p] + C[q] - D[q]));
    rep(q, 0, Q) mcf.add_edge(P + q, gl, 1, 0);
    mcf.add_edge(st, gl, maxflow, MAX-0);

    int _; ll cost;
    tie(_, cost) = mcf.flow(st, gl, maxflow);

    ll ans = 0;
    rep(p, 0, P) ans += B[p];
    rep(q, 0, Q) ans += D[q];
    ans += MAX * maxflow - cost;
    cout << ans << endl;
}

2021-10-21

Reverse Array [第八回アルゴリズム実技検定 J]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_j

前提知識

遅延評価セグメントツリー

解説

https://atcoder.jp/contests/past202109-open/submissions/26703507

遅延評価セグメントツリー以外にも沢山実装方法があるように見える。
今回、自分がやったやり方を説明していこう。

重要性質は何か

今回面倒なのは反転操作であると思うが、何回操作を行っても、回文関係にある部分が
反転するか反転してないかの状態にしかならない。
よって、保持すべき情報、判断すべき情報は、反転しているかどうかだけである。
これをうまくやっていくにはどうすればいいだろうか。

反転操作は区間について行うことになるが、その区間において反転するしないが逆転するような感じになる。
0を反転しない、1を反転するということにすると区間について1でXORをしているような操作になる。
これはそのまま遅延評価セグメントツリーに乗せることもできるが、
自分は区間について+1するような遅延評価セグメントツリーを書いた。
+1するようにしておけば2の倍数であれば反転しないし、2の倍数でないなら反転することに相当する。

まとめ

ちょっとわかりにくかったかもしれないので、実際の実装に落とし込んだ場合としてまとめておく。
区間addを実装した遅延評価セグメントツリーを用意しておく。

t=1のときは、左からk番目の遅延評価セグメントツリーの要素を見て、2の倍数であれば、kを答え、
2の倍数でないなら、2N - k + 1を答える。

t=2のときは、遅延評価セグメントツリーにおいて[N - k + 1, N + k]の要素を+1する

自分の実装では0-indexedになっているので添え字がけっこうややこしいが、以上を実装すればAC.

int N, Q;
LazySegTree<int,1<<19> lst;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    
    rep(i, 0, Q) {
        int t, k; cin >> t >> k;

        if (t == 1) {
            k--;
            if (lst.get(k, k + 1) % 2 == 0) printf("%d\n", k + 1);
            else printf("%d\n", 2 * N - k);
        }
        else {
            lst.update(N - k, N + k, 1);
        }
    }
}

2021-10-21

/2 and *3 [第八回アルゴリズム実技検定 I]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_i

解説

https://atcoder.jp/contests/past202109-open/submissions/26690153

難しい問題。色々方針が思い浮かぶかもしれないが、思いつかないと中々厄介だろうと思う。

本質を見抜く

実は、今回の操作はやればやるだけ状況が改善される。
操作で÷2を行ったときに最小値がより小さくなってしまった場合は自分に×3をすればいい。
なので、すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行うことにしよう。

加えてもう1つ便利な性質として全体でcnt回操作が行えるときに、全体で÷2をcnt回、×3をcnt回行うことができるが、
÷2の操作が×3の操作に影響はせず、逆もまたしかりなので、最初に÷2をcnt回してしまって、最後に×3をcnt回行っても
問題ない。

おさらいすると、以下の性質が問題を解くうえで便利である。

すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行う
最初に÷2をcnt回してしまって、最後に×3をcnt回行っても問題ない

最適動作を考える

÷2はどのように操作をしても結果は変わらないので、操作後は一意な状態となる。
ここから適切に×3をcnt回行うことで最小値を最大化したい。
これには貪欲に小さい数から優先的に×3を行っていくことで実現できる。
なので、N個の数から最小値を高速に取り出して×3をして入れなおすということを繰り返すことができればACできる。
このために優先度付きキューを使うことができる。
C++では要素の最大値を返すようになっているので負数を使うか比較関数を用意することで最小値を返すように改造すること。

操作回数の最大値

特に工夫しなくても操作をそのまま実装すれば今回は間に合う。
計算量のキーになりそうなのが、操作回数の最大値であるが、これは÷2を行う最大回数と一致する。
÷2をしていくと急激に数が小さくなっていく、もう少し正確に書くと、最大回数はlog2(10⁹)くらいになるので、30回とかそんなもん。
なので30N回くらいが最大値でこれは全部普通に行っても計算時間的には間に合う。

int N; ll A[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    min_priority_queue<ll> que;
    int cnt = 0;
    rep(i, 0, N) {
        while (A[i] % 2 == 0) cnt++, A[i] /= 2;
        que.push(A[i]);
    }
    rep(i, 0, cnt) {
        ll top = que.top() * 3;
        que.pop();
        que.push(top);
    }

    ll ans = que.top();
    cout << ans << endl;
}

2021-10-21

Shortest Path [第八回アルゴリズム実技検定 H]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_h

前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26687334

今回の問題は制約が割と緩いので、基本的な典型アルゴリズムを理解していると解ける。

愚直に考えてみる

条件を満たす都市の組(i,j)が存在するかを判定することが要求されているが、
都市の組については全探索できる制約となっている。
なので、愚直に考えるとすると、都市の組(i,j)を全探索して、各組について距離を求めてXのものがあればYesと答えるようにする。

だが、都市の組(i,j)の全列挙はすでにO(N²)となるので、制約から見ると計算時間はあまり余裕がない。
残る問題は木上の2頂点間の距離を高速に求めるという部分であるが、これは典型アルゴリズムが存在する。

木上の2点間の距離

これを求める方法の1つとしてLCAと累積和を利用する手法がある。
典型だからググって読んでみてと書こうとしたがさっと探して見当たらなかったので、少し詳しく書いておく。
LCAと累積和についてはそれぞれ良質な記事が存在しているので書かない。
もし知らない場合は、検索して学習しよう。
自分はLCAはHL分解を利用したものを使っているが、ややこしいので普通にダブリングで実装したものを使うといい。

さて、木上の2点(a,b)について距離を求める。

木の根をどこでもいいので設定
LCAの構築
すべての頂点について根からの距離を累積和っぽくDFSで求めておく。配列totとする。

ここまでが事前準備で、利用するときは、

頂点(a,b)からLCAを求める。頂点lcとする
頂点(a,b)間の距離はtot[a] + tot[b] - 2 * tot[lc]となる

細かく見ていこう

手順1

根っこはどこでもいいが、ランダムにしておくと、いじわるなケースを意図せず回避できるかもしれない。
本質的な改善ではないから、普通に0にしとけばいい。

手順2

LCAの構築は、どこかを見て、調べてほしい。
自分はHL分解でやっているが、やや難しいので、ダブリングが楽。
どちらにしろ、ライブラリ化しておくといい。

手順3

手順1で決めた根から累積和で配列totを計算する。

tot[cu] := 根から頂点cuまでの経路の重みの和

累積和と書いているのは、とある頂点cuの子供toへは

tot[to] = tot[cu] + (cuからtoへの重み)

のように計算ができるので、累積和っぽく高速に求めることができるためである。

手順4

これはLCAがあればよい。
頂点aと頂点bのLCAを頂点lcとしておこう。

手順5

すると、頂点aから頂点bへの距離は、tot[a] + tot[b] - 2 * tot[lc]で求められる。
もう少しかみ砕くと、

「頂点a -> 頂点b」は「頂点a -> 頂点lc -> 頂点b」と経路を分解できる。
「頂点a -> 頂点lc」はtot[a] - tot[lc]と計算でき、「頂点lc -> 頂点b」はtpt[b] - tot[lc]と計算できる。
よって、足し合わせるとtot[a] + tot[b] - 2 * tot[lc]となる。

int N, X;
vector<pair<int, int>> E[3010];
//---------------------------------------------------------------------------------------------------
int tot[3010];
void dfs(int cu, int pa = -1) {
    fore(p, E[cu]) if (p.first != pa) {
        tot[p.first] = tot[cu] + p.second;
        dfs(p.first, cu);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    HLDecomposition hld;
    hld.init(N);
    rep(i, 0, N - 1) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        hld.add(a, b);
        E[a].push_back({ b, c });
        E[b].push_back({ a, c });
    }
    
    hld.build(0);
    dfs(0);

    rep(a, 0, N) rep(b, a + 1, N) {
        int lc = hld.lca(a, b);
        int len = tot[a] + tot[b] - 2 * tot[lc];
        if (len == X) {
            cout << "Yes" << endl;
            return;
        }
    }

    cout << "No" << endl;
}

2021-10-21

K-th element [第八回アルゴリズム実技検定 G]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_g

前提知識

二分探索

解説

https://atcoder.jp/contests/past202109-open/submissions/26603092

この問題は正直典型問題として知っていないと解くのは難しいように思う。
二分探索を利用することで解くことができる。
全てそうかは分からないが、以下から類題を探せるかもしれない。
https://drken1215.hatenablog.com/archive/category/k%E7%95%AA%E7%9B%AE%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B

「K番目の要素」

このK番目の要素という題名がヒントになっていて、やや典型テクとしてK番目の要素を求めるなら二分探索みたいな
テクというか、よく出る手法というかがある。
あまりピンとこないかもしれない。
二分探索の比較関数を定義しよう。

比較関数

check(lim) := 数列の要素の中でlim以下のものの個数を集計したときに、K以上個あればtrue、さもなければfalse

ちょっとわかりにくいかもしれない。
少し例を使って説明してみよう。

check(0)は、数列の要素の中で0以下のものを集計していて、そんな要素はないので、かならずfalseになる。
check(∞)は、数列の要素の中で∞以下のものを集計していて、すべての要素が含まれるため、かならずtrueになる。
これはよくって…

例えば答えがansであった場合を考えてみよう。
check(ans)は、数列の要素の中でans以下のものを集計している。
K番目がansという定義で進めているので、数列の要素の中でans以下のものはK個はあるはずである。
よって、K以上個あるのでtrueになる。

check(ans - 1)を考えてみると、K番目がansであるはずなので、数列の要素の中でans-1以下の個数は
K個未満のはずである。
そのため、check(ans - 1)はfalseとなる。

二分探索的にはちょうど境界線上に答えが浮かび上がってくることになる！
なので、比較関数を高速にさばくことができれば、二分探索で答えを導くことができる。

lim以下の要素の個数

全ての数列それぞれに対して、lim以下の要素の個数を求めてその総和を取ればいい。
なので、とある数列に対してlim以下の要素が何個あるかについて高速に計算したい。
これはmin(1LL * A[i], 1LL + (lim - B[i]) / C[i])で求めることができる。

minを使っているのは個数の最大値はA[i]個なので、その上限を決めるために使っている。
なお、1LLを使っているのはlong longに型変換させるために使っている。明示キャストでも問題ない。

実際の個数計算は1LL + (lim - B[i]) / C[i]である。
例えば3 5 7 9 11という数列があって、10以下の個数を求める場合を考えてみる。
最初の3は含まれるとカウントして、全部の数から初項を引いてみよう。
0 2 4 6 8という数列で7以下の個数を求める問題になる。
これは丁度倍数の個数を求めているような感じになるので、7から公差である2を割ったときの商を使えばいい。
7÷2の商は3なので、初項の1つと合わせて1+3の4個が答え。
これを数式に落とし込むと、1LL + (lim - B[i]) / C[i]になる。

int N; ll K;
int A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
bool check(ll lim) {
    ll cnt = 0;
    rep(i, 0, N) if (B[i] <= lim) cnt += min(1LL * A[i], 1LL + (lim - B[i]) / C[i]);
    return K <= cnt;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i] >> B[i] >> C[i];

    ll ng = 0, ok = infl;
    while (ng + 1 != ok) {
        ll md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }

    cout << ok << endl;
}

2021-10-21

Incomplete Permutation [第八回アルゴリズム実技検定 F]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_f

構築

解説

https://atcoder.jp/contests/past202109-open/submissions/26602840

構築問題。
構築問題の基本は、シンプルな構築ルールである。
なるべく簡単に簡単に条件を満たせるルールを使うことが大切。

-1のとき

構築できない場合はどういった場合かを考えてみると、0が1つの場合になる。
0が1つであるので、他はすべて1ということになる。
1の部分は添え字と同じ数字になっている必要があるが、そうすると、0の部分で使える数字は
その添え字の数字しかなくなり、添え字と違う数字を割り当てることができない。

構築できない場合をざっくり考えてみると他に無さそうではある。
（構築法を考えると、0が1つのときだけだなという確信が増してくる）

どういった構築ルールにするか

適当に並び替えてやれば条件を満たしそうではあるが、それは人間視点であり、
どんな状況でも単一ルールで条件を満たすようなものを考えてみよう。

自分は0の部分の添え字を1つずつ横にずらすことで、自分の添え字とは違うようにした。
実装ではdequeを使った実装を行った。
1つずつ横にずらす必要があるので、順番にdequeに入れておいて、そのあと、
先頭の1つを取り出して、末尾に追加してやれば1つずらしたような感じになる。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    
    deque<int> zero, one;
    rep(i, 0, N) {
        if (S[i] == '0') zero.push_back(i + 1);
        else one.push_back(i + 1);
    }

    if (zero.size() == 0) { }
    else if (zero.size() == 1) {
        cout << -1 << endl;
        return;
    }
    else {
        int top = zero.front();
        zero.pop_front();
        zero.push_back(top);
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        if (S[i] == '0') {
            printf("%d", zero.front());
            zero.pop_front();
        }
        else {
            printf("%d", one.front());
            one.pop_front();
        }
    }
    printf("\n");
}

2021-10-21

Colorful T-Shirts [第八回アルゴリズム実技検定 E]

競技プログラミング

https://atcoder.jp/contests/past202109-open/tasks/past202109_e

解説

https://atcoder.jp/contests/past202109-open/submissions/26602632

貪欲法で解いていく。
かかる値段を最小化したいと考えた場合、簡単な方針として、安いものから選択するという方針がある。
今回はこれで解いていこう。

安いものから選択する

具体的に方針を示すと、全てのTシャツを価格が安い順に並び替えて、買うかどうかを判定していく。
まだ買ってない色のTシャツなら購入して、そうでないなら買わないという感じで購入していき、
K枚買ったら終了。

実装について

自分のC++の実装では、pairとソートをうまく使って、順番に処理している。
pairの配列に対して昇順ソートを適用すると、第一要素で昇順にして、第一要素が同じなら第二要素で昇順にしてくれる。
今回はpairの第一要素に値段をおいてソートを行う。
第二要素はソート的には使っていない（別にどんな順番でもいい）のだが、
色を保持しておくことでソートしても対応する色を楽に取ってくることができる。
この辺は好き好きで実装するといい。

あと、購入済みの色を管理するためにsetを利用している。

int N, K;
int c[101010], p[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> c[i];
    rep(i, 0, N) cin >> p[i];

    vector<pair<int, int>> orders;
    rep(i, 0, N) orders.push_back({ p[i], c[i] });
    sort(all(orders));

    set<int> used;
    ll ans = 0;
    rep(i, 0, N) {
        int price = orders[i].first;
        int color = orders[i].second;

        if (used.count(color)) continue;

        ans += price;
        used.insert(color);

        if (used.size() == K) {
            cout << ans << endl;
            return;
        }
    }

    cout << -1 << endl;
}