ei1333の日記

ぺこい

Codeforces Round #370 (Div. 2)

Codeforces

こどふぉってunratedの回らしい. C解き終わって, D読んで分かんないなぁって思ってたら寝落ちしたみたい. 直前にやってた某プロコンで疲れた.

A. Memory and Crow

問題概要(というか直訳...)

{1} 行に {n(1 \le n \le 100\ 000)} 個の整数 {b_1, b_2, ..., b_n} が書かれている.

カラスは以下の手順によって, {a_{i} (1 \le i \le n, -10^9 \le a_i \le 10^9)} を定義している.

  • カラスは最初 {a_i} に {0} を設定する.
  • カラスはその後 {a_i} に {b_i} を足し, {b_{i+1}} を引き, {b_{i+2}} を足す を {n} 番目の数まで繰り返す. 従って, {a_i = b_i - b_{i+1} + b_{i+2} - b_{i+3} ...} である.

{a_1, a_2, ..., a_n} が与えられるので, {b_1, b_2, ..., b_n} を復元せよ.

解法

(サンプルだけ見て察して通しただけなんだけど)

定義より, {a_i + a_{i+1} = b_i} である.

但し {i=n} のとき {a_{i+1}} は存在しないので注意. {a_n = b_n} なのでそのまま.

これを実装すれば良い.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[100000];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for(int i = 1; i < N; i++) {
    cout << A[i] + A[i - 1] << " ";
  }
  cout << A[N - 1] << endl;
}

B. Memory and Trident

問題概要

二次元平面上を, 与えられた文字列 {s (1 \le |s| \le 100\ 000)} に従って移動する.

{'L'} は左, {'R'} は右, {'U'} は上, {'D'} は下に {1} 移動することを意味する.

文字列 {s} のうち任意の文字を置き換えることができる.

原点から開始し, 最終的に原点に戻ってくるようにできるか判定し, できるときは変更する文字数の最小を求めよ.

解法

移動回数が奇数のときは原点に復帰不可能. よって, 偶数のときのみを考える.

最終的な縦方向の距離 {LR} と, 横方向の距離 {UD} はそれぞれの文字数を数えることで計算できる.

まず {LR} か {UD} の小さい方を大きい方の逆方向の移動に充てる. すると, 小さい方の方向の移動量は {0} にできて, 大きい方の方向の移動量は残り {|UD-AD|} となる.

うち半分の文字の移動方向を反対にすれば, それも {0} にできる.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  string S;
  cin >> S;
  if(S.size() & 1) {
    cout << -1 << endl;
  } else {
    int x = 0, y = 0;
    for(char& c : S) {
      if(c == 'L') ++x;
      else if(c == 'R') --x;
      else if(c == 'U') ++y;
      else --y;
    }
    x = abs(x);
    y = abs(y);
    cout << min(x, y) + abs(x - y) / 2 << endl;
  }

}

C. Memory and De-Evolution

問題概要

長さ {x(3 \le x \le 100\ 000)} の正三角形がある.

この正三角形の一辺を選んで辺の長さを変更する操作を何度も行うことができる. ただしこのとき三角形の状態が保たれなければならない.

長さ {y(y \lt x)} の正三角形にするために必要な変更操作の最小回数を求めよ.

解法

{y} から {x} に戻すことを考えても, 問題は変わらないのでそっちを考える.

一回の操作でなるべく {y} を {x} に近づけたほうがよく, かつ三角形の状態を保つようにしたい. このことを考えると, 現在の三角形の最小の長さの辺を他の {2} 辺の和 {- 1} とするのが最も辺を伸ばすことが出来て最適.

計算量はよくわからないけど {O(\log x)} になるらしい.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int x, y;
  cin >> x >> y;

  vector< int > a(3, y);
  int ret = 0;
  while(a[0] < x || a[1] < x || a[2] < x) {
    a[0] = min(x, a[1] + a[2] - 1);
    ++ret;
    sort(begin(a), end(a));
  }
  cout << ret << endl;
}