ei1333の日記

ぺこい

Codeforces Round #411 (Div. 1)

C………

1947 -> 1904.

A. Find Amir

codeforces.com

問題概要

{n(1 \le n \le 10^5)} 個の学校があって {1} から {n} の番号がつけられている.

始点と終点は自由で, すべての学校を訪れたい.

学校 {i} と学校 {j} との間を移動するためにはチケットが必要で, そのコストは {(i + j) \mod (n+1)} である. 一度買ったチケットはチケットは何回でも使える.

解法

{1} と {n}, {2} と {n - 1}, {3} と {n - 2} … との間はコスト {0} で移動できる.

だいたい {n / 2} 個のグループをすべてまとめるのにかかるコストを知りたくなる.

{n} と {2}, {n - 1} と {3} というふうに結ぶとコスト {1} なのでこれが最適.

答えは {(n - 1) / 2} となる.

ソース

こういう問題, 謎反例がありそうで怖い.

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  cin >> N;
  if(N % 2 == 0) {
    cout << N / 2 - 1 << endl;
  } else {
    cout << N / 2 << endl;
  }
}

B. Minimum number of steps

codeforces.com

問題概要

{a} と {b} からなる文字列が与えられる.

文字列中に {ab} の部分文字列が存在する間, それを {bba} に置き換える.

置き換える回数の最小値を求めよ.

解法

文字列を先頭から見ていって, 文字を追加していく感じで考える.

ある文字列に {b} を加えると, {a_{sz}} が今までに現れた {a} の文字数とすると, 操作回数は {2^{a_{sz}} - 1} 回増加する.

その和を求めれば解.

ソース

なんか, 寝てたら他の人々が無限にACしていて最遅になってしまってつらかった.

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
  int64 fact[1000001];
  fact[0] = 1;
  for(int i = 1; i <= 1000000; i++) {
    fact[i] = fact[i - 1] * 2;
    fact[i] %= mod;
  }

  string S;
  cin >> S;

  int64 ret = 0;
  int A_sz = 0;
  for(int j = 0; j < S.size(); j++) {
    if(S[j] == 'b') {
      ret += fact[A_sz];
      ret %= mod;
      ret += mod - 1;
      ret %= mod;
    } else {
      ++A_sz;
    }
  }
  cout << ret << endl;
}

C. Ice cream coloring

codeforces.com

問題概要

{n(1 \le n \le 3 \times 10^5)} 頂点の木 {T} が与えられる.

また {m(1 \le m \le 3 \times 10^5)} 種類のアイスクリームが売られている.

頂点 {i} では {s_i(0 \le s_i \le 3 \times 10^5)} 種類のアイスクリームが購入できる.

同じ種類のアイスクリームについては, 木 {T} 内で部分連結である.

新たな {m} 頂点のグラフ {G} を考える. {T} の頂点で, 種類 {i} と {j} のアイスクリームが売られている頂点が存在する時, 頂点 {i} と頂点 {j} に辺が張る.

{G} の彩色数の最小値と, その塗り方を求めよ.

解法

適当な頂点を根とした根付き木を考える.

連結という条件を上手く使う.

根から下っていったときに, ある頂点ではじめて現れるアイスクリームは, その部分木以外では現れることはない.

またある頂点について, 親で現れていたアイスクリームが, ある頂点で現れなくなった時, その部分木内では現れない.

これだけわかれば, あとは自明(コンテスト中は自明ではなかった).

行きがけ順に, 自分の頂点が販売できるアイスクリームのうちまだ色が決まっていない種類について, 貪欲に最小の色を割り当てれば良い.

ある頂点でどの色を使っていないかは, 鳩ノ巣(鳩ノ巣ではないね)っぽくやると全体で {s_i} の合計くらいに収まる.

ソース

ソースコード, 思っていたよりずっとシンプルだよね….

#include <bits/stdc++.h>

using namespace std;


int N, M;
vector< int > beet[300001];
vector< int > g[300001];
int color[300001];
int used[300001];

void dfs(int idx, int par = -1)
{
  vector< bool > used(beet[idx].size() + 1, 0);
  for(auto &c : beet[idx]) {
    if(~color[c]) used[min((int) beet[idx].size(), color[c])] = idx;
  }
  int tail = 0;
  for(auto &c : beet[idx]) {
    while(used[tail]) ++tail;
    if(!~color[c]) color[c] = tail++;
  }
  for(auto &to : g[idx]) {
    if(to != par) dfs(to, idx);
  }
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    int S;
    scanf("%d", &S);
    while(S--) {
      int t;
      scanf("%d", &t);
      beet[i].push_back(t);
    }
  }

  for(int i = 1; i < N; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  memset(used, -1, sizeof(used));
  memset(color, -1, sizeof(color));
  dfs(0);

  int res = 1;
  for(int i = 1; i <= M; i++) res = max(res, color[i] + 1);
  cout << res << endl;
  for(int i = 1; i <= M; i++) cout << max(1, color[i] + 1) << " ";
  cout << endl;
}