World CodeSprint 10 - ei1333の日記

つらいなぁ…..

F 思いつければというところだけど, 仕方ないね.

Reward Points

www.hackerrank.com

解法

忘れた. 問題文を読んでいない気がする. サンプル読んで適当に合わせただけ.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int A[3];
  for(int i = 0; i < 3; i++) cin >> A[i];
  int ret = 0;
  for(int i = 0; i < 3; i++) {
    ret += min(100, A[i] * 10);
  }
  cout << ret << endl;
}

Zigzag Array

www.hackerrank.com

解法

大小大小… か小大小大… の ${2}$ 通りしかないので, 適当に試す.

結構難しい.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[100];

  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];

  int latte = A[0], malta = 0;
  bool zigzag = false;
  for(int i = 0; i < N; i++) {
    if(zigzag) {
      if(latte < A[i]) latte = max(latte, A[i]), ++malta;
      else latte = A[i], zigzag ^= 1;
    } else {
      if(latte > A[i]) latte = min(latte, A[i]), ++malta;
      else latte = A[i], zigzag ^= 1;
    }
  }

  int beet = 0;
  zigzag = true;
  latte = A[0];
  for(int i = 0; i < N; i++) {
    if(zigzag) {
      if(latte < A[i]) latte = max(latte, A[i]), ++beet;
      else latte = A[i], zigzag ^= 1;
    } else {
      if(latte > A[i]) latte = min(latte, A[i]), ++beet;
      else latte = A[i], zigzag ^= 1;
    }
  }
  cout << min(beet, malta) << endl;
}

Maximal AND Subsequences

www.hackerrank.com

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${a_i(1 \le a_i \le 10^{18})}$ が与えられる.

長さ ${k(1 \le k \le n)}$ の subsequence のうち, bitごとの論理積の最大値と, その選び方の組み合わせを求めよ.

解法

なるべく上位 bit を ${1}$ にしたい気持ち.

今 ${i}$ 桁目を見ているとする. ${i}$ 桁目が ${1}$ の要素の個数が ${k}$ 個以上なら, その bit を ${1}$ にできて, 満たなければ ${1}$ にできない.

${i}$ 桁目を ${1}$ にしたときには, ${0}$ の要素は使えないので候補から除外していく.

最大値はそれを繰り返して求まる.

その選び方は, 最終的に残った要素での組み合わせなので適当にはい.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

inline int64 modCombination(int p, int q)
{
  static int64 fact[202020], rfact[202020];
  if(fact[0] == 0) {
    fact[0] = rfact[0] = 1;
    for(int i = 1; i < 102020; i++) {
      fact[i] = fact[i - 1] * i % mod;
      rfact[i] = modInv(fact[i]);
    }
  }
  if(q < 0 || p < q) return (0);
  return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
}


int main()
{
  int K, N;
  int64 A[100000];

  cin >> N >> K;
  for(int i = 0; i < N; i++) cin >> A[i];

  vector< int > alive(N);
  iota(begin(alive), end(alive), 0);
  int64 val = 0;
  for(int64 i = 60; i >= 0; i--) {
    vector< int > next_alive;
    int bitcount = 0;
    for(int j : alive) bitcount += (A[j] >> i) & 1;
    val |= (int64) (bitcount >= K) << i;
    for(int j : alive) {
      if(bitcount < K || (bitcount >= K && (A[j] >> i) & 1)) {
        next_alive.push_back(j);
      }
    }
    swap(alive, next_alive);
  }

  cout << val << endl;
  cout << modCombination(alive.size(), K) << endl;
}

Permutation Happiness

www.hackerrank.com

問題概要

ある要素について, どちらかの隣接要素が自分の値より高ければ happy と定義する.

以下の ${q(1 \le q \le 100)}$ 個のクエリすべてに答えよ.

長さ ${n(1 \le n \le 3000)}$ の順列で, happy の個数が ${k}$ 個以上ある数列の組み合わせを ${10^9 + 7}$ で割った余りで求めよ.

解法

これ異常難易度で, ${n}$ 時間費やしたんだけどそんなことないですか… ないですね.

happy の個数を数えるのは大変そうなので, unhappy のものについて考えると, これは左右どちらの要素の値よりも大きいものである.

簡単のため, 数列の両端は除いて考える.

unhappy の要素が ${k}$ 個あって長さ ${n}$ の数列に, 値 ${n + 1}$ を ${1}$ 個挿入することを考える(一般に挿入DPと言われていそう).

unhappy の隣接位置に値を加えると, unhappy の個数は ${k}$ 個のまま. 隣接以外の位置に加えると, unhappy の個数は ${1}$ 個増えて ${k + 1}$ となる.

基本的にはこれで ${O(n^2)}$ の dp ができるのだが数列の両端がヤバヤバ.

気合いで.

ソース

これつらいよなぁ.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 mod = 1e9 + 7;

int64 dp[2][2][3001];
int64 fat[3001][3001];

int main()
{
  dp[0][0][1] = 2;
  dp[1][1][2] = 2;
  dp[0][1][1] = 1;
  dp[1][0][1] = 1;
  for(int i = 0; i < 3000; i++) {

    for(int j = 1; j <= 3000; j++) {
      fat[i][j] += dp[0][0][j];
      fat[i][j] += dp[1][1][j];
      fat[i][j] += dp[0][1][j];
      fat[i][j] += dp[1][0][j];
      fat[i][j] += fat[i][j - 1];
      fat[i][j] %= mod;
    }

    int64 dp2[2][2][3001] = {{{}}};
    int width = i + 3;
    for(int j = 2999; j >= 0; j--) {
      int sub = width + 1;

      // {0, 0} -->
      dp2[0][0][j] += dp[0][0][j] * j * 2;
      dp2[0][0][j + 1] += dp[0][0][j] * (sub - j * 2 - 2);
      dp2[0][1][j + 1] += dp[0][0][j];
      dp2[1][0][j + 1] += dp[0][0][j];

      // {1, 1} -->
      dp2[1][0][j] += dp[1][1][j];
      dp2[0][1][j] += dp[1][1][j];
      dp2[1][1][j] += dp[1][1][j] * ((j - 2) * 2 + 2);
      dp2[1][1][j + 1] += dp[1][1][j] * (sub - (j - 2) * 2 - 4);

      // {1, 0} -->
      dp2[1][0][j] += dp[1][0][j] * ((j - 1) * 2 + 1);
      dp2[1][0][j + 1] += dp[1][0][j] * (sub - ((j - 1) * 2 + 1) - 2);
      dp2[1][1][j + 1] += dp[1][0][j];
      dp2[0][0][j] += dp[1][0][j];

      // {0,1} -->
      dp2[0][1][j] += dp[0][1][j] * ((j - 1) * 2 + 1);
      dp2[0][1][j + 1] += dp[0][1][j] * (sub - ((j - 1) * 2 + 1) - 2);
      dp2[1][1][j + 1] += dp[0][1][j];
      dp2[0][0][j] += dp[0][1][j];
    }

    for(int k = 0; k < 2; k++) {
      for(int l = 0; l < 2; l++) {
        for(int j = 3000; j >= 0; j--) {
          dp2[k][l][j] %= mod;
        }
      }
    }
    swap(dp, dp2);
  }


  int Q;
  cin >> Q;

  while(Q--) {
    int N, K;
    cin >> N >> K;

    if(N == 1) {
      cout << 0 << endl;
      continue;
    } else if(N == 2) {
      if(K == 1) cout << 2 << endl;
      else cout << 0 << endl;
      continue;
    }
    int sz = N - K;
    N -= 3;
    cout << fat[N][sz] << endl;
  }
}

Maximum Disjoint Subtree Product

www.hackerrank.com

問題概要

${n(3 \le n \le 3 \times 10^5)}$ 頂点の木があって, それぞれの頂点には値 ${w_i(-10^3 \le w_i \le 10^3)}$ が書かれている.

互いに素な ${2}$ つの連結成分 ${T_a, T_b}$ を取り出せる.

${T_a}$ 内の頂点の値の和 × ${T_b}$ 内の頂点の値の和の最大値を求めよ.

解法

†全方位木DP†

${1}$ 回目のDFSで, 部分木内の連結成分のうちの頂点和の最小値と最大値を求める.

また, 部分木のrootを含む連結成分のうちの頂点和の最小値と最大値も求めておく.

${2}$ 回目のDFSで, 根を変えながらアレをする(語彙力がないね) 例のアレをする.

ソース

実家のような安心感(全方位木DP好きなので).

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1 << 58;

int64 N, W[500000];
vector< int > g[500000];
int64 sub_small[500000], sub_large[500000];
int64 con_small[500000], con_large[500000];

void dfs(int idx, int par = -1)
{
  sub_small[idx] = sub_large[idx] = con_small[idx] = con_large[idx] = W[idx];
  for(auto &to : g[idx]) {
    if(par == to) continue;
    dfs(to, idx);
    if(con_small[to] < 0) con_small[idx] += con_small[to];
    if(con_large[to] > 0) con_large[idx] += con_large[to];
    sub_small[idx] = min(sub_small[idx], sub_small[to]);
    sub_large[idx] = max(sub_large[idx], sub_large[to]);
  }
  sub_small[idx] = min(sub_small[idx], con_small[idx]);
  sub_large[idx] = max(sub_large[idx], con_large[idx]);
}

int64 dfs2(int idx, int64 par_small, int64 par_large, int64 bee_small, int64 bee_large, int par = -1)
{
  int64 ret = -INF;
  if(par_small < 0) con_small[idx] += par_small;
  if(par_large > 0) con_large[idx] += par_large;
  vector< pair< int64, int > > ps, qs;
  for(auto &to : g[idx]) {
    if(to == par) {
      ps.emplace_back(bee_small, to);
      qs.emplace_back(bee_large, to);
    } else {
      ps.emplace_back(sub_small[to], to);
      qs.emplace_back(sub_large[to], to);
    }
  }
  sort(ps.begin(), ps.end());
  sort(qs.rbegin(), qs.rend());

  for(auto &to : g[idx]) {
    if(to == par) continue;
    int64 ch_small = con_small[idx], ch_large = con_large[idx];
    if(con_small[to] < 0) ch_small -= con_small[to];
    if(con_large[to] > 0) ch_large -= con_large[to];
    int64 ll_small = min(ch_small, ps[to == ps[0].second].first);
    int64 ll_large = max(ch_large, qs[to == qs[0].second].first);
    ret = max(ret, dfs2(to, ch_small, ch_large, ll_small, ll_large, idx));
    ret = max(ret, ll_small * sub_small[to]);
    ret = max(ret, ll_large * sub_large[to]);
  }
  return (ret);
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> W[i];
  }
  for(int i = 0; i < N - 1; i++) {
    int U, V;
    cin >> U >> V;
    --U, --V;
    g[U].push_back(V);
    g[V].push_back(U);
  }
  dfs(0);
  cout << dfs2(0, 0, 0, 0, 0) << endl;
}

Node-Point Mappings

問題概要

${n(1 \le n \le 1000)}$ 頂点の木と, 2次元平面上の ${n}$ 個の点集合 ${(x_i, y_i)}$ が与えられる.

木のノードと点を ${1}$ つずつマッピングしていく.

ノード間に辺があるなら, 座標平面上でその点間に線分を引く.

適切にマッピングすることにより, 線分交差がないようにせよ.

解法

よくわからないけど, どの点に頂点 ${1}$ を割り当てても, 線分交差しない割り当て方は必ず存在する.

頂点 ${1}$ を根とする根付き木とする.

1 回目の dfs で, それぞれの部分木の頂点数を計算しておく.

2 回目の dfs で割り当てる. それぞれの頂点を基準で, 割り当てられた点を偏角ソートして, 部分木の頂点数分の点を一定方向回りに割り当てていく.

ソース

これは思いつかないなぁ…

#include <bits/stdc++.h>

using namespace std;

struct Point
{
  int x, y, idx;
};

int N;
vector< int > g[1000];
Point points[1000];
int sub[1000];
int ans[1000];

void dfs(int idx, int par = -1)
{
  sub[idx] = 1;
  for(auto &to : g[idx]) {
    if(par == to) continue;
    dfs(to, idx);
    sub[idx] += sub[to];
  }
}

void dfs2(int idx, int l, int r, int par = -1)
{
  for(int i = l + 1; i < r; i++) {
    if(tie(points[l].x, points[l].y) > tie(points[i].x, points[i].y)) {
      swap(points[l], points[i]);
    }
  }
  ans[idx] = points[l].idx;
  sort(points + l + 1, points + r, [&](Point &a, Point &b)
  {
    return ((a.x - points[l].x) * (b.y - points[l].y) > (b.x - points[l].x) * (a.y - points[l].y));
  });
  ++l;
  for(auto &to : g[idx]) {
    if(par == to) continue;
    dfs2(to, l, l + sub[to], idx);
    l += sub[to];
  }
}

int main()
{
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  for(int i = 0; i < N; i++) {
    cin >> points[i].x >> points[i].y;
    points[i].idx = i;
  }
  dfs(0);
  dfs2(0, 0, N);

  for(int i = 0; i < N; i++) {
    cout << ans[i] + 1 << " ";
  }
  cout << endl;
}