1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ABC397の振り返り

Posted at

Writerてんこ盛り回(sotanishy,MtSaka,sounansya,kyopro_friends,blackyuki)
そしてレート下げええええええええええ

A問題(diff:不明)

最近ABでペナルティを食らうのが安定してきました。やったね(良くない)
条件分岐すれば行けます。計算量は $O(1)$ です。
ACコード(pypy54ms,c++1ms)

X = float(input())
if X < 37.5:
  print(3)
elif X < 38.0:
  print(2)
else:
  print(1)

AC時間:4:04

B問題(diff:不明)

深く考えすぎた
今見ているところの偶奇を管理していおいて、もしin/outと違う所があったら答えに1加算&偶奇反転すれば良いです。計算量は $O(|S|)$ です。
ACコード(1ms)

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

int main() {
  string S;
  cin >> S;
  int ans = 0, guki = 0;
  for(char s : S) {
    if((s == 'o') != guki) {
      ans++, guki = 1 - guki;
    }
    guki = 1 - guki;
  }
  cout << ans + ((int)S.size() + ans) % 2 << endl;
}

AC時間:35:36(…)

C問題(diff:不明)

Bより問題が分かりやすかった
要素ごとのカウントを持っておいて、それを1つずつ動かして、カウントが1以上の数の和を足したものをchmaxして行けばよいと思います。std::mapを使って $O(NlogN)$ 、制約の $1 \le A_i \le N$ から、std::vectorを使って $O(N)$ で解くことができます。
カウント関連の問題ではカウントが1以上かそうでないかが切り替わる瞬間に何かをすることが大切です。それを練習できる問題を載せておきます。
ABC391C
ACコード(58ms)

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

int main() {
  int N, tmp_1 = 0, tmp_2 = 0;
  cin >> N;
  vector<vector<int>> cnt(2, vector<int>(N + 1, 0));
  vector<int> A(N);
  for(int &o : A) {
    cin >> o, cnt[0][o]++;
    if(cnt[0][o] == 1) {
      tmp_1++;
    }
  }
  int ans = 0;
  for(int i = 0; i < N - 1; i++) {
    cnt[0][A[i]]--, cnt[1][A[i]]++;
    if(cnt[0][A[i]] == 0) {
      tmp_1--;
    }
    if(cnt[1][A[i]] == 1) {
      tmp_2++;
    }
    ans = max(ans, tmp_1 + tmp_2);
  }
  cout << ans << endl;
}

AC時間:6:01

D問題(diff:不明)

方程式を立式することはできましたが、そこからゴチャゴチャしてACできませんでした

感想

やばいですね(パフォ459、レート665)
かなり忙しいですが精進頑張ります

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?