ABC398の振り返り

一応レート下げはしませんでした、それだけでも嬉しい
あと、投稿遅れてすみませんでした

A問題(diff:10)

面倒(c++では)
- $\lfloor \frac{N - 1}{2} \rfloor$ 個、= $2 - (Nmod2)$ 個、- $\lfloor \frac{N - 1}{2} \rfloor$ 個をこの順に連結して出力すれば良いです。
計算量は $O(N)$ です。
ACコード(pypy56ms,c++1ms)

N = int(input())
print('-' * ((N - 1) // 2) + '=' * (2 - N % 2) + '-' * ((N - 1) // 2))

AC時間:3:37

B問題(diff:46)

バケットを使うというだけで250点なるの何
それぞれの数の枚数カウントを管理して、違う2つの数の枚数が $3$ 以上、$2$ 以上という感じになってたらその場で Yes、全部探してもなかったらNoです。
計算量は $O(1)$ です。範囲for文使うと滅びるので気を付けてください
ACコード(1ms)

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

int main() {
  vector<int> cnt(14, 0);
  for(int i = 0; i < 7; i++) {
    int A;
    cin >> A, cnt[A]++;
  }
  for(int i = 1; i < 14; i++) {
    for(int j = 1; j < 14; j++) {
      if(i != j && cnt[i] >= 3 && cnt[j] >= 2) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

AC時間:6:48

C問題(diff:124)

BはCに勝り、CはBに劣る
std::mapやstd::setなどを使ってインデックスを管理し、ある数においてそのインデックスの個数が1個なら答えを更新していく、という感じです。
計算量は $O(NlogN)$ です。
ACコード(398ms)

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

int main() {
  int N;
  cin >> N;
  map<int, vector<int>> A;
  set<int> num;
  for(int i = 1; i <= N; i++) {
    int a;
    cin >> a, num.insert(a), A[a].push_back(i);
  }
  int ans = -1;
  for(int o : num) {
    if((int)A[o].size() == 1) {
      ans = A[o][0];
    }
  }
  cout << ans << endl;
}

AC時間:3:43

D問題(diff:746)

閃きがあれば400点
煙を一斉に動かすと時間がかかるので、イベントごとに不変なものを考えましょう。
もともとの問題では、焚き火と高橋君の位置が不変でした。では、煙の位置を固定し、焚き火と高橋くんを動かすというのはどうでしょうか。この場合、移動に関して前者 $O(N^2)$ 後者 $O(N)$ となり高速に処理できます。
最初に $(0, 0)$ に煙を生成し、その後 $S$ の左から順に焚き火と高橋くんを逆方向に動かし、その度焚き火の座標に煙を生成します。高橋くんのところに煙があるかはstd::setで高速に判定できます。
計算量は $O(NlogN)$ です。
ACコード(65ms)

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
//library end

p vec(char c) {
  if(c == 'N') {
    return make_pair(1, 0);
  }
  if(c == 'S') {
    return make_pair(-1, 0);
  }
  if(c == 'W') {
    return make_pair(0, 1);
  }
  return make_pair(0, -1);
}

int main() {
  int N, R, C;
  string S;
  cin >> N >> R >> C >> S;
  p fire = make_pair(0, 0), taka = make_pair(R, C);
  set<p> kemu;
  kemu.insert(make_pair(0, 0));
  for(int i = 0; i < N; i++) {
    p a = vec(S[i]);
    fire.first += a.first, fire.second += a.second, taka.first += a.first, taka.second += a.second, kemu.insert(fire);
    cout << (kemu.count(taka));
  }
  cout << endl;
}

AC時間:22:28

E問題(diff:1238)

インタラクティブという点もあり、整理ができませんでした。

F問題(diff:1033)

Manacherのアルゴリズムを学びたいと思います。

感想

瓦取り返せそうです。(パフォ927、レート694)
緑に早く行きたい