Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition)

ABCDを通して4完で384位.
レートは1714->1714(±0)みたいな感じになって、参加してないことになってしまった.
Bに1時間溶かしたので, それにはまらなければなぁという感じ.

A. Bear and Game

問題概要

テレビを最大90分見る.
$t_{i}$ 分に面白いことが起こる. 15分連続でつまらないと見るのをやめる.
何分テレビを見ることになるか求めよ.

解法

やるだけ. ${t_{i}}$ と ${t_{i+1}}$ の要素の差が16以上ならそこで消したことにする.

ソース

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

int main()
{
  int N;
  cin >> N;
  int prev = 15;
  for(int i = 0; i < N; i++) {
    int t;
    cin >> t;
    if(prev >= t) prev = t + 15;
  }
  cout << min(90, prev) << endl;
}

B. Problems for Round

問題概要

それぞれ難易度が $i$ の ${n (1 \le n \le 100 000)}$ 個の問題がある.
また、 ${u_i}$ と ${v_i}$ の問題は似ている.
この問題を以下の条件を満たすように, Div. 1 と Div. 2 の 2 つに分けるとき, 何通りの分け方があるか.

それぞれの問題セットは空でない
$n$ 個の問題すべてを使う
Div. 1 のすべての問題は Div. 2 の任意の問題より難しい
2 つの問題が似ている問題であれば別の Div

解法

あまりに難しい.
Div. 1 に属する問題の下限と, Div. 2 に属する問題の上限を求めると、答えはその範囲となる.
前者は, ${ \min(\max(u_i, v_i)) }$ で求まる. なぜなら, ${\max(u_i, v_i)}$ の問題が必ず Div. 1 である必要があるからであり, その最小値が Div. 1 である下限である. 後者は, ${ \max(\min(u_i, v_i)) }$ で求まる. 理由は同様.

ソース

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  int small = N, big = 1;
  for(int i = 0; i < M; i++) {
    int U, V;
    cin >> U >> V;
    small = min(small, max(U, V));
    big = max(big, min(U, V));
  }
  cout << max(0, small - big) << endl;
}

C. Bear and Colors

問題概要

1 から $n(1 \le n \le 5000)$ の番号がつけられたボールがある. $i$ 番目のボールの色は ${t_i}$ である.
支配色を, 連続区間内で最も現れた色と定義する(同じなら最小のindexをもつ色).
連続区間の分け方は ${n*(n+1)/2}$ 通りあるので, このそれぞれの場合について支配色を求め, 色ごとに支配色となった回数の合計を出力せよ.

解法

$O(n^2)$ が間に合う.
まず、区間の最初の $index$ を決める( $n$ 通り). 区間 ${\lbrack index, j \rbrack}$ から, 区間 ${\lbrack index, j + 1 \rbrack}$ とすることを考える.
支配色となりうる色は明らかに, ${\lbrack index, j \rbrack}$ のときの支配色か, ${t_{j+1}}$ . その 2 色を比べて, 支配色を ${\lbrack index, n \rbrack}$ になるまで更新していけば良い.

ソース

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

int main()
{
  int N, T[5000];
  int sum[5000] = {};
  
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> T[i];
    --T[i];
  }
  for(int i = 0; i < N; i++) {
    vector< int > colors(N, 0);
    int each = 0;
    for(int j = i; j < N; j++) {
      colors[T[j]]++;
      if(colors[each] < colors[T[j]] ||
         (colors[each] == colors[T[j]] && each > T[j])) {
        each = T[j];
      }
      ++sum[each];
    }
  }

  for(int i = 0; i < N; i++) {
    if(i > 0) cout << " ";
    cout << sum[i];
  }
  cout << endl;
}

D. Bear and Two Paths

問題概要

$n$ 頂点の連結な無向グラフを考える.
$a$ から, $b$ と, $c$ から $d$ をすべての頂点をちょうど 1 回ずつ通って移動する.
また, $a-b$ と $c-d$ に辺は存在しない.
$n$ と, 使っても良い辺の上限 $k$ が与えられるので, そのようなグラフが存在すれば, 移動経路を出力せよ.

解法

$a-b$ の移動を考えると, 明らかに $n - 1$ 個の辺を使って出来る木が良い. 具体的には ${a-...-b}$ となるような木.
$c-d$ の移動はなるべく, $a - b$ の辺を使ったほうが良いので $a-c-...-d-b$ となる. ただし, これでは ${a, b}$ の頂点を通れないので, $c-a-x-..-y-b-d$ の移動を考え, $a$ と ${x}$ , ${y}$ と ${b}$ に辺をはると良い. 辺の数は $n+1$ 個必要で, また頂点数が 4 以下のときには上が成り立たないので作れないことに注意する.

ソース

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

int main()
{
  int N, K, A, B, C, D;
  
  
  cin >> N >> K;
  cin >> A >> B >> C >> D;
  --A, --B, --C, --D;
  
  if(K <= N || N == 4) {
    cout << -1 << endl;
  } else {
    vector< int > Array;
    Array.push_back(A);
    Array.push_back(C);
    for(int i = 0; i < N; i++) {
      if(i != A && i != B && i != C && i != D) {
        Array.push_back(i);
      }
    }
    Array.push_back(D);
    Array.push_back(B);
    for(int i = 0; i < N; i++) {
      if(i > 0) cout << " ";
      cout << Array[i] + 1;
    }
    cout << endl;

    cout << Array[1] + 1 << " ";
    cout << Array[0] + 1 << " ";
    cout << Array[2] + 1 << " ";
    for(int i = 3; i < N - 2; i++) cout << Array[i] + 1 << " ";
    cout << Array[N - 1] + 1 << " ";
    cout << Array[N - 2] + 1 << endl;
  }
}

ei1333の日記

ぺこい

Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition)

A. Bear and Game

問題概要

解法

ソース

B. Problems for Round

問題概要

解法

ソース

C. Bear and Colors

問題概要

解法

ソース

D. Bear and Two Paths

問題概要

解法

ソース