ei1333の日記

ぺこい

Codeforces Round #350 (Div. 2)

1691->1714(+23). 413位. A, B, C, D1, D2, E まで出して C 以外は通った.
C は unordered_map killer っぽいもので落ちた.

A. Holidays

問題概要

1 年が 7 日であり, 平日 5 日と休日 2 日が交互にくる.
任意の年を選択するとき, 休日の最大数と最小数を求めよ.

解法

まず, 休日を最大にするとき, 休休平平平平平. また, 休日を最小にするとき, 平平平平平休休.
基本は  n / 7 * 2 だが, 休日の位置と  {n \% 7} の値によって, 休日を微妙に含んだりするのでそこら辺を場合分けする.

ソース

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

int main()
{
  int N;
  cin >> N;
  cout << N / 7 * 2 + (N % 7 >= 6) << " " << N / 7 * 2 + min(N % 7, 2) << endl;
}

B. Game of Robots

問題概要

ロボットが  n (1 \le n \le 100 000) 体いる.
まず 1 番目のロボットから順に,  i 番目のロボットは自分の前のロボットが言った番号  {id_{i} (1 \le id_{i} \le 10^{9})} をすべて順に復唱したあと, 自分の番号を言う.  k 番目に言った番号を求めよ.

解法

 i 番目のロボットが発言をする回数は明らかに  i 回.
よって 1 番目の人から順に見ていき,  i 回足した結果が最初に  k 回を上回った人が発言するので, 頑張って計算する.

ソース

 k から引いてく実装のほうが楽だったかな...

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

int main()
{
  int64 N, K, id[100001];

  cin >> N >> K;
  
  int64 pos = 0;
  for(int i = 1; i <= N; i++) {
    cin >> id[i];
    pos += i;
    if(pos >= K) {
      cout << id[i - (pos - K)] << endl;
      break;
    }
  }
}

C. Cinema

問題概要

 {n(1 \le n \le 20 000)} 人の科学者が それぞれ使える言語は  {a_{i}, (1 \le a_{i} \le 10^{9})} 1 つである. また, 映画が  m 個あり, 音声と字幕は違う言語で, それぞれ  {b_i, c_i (1 \le b_{i}, c_{i} \le 10^{9})} である.
1 つの映画を全員で見るとき, もっとも満足できる言語はどれか. 満足とは, 使える言語と音声の言語が一致する人数の多さで, もしそれが等しければ, 使える言語と字幕の言語の一致する人数の多さのことである.

解法

それぞれの映画ごとに, 音声言語を使える人数, 字幕言語を使える人数が分かればそのままなので, map で数える.

ソース

unordered_map 使ったら TLE で落ちた悲しい. 下はそれを map にしただけのやつ.

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

int64 N, A[200000], M, B[200000], C[200000];
map< int, int > people;

int main()
{
 
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    people[A[i]]++;
  }
  cin >> M;
  for(int i = 0; i < M; i++) {
    cin >> B[i];
  }
  for(int i = 0; i < M; i++) {
    cin >> C[i];
  }
  
  pair< pair< int, int >, int > ret = {{0, 0}, 1};
  for(int i = 0; i < M; i++) {
    ret = max(ret, {{people[B[i]], people[C[i]]}, i + 1});
  }
  cout << ret.second << endl;
}

D. Magic Powder

問題概要

1 枚のクッキーを作るには,  {n (1 \le n \le 100 000)} 種類の材料がそれぞれ  {a_{i} (1 \le a_{i} \le 10^{9})} 必要である.
いま材料がそれぞれ  {b_{i} (1 \le b_{i} \le 10^{9})} ある. また魔法のパウダーが  {k (1 \le k \le 10^{9})} あって, これは任意の材料に代用できる.
クッキーは最大で何個作れるか求めよ.

解法

どうみても二分探索.
 x 個作れるかどうかを判定することを考える.
 x 個作るにはそれぞれ材料が  {a_{i} \times x} 必要である.
すると材料  i を作るのに足りない分は  {max(0, a_{i} \times x - b_{i})} であり, この和が  {k} 以下であれば作れることが明らかである.

ソース

オーバーフローに注意

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

int64 N, K, A[100000], B[100000];

bool calc(int64 mid)
{
  int64 dec = K;
  for(int i = 0; i < N; i++) {
    if(mid * A[i] > B[i]) {
      dec -= mid * A[i] - B[i];
      if(dec < 0) return(false);
    }
  }
  return(true);
}

int main()
{
  scanf("%I64d %I64d", &N, &K);
  for(int i = 0; i < N; i++) {
    scanf("%I64d", &A[i]);
  }
  for(int i = 0; i < N; i++) {
    scanf("%I64d", &B[i]);
  }
  int64 low = 0, high = 1LL << 31;
  while(high - low > 0) {
    int64 mid = (low + high + 1) / 2;
    if(calc(mid)) low = mid;
    else high = mid - 1;
  }
  printf("%I64d\n", low);
}

E. Correct Bracket Sequence Editor

問題概要

CBS を以下のように定める.

  • 空文字列はCBS
  • 文字列  sCBSであるとき、 {'('+s+')'}CBS. このとき追加した  {'(',')'} は対応する括弧である.
  • 文字列  s tCBSであるとき、 {s + t}CBS

長さ  {n (1 \le n \le 500 000)}CBS に対して, ある初期位置  {p (1 \le p \le n)} から次のような文字で操作をする.

  • 'L':  p を左に 1 移動する
  • 'R':  p を右に 1 移動する
  • 'D':  p 番目の括弧とそれに対応する括弧, 及びその間にある括弧をすべて取り除く. その後  p の右側に括弧かあれば,  p を1個右にずらし, なければ1個左にずらす.

長さ  {m (1 \le m \le 500 000)} の操作履歴が与えられるので, 最終的にできる CBS を求めよ.

解法

すべての対応する括弧はスタックを使ってえいってやれば, 簡単に  O(n) で求まる.  {i} 番目の文字に対応する括弧の位置をそれぞれ  {b_{i}} とする.

'L'と'R' は簡単そうなので, 'D' の操作について考える.
'D' はすなわち, 区間   {\lbrack \min(i, b_{i}), \max(i, b_{i}) \rbrack } を削除するクエリそのものである.
segtree やらなんとか木やら怖いデータ構造を使っても出来そうだけど,  p の移動の実装が闇になるので, もうちょっと簡単なものを考えようとすると, 双方向リストが使えそうなことが分かる.
双方向リストは, 隣接要素への移動と任意位置への挿入削除が O(1) でできるデータ構造として一般的に知られている.(類題: バトンリレーゲーム | Aizu Online Judge )
これを配列で実装する.  i 番目の要素の左隣( {l_i} とする)と右隣( {r_i}とする)を持たせておく. 区間 {\lbrack L, R \rbrack } の削除は, {L-1}の右隣と {R+1}の左隣が変化することと同値なので,  {r_{l_{L}} = r_{R}} {l_{r_{R}} = l_{L}} を行えばよい.

ソース

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

int N, M, P;
string S, T;
int prv[600000], nxt[600000], build[600000];

int main()
{
  cin >> N >> M >> P;
  cin >> S;
  cin >> T;
  S = "*" + S;
  for(int i = 0; i < S.size(); i++) prv[i] = i - 1;
  for(int i = 0; i < S.size(); i++) nxt[i] = i + 1;
  
  stack< int > ss;
  ss.push(0);
  for(int i = 1; i < S.size(); i++) {
    int now = ss.top();
    if(S[i] == '(') {
      ss.push(i);
    } else {
      build[i] = now;
      build[now] = i;
      ss.pop();
    }
  }
  for(char query : T) {
    if(query == 'L') {
      P = prv[P];
    } else if(query == 'R') {
      P = nxt[P];
    } else {
      int s = min(P, build[P]);
      int t = max(P, build[P]);
      nxt[prv[s]] = nxt[t];
      prv[nxt[t]] = prv[s];
      if(nxt[t] == S.size()) P = prv[s];
      else                   P = nxt[t];
    }
  }
  string ret = "";
  int ptr = 0;
  while(ptr != S.size()) {
    if(ptr != 0) ret += S[ptr];
    ptr = nxt[ptr];
  }
  cout << ret << endl;
}

Fはね、眠くてまともな考察ができなかった.(そもそも追加される番号が固定なことすら考察できなかった)