Codeforces Round #392 (Div. 2)

なんで ${4}$ 完できなかったんだろう.

A. Holiday Of Equality

問題概要

長さ ${n(1 \le n \le 100)}$ の数列 ${a_i(0 \le a_i \le 10^6)}$ がある.

いくつかの要素に任意の値を加えることにより, 全要素の値を等しくしたい.

加える値の最小和 ${S}$ を求めよ.

解法

数列の最大値に合わせるのが良い.

最大値 ${x}$ を求めて, ${\sum_{ i = 1 }^{ n } x - a_i}$ .

ソース

#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 xx = *max_element(A, A + N);
  int ret = 0;
  for(int i = 0; i < N; i++) {
    ret += xx - A[i];
  }
  cout << ret << endl;

}

B. Blown Garland

問題概要

R B Y G ! からなる文字列 ${s (4 \le |s| \le 100)}$ が与えられる.

それぞれの文字はそのセルの色を表すが, ! の位置は色がわからなくなってしまった.

文字列で任意の連続 ${4}$ 要素をとってきたときにそれぞれの色が相異なっていたことが分かっている.

このときもとの文字列を復元せよ. R B Y G は 1 回以上現れ, もとの文字列は正しいことが保証される.

解法

頭をつわかなかったので最初の ${4}$ 文字を next_permutaion で全列挙して試した.

最初の ${4}$ 文字の順番が決まると, 条件を満たすものはそれを何個か連結した文字列となる.

実際には, 上の事実より mod 4 で文字列を分けると, 題意の制約より一意に定まる.

ソース

#include<bits/stdc++.h>

using namespace std;

const string a = "RBYG";

int main()
{
  string S;
  cin >> S;

  string t = "RBYG";
  sort(begin(t), end(t));
  do {
    string link = t;
    while(link.size() <= S.size()) link += t;

    bool match = true;
    int s[4] = {};
    for(int i = 0; i < S.size(); i++) {
      if(S[i] != '!' && S[i] != link[i]) match = false;
      if(S[i] == '!') s[a.find(link[i])]++;
    }
    if(match) {
      cout << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << endl;
      break;
    }
  } while(next_permutation(begin(t), end(t)));
}

C. Unfair Poll

問題概要

${n(1 \le n \le 100)}$ 行 ${m(1 \le m \le 100)}$ 列で人が並んでいる.

以下の手順で ${k(1 \le k \le 10^{18})}$ 人訪問する.

${1}$ 行目のすべての人を左から順に訪問する. これを ${n}$ 行目まで繰り返す.
${n-1}$ 行目のすべての人を左から順に訪問する. これを ${2}$ 行目まで繰り返す.
上に戻る.

それぞれのセルのうち訪問した数の最大回数, 最小回数, また場所 ${(x, y)}$ の訪問回数を求めよ.

解法

${n = 1, 2}$ とそれ以外で場合分け.

${n = 1}$ のときは, 同じ行.

${n = 2}$ のときは, 上下の順.

それ以外は ${\mod (2n-2)}$ でいい感じの周期になる. 例えば ${n = 4}$ のときは 123432123432..., 周期にわけると 123432, 123432, ... となる. 厳密にやれば ${O(1)}$ で求まるがミスが怖い. ${n, m}$ が小さいことを利用して, 最初に ${2n-2}$ で割ってそれぞれのセルの訪問回数(この回数は自明) を求めた後, 残った分をシミュレーションすればよい.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 N, M, K, X, Y;
  cin >> N >> M >> K >> X >> Y;

  int64 grid[105][105] = {{}};

  int64 nokori = K;

  if(N > 2) {
    int64 repeatRow = K / M;
    int64 oneLoop = N - 1;
    int64 loop = repeatRow / (oneLoop * 2);
    for(int i = 1; i <= N; i++) {
      for(int j = 1; j <= M; j++) {
        if(i == 1 || i == N) grid[i][j] = loop;
        else grid[i][j] = loop * 2;
      }
    }
    nokori -= loop * oneLoop * M * 2;
  } else {
    int64 repeatRow = K / M;
    int64 oneLoop = N;
    int64 loop = repeatRow / oneLoop;
    for(int i = 1; i <= N; i++) {
      for(int j = 1; j <= M; j++) {
        grid[i][j] = loop;
      }
    }
    nokori -= loop * oneLoop * M;
  }

  int64 a = numeric_limits< int64 >::max(), b = 0;

  vector< pair< int, int > > vv;
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) vv.emplace_back(j, i);
  }
  for(int i = N - 1; i > 1; i--) {
    for(int j = 1; j <= M; j++) vv.emplace_back(j, i);
  }

  while(nokori > 0) {
    for(auto &pp : vv) {
      grid[pp.second][pp.first]++;
      nokori--;
      if(nokori == 0) break;
    }
  }


  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      a = min(a, grid[i][j]);
      b = max(b, grid[i][j]);
    }
  }

  cout << b << " " << a << " " << grid[X][Y] << endl;
}

D. Ability To Convert

問題概要

整数 ${n(0 \le n \le 10^9), k(0 \le k \lt 10^{60})}$ が与えられる.

${k}$ をいくつかの ${n}$ 未満の整数(reading 0 はダメ) に分割する.

この整数をこの順に, ${n}$ 進数の各桁の値と見なし, その値を 10 進表記にする.

整数 ${k}$ の各桁は ${n}$ 未満である.

得られる値の最小値を求めよ.

解法

貪欲.

なるべく手前の桁で稼いだ方が最小になるので, ${k}$ を後ろから見ていって, ${n}$ 未満の最大の整数となるように分割すればよい.

ここで ${k}$ の各桁が ${n}$ 未満の制約がないと, 途中で分割できなくなることがあるので, この制約がとても嬉しい.

ソース

なにも考えずに DP したらオーバーフローに負けた...(気をつければDPでも通ったけど貪欲がシンプル)

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  string K;

  cin >> N;
  cin >> K;

  reverse(begin(K), end(K));
  long long ret = 0, tail = 1;
  for(int i = 0; i < K.size(); i++) {
    long long ok = 0;
    long long local = 0, base = 1;
    for(int j = i; j < K.size() && base <= N; j++, base *= 10) {
      if(K[j] == '0') continue;
      local = local + base * (K[j] - '0');
      if(local >= N) break;
      ok = local;
      i = j;
    }
    ret += tail * ok;
    tail *= N;
  }
  cout << ret << endl;
}

ei1333の日記

ぺこい

Codeforces Round #392 (Div. 2)

A. Holiday Of Equality

問題概要

解法

ソース

B. Blown Garland

問題概要

解法

ソース

C. Unfair Poll

問題概要

解法

ソース

D. Ability To Convert

問題概要

解法

ソース