Canada Cup 2016 - ei1333の日記

ABCDを解いた. 1968->1999(+31)でhighest.

A. Jumping Ball

解法

左から '<' が何個連続しているか, また右から '>' が何個連続しているかを数えれば良い.

${O(n)}$

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  string S;
  int N;
  int ret = 0;

  cin >> N;
  cin >> S;
  for(int i = 0; i < S.size(); i++) {
    if(S[i] == '<') ++ret;
    else break;
  }
  for(int i = S.size() - 1; i >= 0; i--) {
    if(S[i] == '>') ++ret;
    else break;
  }
  cout << ret << endl;

}

B. Food on the Plane

codeforces.com

解法

気合い.

ソース

英語が読めない＞＜

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

string t = "fedabc";

int main()
{
  int64 N;
  char c;

  scanf("%lld%c", &N, &c);
  int pos = t.find(c);

  int64 roll = (N - 1) / 2;
  if((N - 1) % 4 == 1) ++roll;
  else if((N - 1) % 4 == 2) --roll;
  if((N - 1) % 4 < 2) {
    cout << roll * 6 + pos + 1 + (N - 1) << endl;
  } else {
    cout << roll * 6 + pos + 1 + (N - 3) << endl;
  }
}

C. Hidden Word

codeforces.com

問題概要

${27}$ 文字からなるアルファベット列 ${s}$ が与えられる. 各アルファベットは少なくとも ${1}$ 回含まれることが保証される.

${s}$ のパスが存在するような ${2 \times 13}$ のグリッドが存在すればそれを出力せよ.

ここでパスはサイドかコーナーで隣接しているマスの間を移動してできる経路のことをいう.

解法

よくわからなかったので, 全探索をしてしまった.

流石に全探索だと遅いのでちょっと考察.

斜めに移動することが可能なので, 上下のアルファベットは入れ替えても一緒. よって例えば右と右下が開いているとき, 試すのは右だけで良い.

これだけやればなんか速かった.

ソース

#include <bits/stdc++.h>

using namespace std;

int dy[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dx[] = {-1, 0, 1, -1, -1, 0, 1, 1};
string S;
char grid[2][13];
bool used[26];

bool isover(int x, int y)
{
  return (x < 0 || y < 0 || x >= 13 || y >= 2);
}

bool solve(int idx, int x, int y)
{
  if(idx == S.size()) {
    return (true);
  } else if(used[S[idx] - 'A']) {
    for(int i = 0; i < 8; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if(isover(nx, ny)) continue;
      if(grid[ny][nx] == S[idx]) return (solve(idx + 1, nx, ny));
    }
  } else {
    used[S[idx] - 'A'] = true;

    if(grid[y ^ 1][x] == 0) {
      grid[y ^ 1][x] = S[idx];
      if(solve(idx + 1, x, y ^ 1)) return (true);
      grid[y ^ 1][x] = 0;
    }

    if(!isover(x + 1, y) && grid[y][x + 1] == 0) {
      grid[y][x + 1] = S[idx];
      if(solve(idx + 1, x + 1, y)) return (true);
      grid[y][x + 1] = 0;
    } else if(!isover(x + 1, y ^ 1) && grid[y ^ 1][x + 1] == 0) {
      grid[y ^ 1][x + 1] = S[idx];
      if(solve(idx + 1, x + 1, y ^ 1)) return (true);
      grid[y ^ 1][x + 1] = 0;
    }

    if(!isover(x - 1, y) && grid[y][x - 1] == 0) {
      grid[y][x - 1] = S[idx];
      if(solve(idx + 1, x - 1, y)) return (true);
      grid[y][x - 1] = 0;
    } else if(!isover(x - 1, y ^ 1) && grid[y ^ 1][x - 1] == 0) {
      grid[y ^ 1][x - 1] = S[idx];
      if(solve(idx + 1, x - 1, y ^ 1)) return (true);
      grid[y ^ 1][x - 1] = 0;
    }

    used[S[idx] - 'A'] = false;
  }
  return (false);
}

void Output()
{
  for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 13; j++) {
      cout << grid[i][j];
    }
    cout << endl;
  }
  exit(0);
}

int main()
{
  cin >> S;
  for(int i = 0; i < 12; i++) {
    grid[0][i] = S.front();
    used[S.front() - 'A'] = true;
    if(solve(1, i, 0)) Output();
    grid[0][i] = 0;
    used[S.front() - 'A'] = false;
  }
  cout << "Impossible" << endl;
}

D. Contest Balloons

codeforces.com

問題概要

${n(1 \le n \le 300\ 000)}$ チームがあって ${1}$ から ${n}$ までの番号がつけられている.

各チームは風船を ${t_i(0 \le t_i \le 10^{18})}$ 個持っていて, チームの体重合計は ${w_i(0 \le w_i \le 10^{18})}$ である.

風船の個数が多い順に順位が振られる. 風船の個数が同じ場合は同順位である. また, 風船の個数が体重合計を上回ると浮かんでしまうので失格となる.

チーム ${1}$ は自分のチームである. 自分が持っている風船を任意個数相手のチームにあげることができる. このときチーム ${1}$ がとることできる最高順位を求めよ.

解法

問題文が面白い.

任意のチーム ${i}$ において, ${w_i - t_i + 1}$ 個の風船を渡せば失格になる. 以降この数を ${l_i}$ とおく.

今の順位から順位を ${1}$ つ上げることを考える.

"自分より多く風船を持つチーム" のうち ${l_i}$ が最小のチームを失格にさせるのが最も効率的.

${l_i}$ 個のバルーンを渡すと, もともと "自分より風船が少なかったチーム" が上に来る. このチームたちを "自分より多く風船が持つチーム" に加える必要がある. 自分の風船の数は単調減少なので, "自分より風船が少なかったチーム" を風船の数で降順ソートしておけば, これに該当するチームは尺取りっぽく無駄なく抽出できる.

また結局, "自分より多く風船が持つチーム" に対してやりたいことは以下 ${2}$ つ.

もともと自分より風船が少なかったチームを, これに加える.
${l_i}$ が最小のチームを取り出す.

これには値の追加, 最小要素の取り出しが ${O(\log n)}$ で出来る優先度付きキューが適している.

以上の, 順位を ${1}$ つ上げる操作を自分の風船がある間繰り返すと良い.

全体で ${O(n \log n)}$ なので間に合う.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int N;
int64 T[300000], W[300000];

int check()
{
  priority_queue< int64, vector< int64 >, greater< int64 > > highdist;
  vector< pair< int64, int > > lowidx;
  for(int i = 1; i < N; i++) {
    if(T[0] >= T[i]) lowidx.emplace_back(T[i], W[i] - T[i] + 1);
    else highdist.push(W[i] - T[i] + 1);
  }
  sort(begin(lowidx), end(lowidx));
  reverse(begin(lowidx), end(lowidx));
  int ret = highdist.size() + 1, tail = 0, odd = T[0];
  while(!highdist.empty()) {
    int64 val = highdist.top();
    highdist.pop();
    odd -= val;
    if(odd < 0) return (ret);
    while(tail < lowidx.size() && odd < lowidx[tail].first) {
      highdist.push(lowidx[tail].second);
      ++tail;
    }
    ret = min< int >(ret, highdist.size() + 1);
  }
  return (ret);
}

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d %d", &T[i], &W[i]);
  }
  printf("%d\n", check());
}