ei1333の日記

ぺこい

Codeforces Round #525 (Div. 2)

ねねねー

C. Ehab and a 2-operation task

codeforces.com

問題概要

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

以下の 2 種類の操作を最大 {n+1} 回できる.

  • prefix {i} 個に対して {x} を加算する
  • prefix {i} 個に対して {x} で割った余りに置き換える

狭義単調増加列にする操作例を求めよ.

解法

mod をとる操作が強力そう.

とりあえず N 種類の値がほしいので, 最後に mod N をとる操作をすることにする. すると最終的な目標は {0, 1, 2, \cdots, n-1}.

add して mod N の余りが目標になるように調節したい. 🐮ろから決めていくとできるため.

ソース

出力形式を間違えがち

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
  int N, A[100000];
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  int64 preadd = 0;
  cout << N + 1 << endl;
  for(int i = N - 1; i >= 0; i--) {
    int64 mod = ((N + i) - ((A[i] + preadd) % N)) % N;
    if(mod == 0) mod += N;
    cout << "1 " << i + 1 << " " << mod << endl;
    (preadd += mod) %= N;
  }
  cout << "2 " << N << " " << N << endl;
}

D. Ehab and another another xor problem

codeforces.com

問題概要

This is an interactive problem! じゃあないんだよね

30bit以下の整数ペア {(a,b)} を当てるためにクエリ {(c,d)} を最大62回投げることができる.

クエリに対する答えは次の3種類

  • a xor c > b xor d のとき 1
  • a xor c = b xor d のとき 0
  • a xor c < b xor d のとき -1

{(a,b)} をあててね

解法

上から決めるとよさそう.

最初に {(c,d)=(0,0)} とすれば {(a,b)} の大小関係がわかる.

この結果 a>b を仮定する(a<bは反転させて同じ問題を解けば良い).

最上位bitを特定したい. とりあえず c の最上位bitを 1 に変化させてみて, クエリ {(c,d)} を投げてみる. この結果で場合分け.

a', b' をそれぞれ最上位bitを取り除いた a, b とする. (結果が0のときは面倒なので考えてません(サンプル合わせただけ(えぇ...

  • 結果が -1 のとき

変化させたら大小関係が変化したことを意味する.

a: {1a'}, b: {0b'} で a'<b' の場合

a: {1a'}, b: {1b'} で a'>b' の場合

aの最上位bitが1であることは確定. bの最上位bitを求めるたにもう1クエリ投げればよい.

  • 結果が 1 のとき

変化させても大小関係が変化しなかったことを意味する.

あり得るのは

a: {1a'}, b: {0b'} で a'>b' の場合

a: {0a'}, b: {0b'} で a'>b' の場合

bの最上位bitが0であることは確定. aの最上位bitを求めるたにもう1クエリ投げればよい.

これは再帰的に1bit小さい問題にできるのでとける.

ソース

にがて

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int ask(int c, int d) {
  cout << "? " << c << " " << d << endl;
  int k;
  cin >> k;
  return k;
}

void dfs(int p, int bit, int c, int d) {

  if(bit == -1) {
    cout << "! " << c << " " << d << endl;
    return;
  }

  if(p) {
    int cc = c | (1 << bit);
    int dd = d;

    int pp = ask(cc, dd);

    if(pp <= 0) {
      int qq = ask(cc, dd ^ (1 << bit));
      if(qq >= 0) {
        dd |= 1 << bit;
        dfs(true, bit - 1, cc, dd);
      } else {
        dfs(false, bit - 1, cc, dd);
      }
    } else {
      int qq = ask(cc ^ (1 << bit), dd | (1 << bit));
      if(qq > 0) {
        dfs(true, bit - 1, cc, dd);
      } else {
        dfs(true, bit - 1, cc ^ (1 << bit), dd);
      }
    }

  } else {

    int cc = c;
    int dd = d | (1 << bit);

    int pp = ask(cc, dd) * -1;

    if(pp == 0) {
      dfs(false, bit - 1, cc, dd);
    } else if(pp == -1) {
      int qq = ask(cc ^ (1 << bit), dd) * -1;
      if(qq >= 0) {
        cc |= 1 << bit;
        dfs(false, bit - 1, cc, dd);
      } else {
        dfs(true, bit - 1, cc, dd);
      }
    } else {
      int qq = ask(cc | (1 << bit), dd ^ (1 << bit)) * -1;
      if(qq > 0) {
        dfs(false, bit - 1, cc, dd);
      } else {
        dfs(false, bit - 1, cc, dd ^ (1 << bit));
      }
    }
  }
}
int main() {
  dfs(ask(0, 0) >= 0, 29, 0, 0);
}

E. Ehab and a component choosing problem

codeforces.com

問題概要

{n} 頂点の木が与えられる. 頂点 {i} には値 {a_{i}} が書かれている.

{k} 個の互いに素な連結成分をとってきたとき、連結成分の頂点の値の和/k の最大値(既約分数にはしない)を求めよ.

そのようなものが複数あるとき, kを最大となるような分数を求めよ.

解法

頂点に書かれている値が全て 0 以下のとき、最大の値が書かれた頂点を1個ずつ取ってくるのが最適(kが最大化される).

それ以外を考える. つまり 1 以上の値が書かれた頂点が 1 個以上存在する.

とってくる連結成分の、それぞれの連結成分に含まれる頂点の値の和はすべて等しいことがわかる(等しくないと大きい方の連結成分だけを選んだほうが大きくなるので).

とりあえず連結成分の頂点の値の和の最大値はかんたんな木DPで求まる.

この最大値となる連結成分が最大で何個あるかを求めたい. これは, これしかないだろうなあという気持ちになるとコードが生えるので, それを実装するとサンプルがあうので提出する.

ソース

#include <bits/stdc++.h>

using namespace std;

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

int N, A[300000];
vector< int > g[300000];
int64 ask, beet;

int64 rec(int idx, int par) {
  int64 ret = A[idx];
  for(auto &to : g[idx]) {
    if(to == par) continue;
    ret += max(0LL, rec(to, idx));
  }
  ask = max(ask, ret);
  return ret;
}

int64 rec2(int idx, int par) {
  int64 ret = A[idx];
  for(auto& to : g[idx]) {
    if(to == par) continue;
    ret += max(0LL, rec2(to, idx));
  }
  if(ret == ask) {
    ++beet;
    ret = 0;
  }
  return ret;
}

int main() {
  scanf("%d", &N);
  bool f = false;
  int small = -INF;
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    f |= A[i] > 0;
    small = max(small, A[i]);
  }
  for(int i = 1; i < N; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }


  if(!f) {
    int sum = 0;
    for(int i = 0; i < N; i++) {
      sum += A[i] == small;
    }
    cout << 1LL*small*sum << " " << sum << endl;
    return 0;
  }

  rec(0, -1);
  assert(ask > 0);

  rec2(0, -1);
  cout << 1LL*ask*beet << " " << beet << endl;
}