ei1333の日記

ぺこい

Codeforces Round #341 (Div. 2)

A, B, Cを解いて3完。D, Eは数学に疎いので無理そうだった。
1657->1685(+28)。レートが単調増加してるのでそろそろ単調減少に転じそうつらい。

A. Wet Shark and Odd and Even

問題概要

N個の正整数からなる列から、任意の個数を選んで和を最大化せよ。但し和は偶数である必要がある。

解法

まず偶数は、何個あっても偶数なので全て選んだ方がいい。
奇数は、奇数個あったら奇数だが偶数個なら偶数。よって大きい方から奇数を最大の偶数個選ぶようにすればよい。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 N;
  vector< int64 > B;
  cin >> N;
  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int64 D;
    cin >> D;
    if(D % 2LL == 1LL) B.push_back(D);
    ret += D;
  }
  if(B.size() % 2 == 1) {
    ret -= *min_element(B.begin(), B.end());
  }
  cout << ret << endl;
}

B. Wet Shark and Bishops

問題概要

1000×1000の2次元グリッド上にN個のbishopが置かれている。それぞれのbishopは対角線上にあるbishopを攻撃する。攻撃ペアの個数を求めよ。

解法

例によって45度回転させるととても楽。組み合わせの個数なので、それぞれの対角線に対し,その個数 x に対し, x(x-1)/2 となる。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int main()
{
  int64 N, fieldA[10000] = {}, fieldB[10000] = {};

  cin >> N;
  for(int i = 0; i < N; i++) {
    int A, B;
    cin >> A >> B;
    fieldA[A - B + 5000]++;
    fieldB[A + B + 5000]++;
  }
  int64 ret = 0;
  for(int i = 0; i < 10000; i++) {
    ret += 1LL * fieldA[i] * (fieldA[i] - 1) / 2LL;
    ret += 1LL * fieldB[i] * (fieldB[i] - 1) / 2LL;
  }
  cout << ret << endl;
}

C. Wet Shark and Flowers

問題概要

N匹のサメが円環状に並んでいる。それぞれのサメが、l[i] 以上 r[i] 以下の数を等確率で選ぶ。任意の隣接したサメが選んだ数(si, sj)の積が、与えられた定数である素数 P で割り切れるとき、Wet Shark はサメ i, j にそれぞれ 1000 ドルを与える。 このとき Wet Shark がサメたちに与える金額の合計の期待値を求めよ。

解法

円環、期待値つらい。これ期待値 DP では書けないつらいってなるけど、選ぶ数の範囲が広すぎてそれでは話にならなさそう。なんか線形的なアルゴリズムが求められていそう。数学に疎いつらい。

まず、それぞれの隣接ペアは独立して考えられそう(期待値の線形性による)。Pで割り切れるとき両者が1000ドルずつを得るのは、すなわち 2000ドルを得ることから、

2000 ×  \sum_{i=0}^{N} (si × sj % P == 0 の確率)

で、 si × sj % P == 0 の確率を求めたくなる。そこで, 定数 P が素数であるという性質に注目すると、

si × sj % P == 0 を満たすとき,
si % P == 0 か sj % P == 0 の少なくとも一方に当てはまる

的な考察に至る。これは, 2 つの数を掛けたとき, 素数の約数は生えないからである。
このような si と sj のペアの個数は包除原理ともいえないようなことをすると求まって、これは以下の式となる。

前者: (si % P == 0 の数) = r[i] / P - (l[i] - 1) / P
後者: (sj % P == 0 の数) = r[j] / P - (l[i] - 1) / P
両者: 前者 * (r[j] - l[j] + 1) + 後者 * (r[i] - l[i] + 1) - 前者 * 後者

ここまでくればあとは確率を求めて、足すだけ。2000 をΣの外に出さずにやってしまって、誤差死しそうだったけど10^-7 くらいで済んでまぁ大丈夫だった。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;

int64 N, P, L[100001], R[100001];

int main()
{
  cin >> N >> P;
  long double ret = 0;
  for(int i = 0; i < N; i++) {
    cin >> L[i] >> R[i];
  }
  L[N] = L[0];
  R[N] = R[0];

  for(int i = 0; i < N; i++) {
    int64 cur = R[i] / P - (L[i] - 1) / P; 
    int64 nxt = R[i + 1] / P - (L[i + 1] - 1) / P;
    int64 curdist = R[i] - L[i] + 1;
    int64 nxtdist = R[i + 1] - L[i + 1] + 1;
    int64 sum = cur * nxtdist + nxt * curdist - nxt * cur;
    int64 all = curdist * nxtdist;
    ret += 2000.0 / all * sum;
  }
  cout << fixed << setprecision(20) << ret << endl;
}