ECR154-E Non-Intersecting Subpermutations

問題

https://codeforces.com/contest/1861/problem/E (diff 2300)

1以上 k以下の整数からなる長さ nの数列 aについて、 aの美しさを以下の通り定める。

  • aから 1から kの値が丁度一回ずつ出現する aの連続部分列を、共通区間が存在しないように p個取り出せるとする
  • pとしてありうる最大値

1以上 k以下の整数からなる長さ nの数列 a全ての美しさの総和 \mod 998244353を求めよ。

制約

  • 2\ \le\ k\ \lt\ n\ \le\ 4000
続きを読む

ECR153-E Fast Travel Text Editor

問題

https://codeforces.com/contest/1860/problem/E (2400diff)

文字列 sが与えられる。

s内にカーソルが一つあることを考える。カーソルは文字と文字の間にある。あなたはカーソルに対して以下の操作を行うことができる

  • カーソルを左に動かす
  • カーソルを右に動かす
  • カーソルの左にある文字を l、右にある文字を rとする。 s_{i} = l, s_{i + 1} = rを満たす iを一つ選び、 i文字目と i + 1文字目の間にカーソルを移動する

m個のクエリが与えられる。

  • はじめ f文字目と f + 1文字目の間にカーソルがある。 t文字目と t + 1文字目の間にカーソルを移動するために必要な最小の操作回数を求めよ

制約

  • 2\ \le\ |s|\ \le\ 5\times 10^{4}
  • 1\ \le\ m\ \le\ 5\times 10^{4}
続きを読む

ECR156-E I Wanna be the Team Leader

問題

https://codeforces.com/contest/1886/problem/E (2400diff)

N人のプログラマーがいて、 i人目の耐久力は a_{i}である。

M個のプロジェクトがあって、 i個目のプロジェクトの難易度は b_{i}である。

あなたは、各プロジェクトにプログラマーを割り当てる。以下の条件を全て満たす割当てが存在するか判定し、存在する場合はそのような割当てを一つ求めよ。

制約

  • 1\ \le\ n\ \le\ 2\times 10^{5}
  • 1\ \le\ m\ \le\ 20
  • 1\ \le\ a_{i}, b_{i}\ \le\ 10^{9}
続きを読む

ECR157-F Fancy Arrays

問題

https://codeforces.com/contest/1895/problem/F (diff: 2600)

n, x, kが与えられる。以下の条件を満たす長さ nの非負整数列 aを数え上げよ。

  • x, x + 1, x + 2, \dots, x + k - 1のうち少なくとも一つの要素が少なくとも一回登場する
  • i = 2, 3, \dots, nについて |a_{i} - a_{i - 1}|\ \le\ k

制約

  • 1\ \le\ n, k\ \le\ 10^{9}
  • 0\ \le\ x\ \le\ 40
続きを読む

ECR158-E Compressed Tree

問題文

https://codeforces.com/contest/1901/problem/E (2200diff)

木が与えられる。各頂点 vには整数 a_{v}が書き込まれている。

あなたは木に対して 0回以上以下の操作を行う。

  • 次数が 1以下の頂点を一つ選び、削除する。

全ての操作を終えた後、木が以下のように変化する

  • 全ての次数 2の頂点が削除され、もともとつながっていた両端点が辺で接続される

残った頂点に書き込まれている値の総和(以下スコアと呼ぶ)を最大化せよ

制約

  • 2\ \le\ N\ \le\ 5\times 10^{5}
  • -10^{9}\ \le\ a_{v}\ \le\ 10^{9}
続きを読む

ECR159-F Trees and XOR Queries Again 【xor基底】

問題

https://codeforces.com/contest/1902/problem/F (2400diff)

N頂点からなる木があって、各頂点 vには整数 a_{v}が書き込まれている。

Q個のクエリ (x, y, k)に答えよ

  • 木の x-yパス上の頂点(端点も含む)に書き込まれた整数からなる集合を Xとする。 Xの部分集合 X'であって、 X'の各要素の総xorが kになるようなものが存在するか判定せよ

制約:

  • 2\ \le\ N, Q\ \le\ 2\times 10^{5}
  • 0\ \le\ A_{v}\ \lt\ 2^{20}
  • TL6.5秒
続きを読む

ECR160-E Matrix Problem

問題

https://codeforces.com/contest/1913/problem/E (2400diff)

n行 m列の01行列 aが与えられる。また、長さがそれぞれ n, mの数列 A, Bが与えられる。

あなたの目標は aのいくつかのマスを反転することで、 i行目の 1の数を A_{i}個、 j列目の 1の数を B_{j}にすることである。

目標を達成することが可能なら、反転するマスの最小個数を、不可能ならそのことを報告せよ。

制約

  • 1\ \le\ n, m\ \le\ 50

解法

\sum A = \sum Bが明らかに必要。

最小費用流の問題に帰着させる。各マスに0か1を割り当てることを考える。

  • もともとのマスの値が 0のとき、 0を割り当てるのにコスト 0, 1を割り当てるのにコスト 1
  • もともとのマスの値が 1のとき、「あらかじめ一回操作をして値を 0にした」と考える。 0を割り当てるのにコスト 0, 1を割り当てるのにコスト -1

負コストがあるので、初回のポテンシャル計算にはベルマンフォードを使う。最初ネットワークがDAGなので、dpをしても良い。

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
#include "Src/Graph/Flow/SuccessiveShortestPath.hpp"
using namespace zawa;

int main() {
    SetFastIO();

    int n, m; std::cin >> n >> m;
    std::vector s(n, std::vector<int>(m));
    for (auto& v : s) for (auto& x : v) std::cin >> x;
    std::vector<int> a(n), b(m);
    for (auto& x : a) std::cin >> x;
    for (auto& x : b) std::cin >> x;
    int sum{std::reduce(a.begin(), a.end(), 0)};
    if (sum != std::reduce(b.begin(), b.end(), 0)) {
        std::cout << -1 << '\n';
        return 0;
    }
    SuccessiveShortestPath<int, int> mcf(n + m + 2);
    int source{n + m}, sink{source + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, a[i], 0);
    }
    for (int i{} ; i < m ; i++) {
        mcf.addEdge(n + i, sink, b[i], 0);
    }
    int ans{};
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < m ; j++) {
            if (s[i][j] == 0) {
                mcf.addEdge(i, n + j, 1, 1);
            }
            else if (s[i][j] == 1) {
                ans++;
                mcf.addEdge(i, n + j, 1, -1); 
            }
            else {
                assert(false);
            }
        }
    }
    mcf.dagdp(source, sink);
    mcf.updatePotential();
    int flow{mcf.maxflow(source, sink)};
    assert(flow <= sum);
    if (flow < sum) {
        std::cout << -1 << '\n';
        return 0;
    }
    ans += mcf.minCost();
    std::cout << ans << '\n';
}

自分のMCFはACLより遅いが、ベルマンフォードやDAG上のDPでポテンシャルが計算できるのが強み(自慢)

反省

バチャ中はE問題を開くことが無かった。

自分にとってはDよりEの方が解きやすそうに見えた。

しかし、Dが解けていないなかでEのフローを信じて詰めれたかと言われると、かなり自信が無い。Dを解かないと始まらないな。