Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

えー, レートの変動が大きすぎるだろ.

問題文はとても読みやすいのですき.

ooooo--- 5735pts 90th.

2108->2208(+100).

A. Perfect Squares

問題概要

ある数 ${x}$ について, ${x = y^2}$ となる整数 ${y}$ が存在するとき Perfect Square であると定義する.

長さ ${n(1 \le n \le 1000)}$ の整数列 ${a_1, a_2, \dots, a_n(-10^6 \le a_i \le 10^6)}$ が与えられるので, Perfect Square ではないもののうちの最大値を求めよ.

解法

問題文に書かれている通りに実装をします.

${0}$ 以下の整数の判定や扱いに注意.

ソース

#include<bits/stdc++.h>

using namespace std;

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

int main()
{
  int N;
  cin >> N;
  int ret = -INF;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    bool perfect = false;
    for(int j = 1; j * j <= x; j++) {
      if(j * j == x) perfect = true;
    }
    if(x == 0) perfect = true;

    if(!perfect) {
      ret = max(ret, x);
    }
  }
  cout << ret << endl;
}

B. Conan and Agasa play a Card Game

codeforces.com

問題概要

Conan が先攻, Agasa が後攻で ${n(1 \le n \le 10^5)}$ 枚のカードを使ってゲームをする. カード ${i}$ には値 ${a_i(1 \le a_i \le 10^5)}$ が書かれている.

各ターンでは, 好きなカード ${i}$ を選んでそのカードと, ${a_j \lt a_i}$ を満たす全てのカード ${j}$ を取り除く. この行動ができなくなった最初のプレイヤーが負けである.

両者が最適に行動した時, どちらが勝つか.

解法

えーーーー, これむずかしい.

負けの局面はカードが空のときである. 最後に取り除かれるカードは最大の値を持つカードである. このカードが ${1}$ 枚あるときは勝ちである. もう ${1}$ 枚あるときは負けである.

したがって最大の値が偶数枚のとき先手が負けであるが, それより ${1}$ 個小さい値をとると勝ちにできる可能性がある. これも同様に偶奇によってきまるため, 結局奇数枚の同じ値が書かれたカードがある場合は先手必勝, それ以外は後手必勝ということがわかる.

あと B 問題なのでどうせ偶奇.

ソース

#include<bits/stdc++.h>

using namespace std;

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

int main()
{
  int N;

  cin >> N;
  map< int, int > mp;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    --x;
    mp[x]++;
  }

  for(auto& p : mp) {
    if(p.second % 2 == 1) {
      cout << "Conan" << endl;
      return(0);
    }
  }

  cout << "Agasa" << endl;
}

C. Travelling Salesman and Special Numbers

codeforces.com

問題概要

ある値 ${x}$ がある. この値に対して, その値で 1 が立っている bit 数に書き換える操作を ${1}$ になるまで行う.

この操作回数が ${k(0 \le k \le 1000)}$ 回となるような ${n(1 \le n \lt 10^{1000})}$ 以下の値の個数を ${10^9+7}$ で求めよ.

解法

桁DPする以外なくない？ないね.

まず ${k=0}$ は罠っぽいので別処理することとして, それ以外の処理を考える.

${1}$ 回の操作で値は ${1000}$ bit 以下に減るため, 前処理として ${1000}$ bit 以下の全ての bit 数に対して, その値を ${1}$ にするまでの操作回数を求めておく. 次に桁DP. 状態として 1 の bit 数を持っておく. あとはまあなんか雰囲気で書けるんですが, ${1}$ が立っている bit 数が ${1}$ かつ最初の値が ${1}$ というアの処理にに注意する.

ソース

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1 << 30;

string N;
int K;
int dp[1001][1001][2];
int dp2[1001];


int rec2(int idx)
{
  if(idx == 0) return (INF);
  if(idx == 1) return (0);
  if(~dp2[idx]) return (dp2[idx]);
  auto p = __builtin_popcount(idx);
  return (dp2[idx] = rec2(p) + 1);
}


int rec(int idx, int bit, bool free)
{
  if(idx == N.size()) {
    return (1 + rec2(bit) == K);
  }
  if(~dp[idx][bit][free]) return (dp[idx][bit][free]);
  if(idx + 1 == N.size() && bit == 0) return(0);
  int ret = 0;
  for(int i = free ? 1 : N[idx] - '0'; i >= 0; i--) {
    (ret += rec(idx + 1, bit + i, free | (N[idx] - '0' != i))) %= mod;
  }
  return (dp[idx][bit][free] = ret);
}

int main()
{
  cin >> N >> K;

  if(K == 0) {
    cout << 1 << endl;
    return (0);
  }
  memset(dp2, -1, sizeof(dp2));
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 0, false) << endl;
}

D. Bash and a Tough Math Puzzle

codeforces.com

問題概要

長さ ${n(1 \le n \le 5 \times 10^5)}$ の数列 ${a_1, a_2, \dots, a_n(1 \le a_i \le 10^9)}$ が与えられる.

${q(1 \le q \le 4 \times 10^4)}$ 個のクエリを処理せよ.

区間 ${[l, r]}$ の gcd が, 高々 ${1}$ つの要素を変更することにより ${x}$ にできるか判定する.
${a_i}$ を ${y}$ に更新する.

解法

gcd はセグ木にのせられるので, gcd を持たせるセグ木を使いたくなる.

更新クエリでは普通にセグ木を更新すれば良い. 判定クエリを考える.

要するに, 区間 ${[l, k]}$ が ${x}$ で割り切れて, ${[k + 2, r]}$ も ${x}$ で割り切れるような ${k}$ があるか判定すれば良い. えーこれはセグ木をくだる二分探索をして ${[l, k]}$ について条件を満たす最右の ${k}$ を求めて, ${[k + 2, r]}$ が ${x}$ で割り切れるか判定すれば良い. ${O(\log n)}$ でできるため, できる(できるので).

ソース

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1 << 30;

struct SegNode
{
  int v;

  SegNode(int v) : v(v) {}

  SegNode operator*(const SegNode &r) const
  {
    return (__gcd(v, r.v));
  }
} e(0);

struct SegmentTree
{
  int sz;
  vector< SegNode > seg;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, e);
  }

  void update(int k, const SegNode &x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
    }
  }

  SegNode query(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (e);
    if(a <= l && r <= b) return (seg[k]);
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) * query(a, b, 2 * k + 2, (l + r) >> 1, r));
  }

  SegNode query(int a, int b)
  {
    return (query(a, b, 0, 0, sz));
  }

  void set(int k, SegNode x)
  {
    seg[k + sz - 1] = x;
  }

  void build()
  {
    for(int k = sz - 2; k >= 0; k--) {
      seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
    }
  }

  int lower_bound(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) return (-3);
    if(a <= l && r <= b) {
      if(seg[k].v % x == 0) return (r - 1);
      if(l + 1 == r) return (-2);
    }
    auto latte = lower_bound(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    if(latte == -3) return (lower_bound(a, b, x, 2 * k + 2, (l + r) >> 1, r));
    if(latte == -2) return (-2);
    if(latte + 1 == (l + r) >> 1) {
      auto malta = lower_bound(a, b, x, 2 * k + 2, (l + r) >> 1, r);
      return (malta < 0 ? latte : malta);
    } else {
      return (latte);
    }
  }

  int lower_bound(int a, int b, int x)
  {
    return (lower_bound(a, b, x, 0, 0, sz));
  }

};

int main()
{
  int N, A[500000];
  scanf("%d", &N);
  SegmentTree seg(N);
  for(int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    seg.set(i, x);
  }
  seg.build();
  int Q;
  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    int t;
    scanf("%d", &t);
    if(t == 2) {
      int x, y;
      scanf("%d %d", &x, &y);
      --x;
      seg.update(x, y);
    } else {
      int l, r, x;
      scanf("%d %d %d", &l, &r, &x);
      --l;
      int ok = max(l - 1, seg.lower_bound(l, r, x));
      if(seg.query(ok + 2, r).v % x == 0) puts("YES");
      else puts("NO");
    }
  }
}

E. Palindromes in a Tree

codeforces.com

問題概要

${n(2 \le n \le 2 \times 10^5)}$ の木が与えられる. すべての頂点には a-t のいずれかの文字が割り当てられている.

木のパスのうち, パス内の頂点に書かれた文字を置換して回文にできるとき, そのパスを palindromic と定義する.

それぞれの頂点について, その頂点を通るような palindromic なパスがいくつあるか求めよ.

解法

a-t の文字を bit で表すと, あるパスが palindromic であるとはパス内のすべての頂点と xor をとったときに 1 が立っている bit が高々 1 と等しい.

パスの本数の数え上げなので木の重心分解を考えたくなる.

ある重心を通る全てのパスを数え上げる. 重心から生える部分木のうちある地点の部分木まで処理していて, 重心から処理済みの部分木までの頂点のうちのパスの出現の bit の状態を全て列挙できているとする.

次に新たな部分木に含まれる頂点を DFS で処理する. 部分木内の頂点から重心(正確には重心手前)へのパスの状態と, 既に他の部分木で出現した状態との xor の bitcount が高々 ${1}$ のものすべてが palindromic なパスで, これは 20 回ループを回せば調べることが可能. このパスの本数を重心に戻る過程で通った全ての頂点について足し込む.

既に処理済みの頂点から新たな頂点への palindromic なパスで, 処理済みの頂点から重心へのアが加算できないように見えるが, これは重心から生える辺の順番を反転させて ${2}$ 回試すと網羅できる.

計算量は ${O(n \log n)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

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

int N;
vector< int > g[MAX_N];
int sub[MAX_N];
bool v[MAX_N];
int bit[MAX_N];
int mp[1 << 20], last_update[1 << 20], ween;

int64 all[MAX_N];

int update[MAX_N + 1], ptr = 0;

inline int build_dfs(int idx, int par)
{
  sub[idx] = 1;
  for(auto &to : g[idx]) {
    if(to == par || v[to]) continue;
    sub[idx] += build_dfs(to, idx);
  }
  return (sub[idx]);
}

inline pair< int, int > search_centroid(int idx, int par, const int all)
{
  pair< int, int > ret(INF, -1);
  int connect = all - sub[idx];
  for(auto &to : g[idx]) {
    if(to == par || v[to]) continue;
    ret = min(ret, search_centroid(to, idx, all));
    connect = max(connect, sub[to]);
  }
  return (min(ret, make_pair(connect, idx)));
}

inline void addd(int idx)
{
  if(last_update[idx] == ween) ++mp[idx];
  else mp[idx] = 1, last_update[idx] = ween;
}

inline int acce(int idx)
{
  if(last_update[idx] != ween) return (0);
  return (mp[idx]);
}


inline int64 rec(int idx, int par, int root_connect, int root_disconnect)
{
  root_connect ^= bit[idx];
  update[ptr++] = root_connect;

  root_disconnect ^= bit[idx];
  int64 sum = acce(root_disconnect);
  for(int i = 0; i < 20; i++) {
    sum += acce(root_disconnect ^ (1 << i));
  }

  for(auto &to : g[idx]) {
    if(to == par || v[to]) continue;
    sum += rec(to, idx, root_connect, root_disconnect);
  }
  all[idx] += sum;
  return (sum);
}

inline void beet(int idx)
{
  for(int i = 0; i < 2; reverse(begin(g[idx]), end(g[idx])), i++) {
    ++ween;
    if(i == 0) addd(bit[idx]);
    for(auto &to: g[idx]) {
      if(v[to]) continue;
      ptr = 0;
      auto ret = rec(to, idx, bit[idx], 0);
      if(i == 0) all[idx] += ret;
      for(int j = 0; j < ptr; j++) addd(update[j]);
    }
  }
}

inline void centroid_decomp(int idx)
{
  int centroid = search_centroid(idx, -1, build_dfs(idx, -1)).second;
  beet(centroid);
  v[centroid] = true;
  for(auto &to : g[centroid]) {
    if(v[to]) continue;
    centroid_decomp(to);
  }
}


int main()
{
  scanf("%d", &N);
  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);
  }
  string s;
  cin >> s;
  for(int i = 0; i < N; i++) {
    int c = s[i] - 'a';
    bit[i] = 1 << c;
  }
  memset(last_update, -1, sizeof(last_update));
  centroid_decomp(0);
  for(int i = 0; i < N; i++) {
    printf("%lld ", all[i] + 1);
  }
  puts("");
}

ei1333の日記

ぺこい

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

A. Perfect Squares

問題概要

解法

ソース

B. Conan and Agasa play a Card Game

問題概要

解法

ソース

C. Travelling Salesman and Special Numbers

問題概要

解法

ソース

D. Bash and a Tough Math Puzzle

問題概要

解法

ソース

E. Palindromes in a Tree

問題概要

解法

ソース