ei1333の日記

ぺこい

Codeforces Round #400 (Div. 1 + Div. 2, combined)

軽症. D 問題落ちたのが事故なんだよなぁ. 2087->2061(-16).

ooox--- +6 3340points 574th.

鯖の方をね安定させてほしいよ.

A. Serial Killer

codeforces.com

解法

どんな問題か忘れた.

罠も無さそうだし, なんか簡単そう.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  string S, T;
  int N;

  cin >> S >> T;
  cin >> N;

  cout << S << " " << T << endl;

  for(int i = 0; i < N; i++) {
    string A, B;
    cin >> A >> B;
    if(S == A) S = B;
    else if(T == A) T = B;
    cout << S << " " << T << endl;
  }
}

B. Sherlock and his girlfriend

codeforces.com

問題概要

ガールフレンドに宝石をプレゼントしたい.(は?)

 {n(1 \le n \le 10^5)} 個の宝石を持っていて、 {i} 番目の宝石の価格は  {i + 1} である.

そこで, 全ての宝石に色をつけたい. 但しある宝石について, その素因数の価格を持つ宝石とは違う色にする必要がある.

必要な色の最小数と, その時の各宝石の色を出力せよ.

解法

 {n \le 2}のとき  {1} 色なので例外処理.

 {n \ge 3} のときを考えると, 価格  {2} と価格  {4} は同じ色で塗れないので  {2} 色以上となる. また, 素数とそれ以外のグループに分けて色を塗ると  {2} 色で塗れるのでこれが最適解.

ソース

#include<bits/stdc++.h>

using namespace std;

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

  bool dp[100003] = {};
  for(int i = 2; i * i <= N; i++) {
    if(!dp[i]) {
      for(int j = i + i; j <= N; j += i) {
        dp[j] = true;
      }
    }
  }

  cout << 1 + (N >= 4) << endl;
  for(int i = 2; i <= N; i++) {
    cout << dp[i] + 1 << " ";
  }
  cout << endl;

}

C. Molly’s Chemicals

codeforces.com

問題概要

長さ  {n(1 \le n \le 10^5)} の配列  {a_i(-10^9 \le a_i \le 10^9)} がある.

任意の連続区間  {[l, r]} のうち, その総和が  {k(1 \le |k| \le 10)} の非負整数乗となる組み合わせの個数を求めよ.

解法

安心する問題. 見るからに危ない罠がある. 僕は罠に引っかからないぞ(これはフラグ(引っかからなかったけど)).

総和として考えられるのは  {k} の非負整数乗なので,  {a_i} の最大値を考えると物理的に高々  {50} 個くらいとなる. この個々の値  {x_j} について, その値になる区間の組を求めて和をとればよい.

で, 値  {x_j} となる区間の組を数えることができれば良い.

累積和をとるとできそうなので,  {b_k = \sum_{ i = 1 }^{j - 1} a_i} としてみる.

すると,  {b_k - b_i = x_j(1 \le i \lt k \le n+1)} となる組を数える問題に帰着できる. 整理すると  {b_k - x_j = b_i}

 {k} は順番に増やしていくとする. map で  {k} 番目まで見たときの  {b_i(i \lt k)} の値の出現回数を管理しておくと, このような数は簡単に数えることが出来る.

罠というのは  {|k| = 1}. hoge 乗してもずっと  {1} (か  {-1}).

1 1
1

 {6} hack できてたのしかった.

ソース

慎重に書く.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 limit = 1LL << 57;

int64 N, K;
int64 A[100000];

int64 get(vector< int64 >& x)
{
  map< int64, int > dp;
  dp[0] = 1;
  int64 sum = 0, ret = 0;
  for(int i = 0; i < N; i++) {
    sum += A[i];
    for(auto& v : x) {
      if(dp.count(sum - v)) ret += dp[sum - v];
    }
    dp[sum]++;
  }
  return(ret);
}

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

  int64 ret = 0;
  vector< int64 > vect;

  if(K == -1) {
    vect.push_back(-1);
    vect.push_back(1);
  } else if(K == 1) {
    vect.push_back(1);
  } else {
    int64 now = 1;
    while(now < limit) {
      vect.push_back(now);
      now *= K;
    }
  }
  cout << get(vect) << endl;
}

D. The Door Problem

codeforces.com

問題概要

 {n(1 \le n \le 10^5)} 個の部屋があって, 部屋のドアの状態は  {r_i(r_i = 0, 1)} である.  {r_i = 0} がロック,  {r_i = 1} がロックされていないことを表す.

また  {m} 個のスイッチがあり,  {i} 番目のスイッチは何部屋かの部屋のドアに対応する. スイッチを  {1} 回押すごとに対応する部屋のロックの状態が反転する. 各部屋に対応するスイッチは  {2} つである.

同時に全部の部屋をロックされていない状態にできるかどうか判定せよ.

解法

ぐっと睨むと  {2} 部グラフ判定になる.

各部屋に対応する  {2} つのスイッチを  {a_i, b_i} とする.

 {r_i = 0} なら  {a_i \ne b_i},  {r_i = 1} なら  {a_i = b_i}.

スイッチを頂点と見立てるとこれは  {2} 色彩色できるか否かなので  {2} 部グラフ判定すれば良い.

 {2} 部グラフ判定は頂点を倍加して Union-Find するやつが気に入ってる.

ソース

ライブラリがバグっていた(完).
下のソースはバグってません.

#include<bits/stdc++.h>

using namespace std;

int n, m;
int r[100000];
vector< int > cont[100000];

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct Bipartite_Graph : UnionFind
{
  vector< int > color;

  Bipartite_Graph(int v) : color(v + v, -1), UnionFind(v + v) {}

  bool bipartite_graph_coloring()
  {
    for(int i = 0; i < color.size() / 2; i++) {
      int a = find(i);
      int b = find(i + color.size() / 2);
      if(a == b) return (false);
      int c = color[a];
      if(c < 0) color[a] = 0, color[b] = 1;
    }
    return (true);
  }

  bool operator[](int k)
  {
    return (bool(color[find(k)]));
  }
};


int main()
{
  cin >> n >> m;
  for(int i = 0; i < n; i++) {
    cin >> r[i];
  }
  for(int i = 0; i < m; i++) {
    int k;
    cin >> k;
    for(int j = 0; j < k; j++) {
      int x;
      cin >> x;
      --x;
      cont[x].push_back(i);
    }
  }

  Bipartite_Graph tree(m);
  for(int i = 0; i < n; i++) {
    if(r[i] == 0) {
      tree.unite(cont[i][0], cont[i][1] + m);
      tree.unite(cont[i][0] + m, cont[i][1]);
    } else {
      tree.unite(cont[i][0], cont[i][1]);
      tree.unite(cont[i][0] + m, cont[i][1] + m);
    }
  }
  if(tree.bipartite_graph_coloring()) cout << "YES" << endl;
  else cout << "NO" << endl;
}

E. The Holmes Children

codeforces.com

問題概要

 {f(n)} {x + y = n} かつ互いに素の  {(x, y)} のペア数とする. 但し  {f(1) = 1}.
 {g(n)} {\sum_{ d|n } f(n/d)} で,  {d|n} {n} の約数集合と定義する.

 {F_k(n)} は以下のように定義される.

  •  {f(g(n))} ( {k = 1})
  •  {g(F_{k-1}(n))} ( {k \gt 1, k \mod 2 = 0})
  •  {f(F_{k-1}(n))} ( {k \gt 1, k \mod 2 = 1})

解法

実は  {g} は恒等写像で常に  {g(n) = n} となる.

 {f(n)} は 包除原理のような有名なDPをすれば求まる.

あとは, それを適当にシミュレーションするだけで通る(え?).

ソース

#include<bits/stdc++.h>

using namespace std;

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

int64 dp[1000001];

int64 f(int64 k)
{
  if(k == 1) return (1);
  vector< int64 > v;
  for(int64 i = 1; i * i <= k; i++) {
    if(k % i == 0) {
      v.push_back(i);
      if(i * i != k) v.push_back(k / i);
    }
  }
  sort(begin(v), end(v));
  reverse(begin(v), end(v));
  for(int i = 0; i < v.size(); i++) {
    dp[i] = k / v[i] + 1;
    for(int j = 0; j < i; j++) {
      if(v[j] % v[i] == 0) dp[i] -= dp[j];
    }
  }
  return (dp[v.size() - 1]);
}

int main()
{
  int64 n, k;
  cin >> n >> k;
  for(int64 i = 1; i <= k && n != 1; i++) {
    if(i & 1) n = f(n);
  }
  cout << n % mod << endl;
}