Manthan, Codefest 17 - ei1333の日記

ooo-o– 4668pts 89th.

2301->2336(+35) おいおいおいあと64やで.

A. Tom Riddle’s Diary

codeforces.com

問題概要

分かりやすいので自分で読んで♡

解法

問題文に解法が書かれているので、それをそのまま実装します(？）.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  string S[100];

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

    bool found = false;
    for(int j = 0; j < i; j++) {
      if(S[i] == S[j]) found = true;
    }

    if(found) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}

B. Marvolo Gaunt’s Rin

codeforces.com

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${a_i(-10^9 \le a_i \le 10^9)}$ と, 定数 ${p, q, r}$ が与えられる.

${1 \le i \le j \le k \le n}$ を満たす ${(i, j, k)}$ のうち, ${p a_i + q a_j + r a_k}$ の最大値を求めよ.

解法

${n}$ 通りある真ん中の位置 ${j}$ を決めうしする. もー.

${i}$ の最適な位置は, ${j}$ を含む左側での ${a_i}$ の最大値か最小値.

同様に ${k}$ の最適な位置は, ${j}$ を含む右側での ${a_k}$ の最大値か最小値.

これらの値は前計算で ${O(n)}$ で求まるため, できる.

ソース

long long に ${3 \times 10^{18}}$ が入らないと思っていて, 非常に険しい気持ちになった.

結構入るのね.

#include<bits/stdc++.h>

using namespace std;

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

int64 N, P, Q, R, A[100000];
int64 LL[2][100000], RR[2][100000];

int main()
{
  cin >> N >> P >> Q >> R;
  for(int i = 0; i < N; i++) cin >> A[i];

  int64 latte = INF, malta = -INF;
  for(int i = N - 1; i >= 0; i--) {
    latte = min(latte, A[i]);
    malta = max(malta, A[i]);
    LL[0][i] = latte, LL[1][i] = malta;
  }
  latte = INF, malta = -INF;
  for(int i = 0; i < N; i++) {
    latte = min(latte, A[i]);
    malta = max(malta, A[i]);
    RR[0][i] = latte, RR[1][i] = malta;
  }

  int64 ret = numeric_limits< int64 >::min();
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < 2; j++) {
      for(int k = 0; k < 2; k++) {
        ret = max(ret, RR[j][i] * P + A[i] * Q + LL[k][i] * R);
      }
    }
  }

  cout << ret << endl;
}

C. Helga Hufflepuff’s Cup

codeforces.com

問題概要

${n}$ 頂点の木が与えられる. ${i}$ 番目の辺は ${u_i}$ と ${v_i}$ を結ぶ.

各頂点に以下の条件を満たすように値を割り当てる.

${1}$ 以上 ${m(1 \le m \le 10^9)}$ 以下の整数
値 ${k(1 \le k \le m)}$ を割り当てた隣接する頂点は ${k}$ 未満
値 ${k}$ の頂点は最大 ${x(1 \le x \le 10)}$ 個

割り当て方を ${10^9 + 7}$ で割った余りで求めよ.

解法

まあ木DPするしかないんでしょうねという感情になる.

値の種類が多すぎるのでぐっと睨むと, ${k}$ 未満の値の集合(less)と ${k}$ より大きいの値の集合(more), ${k}$ (equal) の ${3}$ つにまとめてもよいことがわかる.

dp[idx][sum][{less, more, equal}] := 頂点 idx を根とする部分木で, equal を sum 個割り当てていて, かつ頂点 idx に値 {less, more, equal} を割り当てたときの組み合わせ

とすると, 気合いでやることになる.

頂点 idx のそれぞれの子の頂点で使った値(集合)を ${s_1, s_2, \dots}$ とする. ${s_i = }$ equal となるものが存在すれば頂点 idx には less, 存在しなければ less も more も使えて, すべての ${i}$ について ${s_i}$ = less ならば equal も使えるみたいにやるとできる.

計算量は ${O(n x^2)}$ で, こどふぉを信じろになる.

ソース

木DP, 苦手だなあって思いながら険しい気持ちで書いてたらなんかできたため.

いきなり難しくなっていてア.

#include<bits/stdc++.h>

using namespace std;

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

int N, M, K, X;
vector< int > g[100000];
int64 dp[100000][11][3], dp2[11][3];

int gettype(int a, int b)
{
  if(a == 2 || b == 2) return (2); // beet
  if(a == 0 && b == 0) return (0); // less then
  return (1); // more
}

int64 rec(int idx, int par = -1)
{
  dp[idx][0][0] = 1;

  for(auto &to : g[idx]) {
    if(par == to) continue;
    rec(to, idx);
    memset(dp2, 0, sizeof(dp2));
    for(int i = 0; i <= 10; i++) {
      for(int j = 0; j <= 10 - i; j++) {
        for(int k = 0; k <= 2; k++) {
          for(int l = 0; l <= 2; l++) {
            (dp2[i + j][gettype(k, l)] += 1LL * dp[idx][i][k] * dp[to][j][l] % mod) %= mod;
          }
        }
      }
    }
    for(int i = 0; i <= 10; i++) {
      dp[idx][i][0] = dp2[i][0];
      dp[idx][i][1] = dp2[i][1];
      dp[idx][i][2] = dp2[i][2];
    }
  }

  memset(dp2, 0, sizeof(dp2));
  int ret = 0;

  for(int i = 0; i < 10; i++) { // -> add
    (dp2[i + 1][2] += dp[idx][i][0]) %= mod;
  }
  for(int i = 0; i <= 10; i++) { // -> less
    (dp2[i][0] += dp[idx][i][0] * (K - 1) % mod) %= mod;
    (dp2[i][0] += dp[idx][i][1] * (K - 1) % mod) %= mod;
    (dp2[i][0] += dp[idx][i][2] * (K - 1) % mod) %= mod;
  }

  for(int i = 0; i <= 10; i++) { // -> more
    (dp2[i][1] += dp[idx][i][0] * (M - K) % mod) %= mod;
    (dp2[i][1] += dp[idx][i][1] * (M - K) % mod) %= mod;
  }

  for(int i = 0; i <= X; i++) {
    dp[idx][i][0] = dp2[i][0];
    dp[idx][i][1] = dp2[i][1];
    dp[idx][i][2] = dp2[i][2];
    (ret += dp[idx][i][0]) %= mod;
    (ret += dp[idx][i][1]) %= mod;
    (ret += dp[idx][i][2]) %= mod;
  }
  return (ret);
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 1; i < N; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  cin >> K >> X;
  printf("%lld\n", rec(0));
}

E. Salazar Slytherin’s Locket

codeforces.com

問題概要

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

${l_i}$ 以上 ${r_i}$ 以下の値について ${b_i}$ 進数表記(reading0は認めない)をして, それぞれの桁の数字の出現回数が偶数回となっているような値の個数を求めよ.

解法

bitdp + 桁DPでできそうなことがわかる(これでできないと解けないため). ここではメモ化再帰を考える.

dp[idx][bit][zero][free][b] := 残り idx 桁, それぞれの値の出現状況(mod2)が bit, 0 かそれ以外か, 値の上限に沿っているか, b 進表記のとき, それ以降で条件を満たす組み合わせの個数

とする. 全体の状態数は 60 × 2^10 × 2 × 2 × 10 みたいな感じになって, 1 つだけなら十分間に合いそう.

しかし各クエリごとにdpを計算しなおしているとこわれるため, もうちょっと考える. すると free が false になった以降の組み合わせの個数はクエリの値 ${l_i, r_i}$ に依存しないことを思うと, free が false のときだけメモ化して, true のときはメモ化せずに愚直に回すとできそうな気持ちになる. free が true の回数は桁数なので間に合う.

ソース

うんうん. バグらず書けてよかった.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int64 dp[70][1 << 10][10][2];
string S;

int64 rec(int idx, int bit, bool free, int zero, const int bb)
{
  if(idx == -1) return (bit == 0);
  if(free && ~dp[idx][bit][bb][zero]) return (dp[idx][bit][bb][zero]);
  int end = free ? bb - 1 : S[idx] - '0';
  int64 ret = 0;
  for(int i = 0; i <= end; i++) {
    bool nt = zero & (i == 0);
    ret += rec(idx - 1, nt ? 0 : (bit ^ (1 << i)), free | (i != end), nt, bb);
  }
  if(free) return (dp[idx][bit][bb][zero] = ret);
  return (ret);
}

int main()
{
  memset(dp, -1, sizeof(dp));

  int Q;
  scanf("%d", &Q);
  for(int i = 0; i < Q; i++) {
    int B;
    int64 L, R;
    scanf("%d %lld %lld", &B, &L, &R);

    S.clear();
    --L;
    do {
      S += char('0' + L % B);
      L /= B;
    } while(L);

    auto ret = -rec(S.size() - 1, 0, false, true, B);

    S.clear();
    do {
      S += char('0' + R %B);
      R /= B;
    } while(R);
    ret += rec(S.size() - 1, 0, false, true, B);
    printf("%lld\n", ret);
  }
}