ei1333の日記

ぺこい

Educational Codeforces Round 55 (Rated for Div. 2)

ねねー

E. Increasing Frequency

codeforces.com

問題概要

長さ  {N} の数列  {a_i} が与えられる.

数列のある連続区間を選んで、好きな値を一様加算する操作を一度だけおこなえる.

 {c} の出現回数の最大値を求めよ.

解法

選ぶべき連続区間の両端の値は同じ値であるという考察をすると実家に帰着できる.

もともとの値  {c} の出現回数を all とする.

どの値を両端の値にするかをすべて試す. その値が出現したindexを列挙し, これを  {k_1, k_2, ..., k_m} とする.

max {(j-i+1)+(all-区間  {[k_i,k_j]} の値  {c} の出現回数)} を求めたい.

 {f_i := } 区間  {[0,i)} の値  {c} の出現回数とすると, max {(j-i+1)+(all-( {f_{k_j+1}} -  {f_{k_i}})} となる.

整理すると, max {(j- {f_{k_j}})+(1-i+all+ {f_{k_i}})} となり  {j} {i} を分けて書くことができて, 終わる.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

int main() {
  int N, C, A[500000];
  scanf("%d %d", &N, &C);
  for(int i = 0; i < N; i++) scanf("%d", &A[i]);

  map< int, vector< int > > appear;
  vector< int64 > Csum(N + 1);
  for(int i = 0; i < N; i++) {
    appear[A[i]].push_back(i);
    Csum[i + 1] = Csum[i] + (A[i] == C);
  }


  int64 ret = Csum[N];

  for(auto &p : appear) {
    auto &vs = p.second;
    vector< int64 > tap(vs.size());
    for(int i = 0; i < vs.size(); i++) tap[i] = i - Csum[vs[i] + 1];
    for(int i = (int)vs.size() - 2; i >= 0; i--) tap[i] = max(tap[i], tap[i + 1]);
    for(int i = 0; i < vs.size(); i++) {
      int64 add = Csum[vs[i]] - i + 1 + Csum[N];
      int64 uku = tap[i];
      ret = max(ret, uku + add);
    }
  }

  cout << ret << endl;
}

F. Speed Dial

codeforces.com

問題概要

 {n(1 \le n \le 500)} 個の電話番号  {s_i(\sum_{i=1}^{n} |s_i| \leq 500)} と入力回数  {m_i(1 \le m_i \le 500)} が与えられる.

 {k(1 \le k \le 10)} 個のショートカットキーを最初に定義する. これらのいずれかを押すことで電話番号のprefixの入力を省略できる.

このとき番号キー(ショートカットキーは数えない)を押す回数の最小値を求めよ.

解法

えーこのDPはむずかしくないか. アイデアとしては祖先を持つ.

ショートカットキーでprefixを最大何個とれるかを求めれば, 全体からそれをひけば解.

まず Trie を構築する. 次に木DPをする.

dp[idx][rest][k]:= (idxの祖先のうち)最後にノードkでショートカットキーを使っていて、ノードidxの部分木でショートカットキーをrest回使った時の最大個数

遷移としては、そのノードでショートカットキーを使うか使わないかの2通りを試す.

使うときは、restのうち1個消費して (dep[idx]-dep[k]) * idxの個数 をとって、dp[to][*][idx] たちとマージする.

使わないときは、dp[to][*][k] たちとマージする.

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 30;

struct Node {
  int weight, dep;
  vector< int > ch;

  Node(int dep) : weight(0), dep(dep), ch(10, -1) {}
};

vector< Node > nodes;
int dp1[501][11][501];

void chmax(int &a, int b) { a = max(a, b); }

int rec(int idx, int rest, int k) { // k: 最後に使ったところ
  if(rest == 0) return 0;
  if(~dp1[idx][rest][k]) return dp1[idx][rest][k];

  vector< int > child;
  for(auto &to : nodes[idx].ch) {
    if(~to) child.push_back(to);
  }


  int ret = 0;
  vector< int > dp2(rest + 1);
  for(auto &to : child) {
    vector< int > dp3(rest + 1);
    for(int j = 0; j <= rest; j++) {
      for(int l = 0; j + l <= rest; l++) {
        chmax(dp3[j + l], dp2[j] + rec(to, l, k));
      }
    }
    dp2.swap(dp3);
  }
  chmax(ret, dp2[rest]);

  dp2.assign(rest + 1, 0);
  for(auto &to : child) {
    vector< int > dp3(rest + 1);
    for(int j = 0; j <= rest; j++) {
      for(int l = 0; j + l <= rest; l++) {
        chmax(dp3[j + l], dp2[j] + rec(to, l, idx));
      }
    }
    dp2.swap(dp3);
  }

  chmax(ret, dp2[rest - 1] + (nodes[idx].dep - nodes[k].dep) * nodes[idx].weight);

  return dp1[idx][rest][k] = ret;
}


int main() {
  int N, K;
  cin >> N >> K;
  nodes.emplace_back(Node(0));
  int all = 0;
  for(int i = 0; i < N; i++) {
    string s;
    int m;
    cin >> s >> m;
    all += s.size() * m;
    int curr = 0, dep = 1;
    for(auto &c : s) {
      int &nxt = nodes[curr].ch[c - '0'];
      if(nxt < 0) {
        nxt = (int) nodes.size();
        nodes.emplace_back(Node(dep));
      }
      curr = nxt;
      nodes[curr].weight += m;
      ++dep;
    }
  }
  memset(dp1, -1, sizeof(dp1));
  cout << all - rec(0, K, 0) << endl;
}

G. Petya and Graph

codeforces.com

問題概要

 {n(1 \le n \le 10^3} 頂点  {m(0 \le m \le 10^3)} 辺の単純グラフが与えられる。それぞれの頂点と辺には重み  {a_i, w_i} が割り当てられている.

部分グラフの重みを(辺の重みの和)-(頂点の重みの和) と定義する. 部分グラフをうまく取ったとき, 最大重みを求めよ.

解法

めっちゃフローぽい. もやすうめるっぽい.

それぞれのグラフの頂点に対して  {1} が割り当てられた時に部分グラフに使用する,  {0} が割り当てられた時に使用しないと定義する.

  • 頂点  {i} {1} のとき罰金  {a_i}
  • 頂点  {v_i, u_i} がともに  {1} のとき報酬  {w_i}

できる

ソース

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

template< typename flow_t >
struct Dinic {
  const flow_t INF;

  struct edge {
    int to;
    flow_t cap;
    int rev;
    bool isrev;
  };

  vector< vector< edge > > graph;
  vector< int > min_cost, iter;

  Dinic(int V) : INF(numeric_limits< flow_t >::max()), graph(V) {}

  void add_edge(int from, int to, flow_t cap) {
    graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false});
    graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true});
  }

  bool bfs(int s, int t) {
    min_cost.assign(graph.size(), -1);
    queue< int > que;
    min_cost[s] = 0;
    que.push(s);
    while(!que.empty() && min_cost[t] == -1) {
      int p = que.front();
      que.pop();
      for(auto &e : graph[p]) {
        if(e.cap > 0 && min_cost[e.to] == -1) {
          min_cost[e.to] = min_cost[p] + 1;
          que.push(e.to);
        }
      }
    }
    return min_cost[t] != -1;
  }

  flow_t dfs(int idx, const int t, flow_t flow) {
    if(idx == t) return flow;
    for(int &i = iter[idx]; i < graph[idx].size(); i++) {
      edge &e = graph[idx][i];
      if(e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
        flow_t d = dfs(e.to, t, min(flow, e.cap));
        if(d > 0) {
          e.cap -= d;
          graph[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

  flow_t max_flow(int s, int t) {
    flow_t flow = 0;
    while(bfs(s, t)) {
      iter.assign(graph.size(), 0);
      flow_t f = 0;
      while((f = dfs(s, t, INF)) > 0) flow += f;
    }
    return flow;
  }

  void output() {
    for(int i = 0; i < graph.size(); i++) {
      for(auto &e : graph[i]) {
        if(e.isrev) continue;
        auto &rev_e = graph[e.to][e.rev];
        cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
      }
    }
  }
};

using int64 = long long;

int main() {
  int N, M, A[1000];
  cin >> N >> M;
  Dinic< int64 > flow(N + M + 2);
  int S = N + M, T = N + M + 1;
  int64 re