ei1333の日記

ぺこい

Educational Codeforces Round 20

oooooo. 6 完 32nd

A. Maximal Binary Matrix

codeforces.com

問題概要

 {n \times n(1 \le n \le 100)} の零行列がある.

対称行列を保ったまま, ちょうど  {k(0 \le k \le 10^6)} 個の  {0} {1} に変更して出来る辞書順最大の行列を求めよ.

解法

左上から順に貪欲に  {1} に変えていく.

対角要素は自由に変えてよくて, それ以外の要素は対称の要素も同時に変えるようにする.

 {O(n^2)}.

ソース

これが A 問題かぁってなった.

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, K;
  cin >> N >> K;

  int mat[100][100] = {{}};
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(mat[i][j]) continue;
      if(i == j && K > 0) {
        K--;
        mat[i][j] = true;
      } else if(K > 1) {
        K -= 2;
        mat[i][j] = mat[j][i] = true;
      }
    }
  }
  if(K == 0) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        cout << mat[i][j] << " ";
      }
      cout << endl;
    }
  } else {
    cout << -1 << endl;
  }
}

B. Distances to Zero

codeforces.com

問題概要

長さ  {n(1 \le n \le 2 \times 10^5)} の数列  {\{a_0, a_1, \dots, a_{n-1}\}} が与えられる. 少なくとも  {1} つの要素は  {0} であることが保証される.

それぞれの要素位置について最も近い  {0} までの距離を求めよ.

解法

左からえいして右からえいする(?).

左から見ていったときに最後に現れた  {0} の位置を保存しておけば, ある要素について, その要素とその要素よりも左で最も近い  {0} までの距離が求まる.

右も同様にして min をとればよい.

 {O(n)}.

ソース

はい.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, A[200000];
  int beet[200000];
  fill_n(beet, 200000, INF);

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

  int st = -1;
  for(int i = 0; i < N; i++) {
    if(A[i] == 0) st = i;
    if(~st) beet[i] = min(beet[i], i - st);
  }
  st = -1;
  for(int i = N - 1; i >= 0; i--) {
    if(A[i] == 0) st = i;
    if(~st) beet[i] = min(beet[i], st - i);
  }
  for(int i = 0; i < N; i++) {
    cout << beet[i] << " ";
  }
  cout << endl;
}

C. Maximal GCD

codeforces.com

問題概要

長さ  {k(1 \le k \le 10^{10})} で数列全体の和が  {n(1 \le n \le 10^{10})} の狭義単調増加部分列で最大公約数が最大となるものを求めよ.

解法

まず  {1} から  {k} までの総和が  {n} を上回れば, そのような列は存在しない. 逆にそれ以外なら, なんらかの列が構成できる.

構成する最大公約数  {x} を決め打ちすることを考える.  {x} を最大公約数とすると構成する列は  {k_1x, k_2x, \dots, k_{p}x} みたいに  {x} の倍数になっている必要がある.

ぐっと睨むと, 列は全体を  {x} でくくれるので, 最大公約数となりうるものは  {n} の約数であることがわかる.

あとは適当にえい.

 {O(\sqrt k)}.

ソース

問題設定がシンプル. これ, はまるとコンテストが終了しそうだったけどすんなり解けてよかった.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

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

  int64 sum = 0;
  for(int i = 1; i <= K; i++) {
    sum += i;
    if(sum > N) {
      cout << -1 << endl;
      return (0);
    }
  }

  vector< int64 > vs;
  for(int64 i = 1; i * i <= N; i++) {
    if(N % i == 0) {
      vs.push_back(i);
      if(i * i != N) vs.push_back(N / i);
    }
  }
  sort(begin(vs), end(vs));
  reverse(begin(vs), end(vs));

  for(auto &v : vs) {
    int64 gcd = v;
    int64 space = N / gcd;
    if(K * (K + 1) / 2 <= space) {
      int64 sums = 0;
      for(int i = 1; i < K; i++) {
        sums += gcd * i;
        cout << gcd * i << " ";
      }
      cout << N-sums << endl;
      return (0);
    }
  }
}

D. Magazine Ad

codeforces.com

問題概要

スペースで区切られた単語列が与えられる.

それぞれの単語には, 文字 ‘-’(ハイフン) が含まれていることがある. ハイフンの位置で単語を折り返すことができる.

単語が折り返されると, ‘-’ の前の単語と ‘-’ が現在の行に残り, それ以降が次の行に置かれる.

 {2} つの単語の間で改行することもできて, その場合はスペースは現在の行にとどまる.

 {k(1 \le k \le 10^5)} 行以下となるように上手く単語を折り返した時, 最小の幅を求めよ.

ソース

野生の勘で解の二分探索ということはわかる.

判定については, 適当に単語列前から見ていって折り返すべきところで折り返す, としか言えない….(これが面倒なんだけど

ソース

謎バグを埋めてしまって悲しい気持ちになった.

僕はデバッグできないので,  {1} からコードを書き直したら通ってまた悲しい気持ちになった(ア

#include <bits/stdc++.h>

using namespace std;

int N;
string S;
vector< int > tt;

bool check(int width)
{
  int beet = 1;

  int sum = 0;
  for(int i = 0; i < tt.size(); i++) {
    if(tt[i] > width) return (false);
    if(sum + tt[i] > width) {
      ++beet;
      sum = 0;
    }
    sum += tt[i];
  }
  return (beet <= N);
}

int main()
{
  cin >> N;
  cin.ignore();
  getline(cin, S);

  int tail = 0;

  for(int i = 0; i <= S.size(); i++) {
    if(i == S.size() || S[i] == ' ' || S[i] == '-') {
      tt.emplace_back(i - tail + 1);
      tail = i + 1;
    }
  }
  tt.back()--;
  int low = 0, high = 1 << 28;
  while(high - low > 0) {
    int mid = (low + high) >> 1;
    if(check(mid)) high = mid;
    else low = mid + 1;
  }
  cout << low << endl;
}

E. Roma and Poker

codeforces.com

問題概要

 {n(1 \le n \le 1000)} 試合を行って, それぞれの結果は勝ちか負けか引き分けである.

このうちいくつかの試合の結果がわからなくなってしまった.

最終的に勝敗の差は  {k(1 \le k \le 1000)} で, 最後以外に差が  {k} になった場面は存在しないことが分かっている.

復元した結果の一例を出力せよ.

解法

(勝ち-負け) の値をもって DP して復元する.

abs(勝ち-負け) が  {k} にならないように適当に遷移させる.

 {O(nk)}.

ソース

#include <bits/stdc++.h>

using namespace std;

int N, K;
string S;

int dp[2300][1001];
pair< int, int > nt[2301][1001];

bool rec(int sa, int tern)
{
  int &ret = dp[sa+1100][tern];
  if(~ret) return (ret);
  if(tern == N) return (abs(sa) == K);
  if(abs(sa) == K) return (false);
  if(S[tern] == '?' || S[tern] == 'L') {
    if(rec(sa - 1, tern + 1)) {
      nt[sa+1100][tern] = {sa - 1, tern + 1};
      return (ret = true);
    }
  }
  if(S[tern] == '?' || S[tern] == 'W') {
    if(rec(sa + 1, tern + 1)) {
      nt[sa+1100][tern] = {sa + 1, tern + 1};
      return (ret = true);
    }
  }
  if(S[tern] == '?' || S[tern] == 'D') {
    if(rec(sa, tern + 1)) {
      nt[sa+1100][tern] = {sa, tern + 1};
      return (ret= true);
    }
  }
  return(ret = false);
}

int main()
{
  cin >> N >> K;
  cin >> S;

  memset(dp, -1, sizeof(dp));
  if(rec(0, 0)) {
    int latte = 0, malta = 0;
    for(int i = 0; i < N; i++) {
      auto ns = nt[latte + 1100][malta];
      if(latte == ns.first) cout << "D";
      else if(latte < ns.first) cout << "W";
      else cout << "L";
      latte = ns.first;
      malta = ns.second;
    }
    cout << endl;
  } else {
    cout << "NO" << endl;
  }
}

F. Coprime Subsequences

codeforces.com

問題概要

長さ  {n(1 \le n \le 10^5)} の数列  {a_i(1 \le a_i \le 10^5)} が与えられる.

最大公約数が  {1} となるような subsequence のとりかたを  {10^9 + 7} で割った余りで求めよ.

解法

数列からとりうる部分列の個数は  {2^n - 1}. この個数から, gcd が 2 以上の部分列の個数を引けばそれが答え.

前から見ていって, それぞれの要素について部分列の一番最後に持ってくる場合を仮定した時に, gcd が 2 以上となる部分列の個数を求める. 

これは包除原理で求めることが出来る. なんでできるんだろう(分かっていない顔

 {O(n \sqrt a_i)}.

ソース

これ終了  {n} 秒前にサンプル通って  {4} 秒前提出でアツかった.

#include <bits/stdc++.h>

using namespace std;

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

int64 fact[100001];
int64 arr[100001];

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

  int N, A[100000];
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];

  int64 ret = fact[N] - 1;
  int64 add = 0;
  for(int i = 0; i < N; i++) {
    if(A[i] == 1) {
      continue;
    }
    vector< int > v;
    int tmp = A[i];
    for(int j = 2; j * j <= tmp; j++) {
      if(tmp % j == 0) v.push_back(j);
      while(tmp % j == 0) tmp /= j;
    }
    if(tmp > 1) v.push_back(tmp);

    int sz = v.size();
    for(int bit = 1; bit < 1 << sz; bit++) {
      int odd = 1;
      int n = 1;
      for(int j = 0; j < sz; j++) {
        if((bit >> j) & 1) odd *= -1, n *= v[j];
      }
      if(odd < 0) (ret += mod - fact[arr[n]]) %= mod;
      else (ret += fact[arr[n]]) %= mod;
      arr[n]++;
    }
  }
  cout << ret << endl;
}