okura diary

おもに競技プログラミングの日記

NIKKEI2019-2-QUAL E. Non-triangular Triplets

構築 パズル Yellow ARC

atcoder.jp

考察

  • [K, K + N), [K+N, K + 2N), [K+2N, K + 3N)をそれぞれ A, B, Cとしよう。

  • 実験をして、 a_i + b_i \leq c_iの右辺はすべて Cの要素になるのではないかと思う

  • もし右辺にC以外の要素があるなら、 x + C \leq C, x + x \leq (not C)の形の式があって、1つ目の式の左辺のCと2つ目の式のnot Cを交換しても条件を満たす。 これを繰り返せばすべての式の右辺をCの要素にできる
  • とりあえず必要条件を考えてみる。A,Bの要素の和がCの要素の和より大きい時は明らかに不可能。この条件を整理すると N \geq 2K - 1となる。
  • どうせ十分条件だろうと予想して(パチンコ)実験をしてみる。この条件をギリギリ満たすもので実験するとなにか見えそうなので N = 5, K = 3でやってみる
(7, 10, 17)
(5, 11, 16)
(3, 12, 15)
(6,  8, 14)
(4,  9, 13)
  • Aの方を2ずつ減らして、Bの方を1ずつ増やすことでCのほうを1ずつ減らすとなんかうまくハマりそう。実際に一般のK, Nでこの構築方法をしたときにうまく行くかを不等式評価してみると なんかうまく行く。Nが偶数の場合もほぼ同様にできることがわかる。
感想

序盤の考察ルートは良かった。十分条件っぽいのを見つけてからがただのパズルにしか見えない。(なにか典型構図がある？)

パズルはパチンコなので苦手

Submission

void solve() {
  int n, k;
  cin >> n >> k;
  if (n < 2 * k - 1) {
    cout << -1 << endl;
    return;
  }
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < (n + 1) / 2; i++) {
    a[i] = k + n - 1 - i * 2;
    b[i] = k + n + n / 2 + i;
    c[i] = k + 3 * n - 1 - i;
  }
  for (int i = 0; i < n / 2; i++) {
    a[i + (n + 1) / 2] = k + n - 2 - i * 2;
    b[i + (n + 1) / 2] = k + n + i;
    c[i + (n + 1) / 2] = k + 3 * n - 1 - (n + 1) / 2 - i;
  }
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ' << b[i] << ' ' << c[i] << endl;
  }
  return;
}

Educational Codeforces Round 96

DP bitDP ECR

Dashboard - Educational Codeforces Round 96 (Rated for Div. 2) - Codeforces

F. Realistic Gameplay

区間の始めに余っている弾を捨ててreloadする必要はない。(余っている分を使えばいいので)したがってreloadは区間の終わりに時間の余裕があるときのみ考えればよい。

\displaystyle dp[ i ] := i\mbox{番目の区間の始めに弾が満タンな時、それまでに使う弾の個数の最小値}

とすると状態数 O(N)、遷移 O(N)のDPができる。

Submission

void solve() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> l(n), r(n), a(n);
  for (int i = 0; i < n; i++) cin >> l[i] >> r[i] >> a[i];
  vector<ll> dp(n + 1, LLINF);
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    if (dp[i] == LLINF) continue;
    ll rem = k;
    ll use = 0ll;
    for (int j = i; j <= n; j++) {
      if (j == n) {
        chmin(dp[n], dp[i] + use);
        break;
      }
      if (rem + k * (r[j] - l[j]) < a[j]) break;
      // いくら余るか
      ll tmp = rem + k * (r[j] - l[j]) - a[j];
      if (tmp > 0) tmp = (tmp - 1) % k + 1;
 
      use += a[j];
 
      dmp(i, j, rem, tmp, use);
      // 間で補充
      if (j + 1 < n && r[j] < l[j + 1]) chmin(dp[j + 1], dp[i] + use + tmp);
      // 区間の最後で補充
      if ((a[j] - rem + k - 1) / k < r[j] - l[j])
        chmin(dp[j + 1], dp[i] + use + tmp % k);
 
      rem = tmp;
    }
  }
 
  if (dp[n] == LLINF)
    cout << -1 << endl;
  else
    cout << dp[n] << endl;
 
  return;
}
G. Yet Another DAG Problem

頂点に割り当てる値は頂点数 N以下でよいことに着目する。(これ超本質)

\displaystyle dp[ i ][S] := S\mbox{の頂点に} i \mbox{以下の数を割り当てた時(} \mbox{S以外は0とする)の目的関数の最小値}

とする。愚直にやるならば更新で iを割り当てる頂点集合を全部みて O(3^NN)とかになる。頂点集合 Tに iを割り当てられるかどうかは、 Tから到達可能な頂点全てに i-1以下が割り当てられているかどうかで判定できる。

これでは間に合わないのでグラフがDAGであることを利用する。 iを割り当てる頂点をトポロジカル順序で前のものから順に見ていくことにすれば、トポロジカル順序が後の点が前の点から到達可能であるのにもかかわらず 同時に iが割り当てられるということはない。(前の点が追加された時点で、後の点は前の点から到達可能ならば i-1以下が割り当てられているはず)

よって O(2^NN^2)でこのDPができる。あとは復元すればOK。

Submission

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> c(n, 0);
  Graph g(n);
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    c[a] += w;
    c[b] -= w;
    g.add_edge(a, b);
  }
  auto topo = topological_order(g);
 
  vector<int> reach(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    int v = topo[i];
    for (auto e : g[v]) {
      reach[v] |= (1 << e.to);
      reach[v] |= reach[e.to];
    }
  }
 
  // dp[i][j] := jの頂点に[0, i]を割り当てるときの最小値
  auto dp = vect(n + 1, vect(1 << n, LLINF));
  auto prev = vect(n + 1, vect(1 << n, -1));
  dp[0][0] = 0;
  for (int i = 0; i < n; i++) {
    // iを割り当てる頂点をトポロジカル順に追加
    for (int k = 0; k < n; k++) {
      for (int j = 0; j < (1 << n); j++) {
        if (dp[i][j] == LLINF) continue;
        if (chmin(dp[i + 1][j], dp[i][j])) prev[i + 1][j] = j;
        int v = topo[k];
        if ((j >> v) & 1) continue;
        if ((reach[v] & j) == reach[v]) {
          if (chmin(dp[i][j | (1 << v)], dp[i][j] + c[v] * i))
            prev[i][j | (1 << v)] = prev[i][j];
        }
      }
    }
  }
 
  vector<ll> ans(n, 0);
  int S = (1 << n) - 1;
  int X = n;
  while (X > 0 && S != 0) {
    int T = prev[X][S];
    int U = S ^ T;
    for (int i = 0; i < n; i++) {
      if ((U >> i) & 1) ans[i] = X;
    }
    S = T;
    X--;
  }
  cout << ans << endl;
  return;
}

Educational Codeforces Round 97

DP Aho-Corasick HLD ECR

Dashboard - Educational Codeforces Round 97 (Rated for Div. 2) - Codeforces

E: Make It Increasing

列を区切ってLISすればOK

Submission

F: Emotional Fishermen

順列の数え上げだし挿入DPだろうと決め打って考えたが解けなかった。この問題はよくある挿入DPのようにソートして昇順or降順に要素を埋めながら列を構成するというよりは、前から順に好きな要素で埋めていくという方法がうまくいく。

\displaystyle dp[ i + 1 ][j] := i\mbox{番目までの順列で、最大値が}a_j

として最大値が更新される場合とそうでない場合の遷移を考える。累積和を使って高速化すると O(N^2)

Submission

G Death DBMS

明らかにAho-Corasickを使ってくれという感じの問題なので使う。するとSuffix Linkからなる木上で、各頂点から根までの最大値を求めるクエリにたくさん答えたくなるのでHLDで殴った。 Editorialで賢い方法が紹介されていた。文字列集合が重複なしであるとすると、Aho-Corasick automatonのあるstateにマッチしうる文字列(suffix linkを辿っていってマッチするもの)の種類数は O(\sqrt{\mbox{文字列の長さの和}})で抑えられる。なぜかというと各長さの文字列についてマッチしうるのは高々一つなので、 1+2+...+k \leq \mbox{長さの和}となるからである。なので木をexit linkで愚直に根まで辿っていっても O(Q\sqrt{N})程度で通る。

Submission

JAG 模擬国内2020 H 辺が先か，頂点が先か (AOJ 3208 Edge or Vertex)

LP 双対 ICPC AOJ

問題文 : Aizu Online Judge

LPの定式化から2つのアプローチができて面白かったのでそれについて説明する。

考察1

先手が初めに各辺e \in Eに確率p_eを割り振り、後手はそれに応じてv \in Vを確率q_vで選ぶとする。値 X = \sum_{e=(u,v)\in E} p_e(q_u - q_v) を先手は最大化、後手は最小化する時、Xの値はいくらかという問題になる。 まず後手はあるpure strategy(ある選択肢を確立1で選ぶ)が最適になる。すなわち、先手の戦略pに対し、各頂点vごとに\sum_{e \in \delta_-(v)}p_e - \sum_{e \in \delta_+(v)}p_eを計算し、これが最小となる頂点を確立1で選ぶのが後手の最適な戦略である。この考察を踏まえると、次のようにLPで定式化できる。

maximize : min_{v \in V} \sum_{e \in \delta_-(v)}p_e - \sum_{e \in \delta_+(v)}p_e \\ s.t. \\ p_e \geq 0 \\ \sum p_e = 1

考察2

与えられるグラフに閉路が存在する場合、pは閉路の辺に均等に確率を割り振ればXの値を0にできる。また、後手はすべての頂点に均等に確立を割り振る戦略でXの値を必ず0以下にできる。 よって、グラフに閉路が存在するなら、解は0が言える。

そうでないとき、\sum_{e \in \delta_-(v)}p_e - \sum_{e \in \delta_+(v)}p_eが負になる頂点が少なくとも１つは存在する。よってDAGの時、解は負の数が言える。

LP解法1

考察1での定式化では、maximizeの対象にminが入っており扱いづらい。こういう際の常套手段として新しい変数を加えminを不等式制約で表現するというのがある。それを行うと、

maximize : S \\ s.t. \\ p_e \geq 0 \\ \sum p_e = 1\\ S \leq \sum_{e \in \delta_-(v)}p_e - \sum_{e \in \delta_+(v)}p_e (\forall v \in V)

自分はここで詰まってしまった。双対とっても綺麗になりそうもないし(もしかしたらなるかもしれませんが)いかんせん \sum p_e = 1の制約が邪魔で変形や解釈が難しかった。

ここ(Lesson 35: Game Theory and Linear Programming)のスライドを眺めてみると、Sの符号がわかっているときは(より一般にmatrix gameでできる)いい感じの変形があるということがわかった。今回の場合、考察2からDAGで解が負になる場合だけを考えればよいためこの変形が利用できる。 具体的には x_e = p_e / |S|とおくと、

maximize : S \\ s.t. \\ x_e \geq 0 \\ \sum x_e = 1 / |S|\\ -1 \leq \sum_{e \in \delta_-(v)}x_e - \sum_{e \in \delta_+(v)}x_e (\forall v \in V)

となるが、よく見るとSが消去できることがわかる。よって問題は

maximize : \sum x_e \\ s.t. \\ x_e \geq 0 \\ \sum_{e \in \delta_+(v)}x_e - \sum_{e \in \delta_-(v)}x_e \leq 1(\forall v \in V)

となる。これは「各頂点を始点とするパスの長さの合計を最大化」するグラフの問題と解釈でき、今回グラフはDAGなので各頂点までの最長パスはDPで簡単に求まるので解けた。 (解説にはラグランジュ双対を取ると書いてあるけど和が1の制約とかが邪魔でどうやったら取れるのかわからない...誰か教えてください)

LP解法2

LPで定式化した際に現れる\sum_{e \in \delta_-(v)}p_e - \sum_{e \in \delta_+(v)}p_eという式は各頂点への相対流入量を表しているので、 p_eをただの辺に割り振られた確率とみるのではなくフローとみなすことが有効かもしれないことがわかる。すなわち、「各頂点の相対流入量がS以上ですべての辺の合計流量が1となるようなフローが存在するSの最大値をもとめる」問題だと解釈できる。ここでそのようなフローが存在するかどうかはSに関して単調であるので、二分探索をすることにすると次の問題を解きたくなる。

maximize : \sum p_e \\ s.t. \\ p_e \geq 0\\ \sum_{e \in \delta_-(v)}x_e - \sum_{e \in \delta_+(v)}x_e \geq S (\forall v \in V)

双対をとると

minimize : -S(\sum q_v) \\ s.t. \\ q_v \geq 0\\ q_u - q_v \geq 1 ((u,v) \in E)

となり、実はSは無関係で二分探索が必要ないことがわかる。答えはこの問題の最適解での -\dfrac{1}{\sum q_v}となる。(合計流量を1以上にできる境目を見つけたいので) そして上の問題はいわゆる牛ゲー(差分制約による最短(長)経路問題のポテンシャルの最大(小)化)に近い形であり、各頂点からの最長路の長さの和が最適値であることがわかる。よって解けた。

提出

Aizu Online Judge

bool solve() {
  int N, M;
  cin >> N >> M;
  if (N == 0 && M == 0) return false;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
  }
  vector<int> vs;
  vector<bool> used(N, false);
  vector<int> ord(N);
  function<void(int)> dfs = [&](int v) {
    used[v] = true;
    for (int u : g[v]) {
      if (!used[u]) dfs(u);
    }
    vs.push_back(v);
  };
  for (int i = 0; i < N; i++) {
    if (!used[i]) dfs(i);
  }
  reverse(all(vs));
  for (int i = 0; i < vs.size(); i++) { ord[vs[i]] = i; }
  for (int i = 0; i < N; i++) {
    for (int j : g[i]) {
      if (ord[i] > ord[j]) {
        cout << 0 << endl;
        return true;
      }
    }
  }
  vector<int> dp(N, 0);
  for (int i = N - 1; i >= 0; i--) {
    int v = vs[i];
    for (int u : g[v]) { chmax(dp[v], dp[u] + 1); }
  }
  cout << setprecision(30) << -1.0 / (long double)(accumulate(all(dp), 0))
       << endl;
  return true;
}

Codeforces Round #591 D. Stack Exterminable Arrays

CFR
問題

https://codeforces.com/contest/1240/problem/D

解法

解説を見た。

各indexについてそこから順にstackに入れていった時に初めて空になるindex nxt[i]が欲しくなる(これが分かればあとはdpで数えるだけ)。 しかし直接nxtを求めるには少し情報が足りないので補助的に次の配列を考える

nxtX[i][x] := a[i]...a[j]が空になって、かつa[j+1] = xであるような最小のj>i

これを必要なところだけHashMapで持って更新していけばOK。nxtXの更新はコピーが発生しないようにswapなりmoveを使うことに注意すればO(n)でnxt,nxtXを求められる。

a[0]...a[i]をスタックに入れた状態を文字列と見てハッシュにして同じ状態のペアを数える方法もあるみたい。こっちのほうが思考停止で書けるかも。

参考: Codeforces Round #591 Div2 F / Div1 D. Stack Exterminable Arrays • knshnbのブログ

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  vector<int> nxt(n + 1, -1);
  vector<unordered_map<int, int>> nxtX(n + 1);
  vector<ll> cnt(n + 1, 0ll);
  ll ans = 0ll;
  for (int i = n - 1; i >= 0; i--) {
    if (i + 1 < n && a[i] == a[i + 1])
      nxt[i] = i + 1;
    else if (nxtX[i + 1].find(a[i]) != nxtX[i + 1].end())
      nxt[i] = nxtX[i + 1][a[i]] + 1;

    if (nxt[i] != -1) swap(nxtX[i], nxtX[nxt[i] + 1]);
    if (nxt[i] != -1 && nxt[i] + 1 < n) nxtX[i][a[nxt[i] + 1]] = nxt[i];
    if (nxt[i] != -1) cnt[i] = 1 + cnt[nxt[i] + 1];
    ans += cnt[i];
  }
  cout << ans << endl;
  return;
}