読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

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;
  }
}