ABC408振り返り

はじめに

AtCoder Beginner Contest 408にRated参加しました。

今回のまとめ

• 今回はA問題〜C問題を解いた
• 初実戦上でC問題正答
• 茶パフォが出た
• D問題以降は相変わらず理解不能

レザルト

• 6264位(Rated参加者内5534位)
• パフォーマンス453
• レーティング113→145(+32)

A - Timeout

A - Timeout
提出時間：9:37

今回1問目の150点問題です。今までの100点問題のようにはいきません。
とはいえ、村長がずっと起きているかどうかを問題文通りに判定するだけなので、さほど難しいことはありません。

150点問題をさほどやっていないこと、最近はDaily Trainingを休んでいることから、結構時間がかかっています。

A.cpp

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

int main() {
  int n, s;
  cin >> n >> s;
  bool wake = true;
  int old_t = 0;
  for (int i = 0; i < n; i++) {
    int t, t_diff;
    cin >> t;
    t_diff = t - old_t;
    if (t_diff >= (s + 0.5)) {
      wake = false;
    }
    old_t = t;
  }
  if (wake) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

B - Compression

B - Compression
提出時間：28:56(19:19)

今回2回目の150点問題です。setの仕様を検索していたら時間がかかってしまいました。
というか、結果出力が難しいという印象です。

B.cpp

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

int main() {
  int n;
  set<int> a;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int ain;
    cin >> ain;
    a.insert(ain);
  }
  cout << a.size() << endl;
  set<int>::iterator i = a.begin();
  while (i != a.end()) {
    if (i != a.begin()) cout << " "; 
    cout << *i++;
  }
  cout << endl;
  return 0;
}

C - Not All Covered

C - Not All Covered
提出時間：50:57(22:01)

これはアルゴ数学本でやった階差と累積和で出せるな、と判断しました。
とりあえず捻っているとはいえ、階差と累積和の基礎問題だなと思いました。

どちらかというと、C問題を実戦で解けたのが感動でした。
いままで解けなかったので。

階差で配列に入力し、累積和のうち一番低い値を結果として出すことで正解となりました。
眠気と混乱で変数名が変なことになっていますが気にしないでください。

C.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define rep1(i,n) for (ll i = 1; i <= (n); i++)

int main() {
  ll n, m;
  cin >> n >> m;
  vl g(n + 2);
  rep(i, m) {
    ll l, r;
    cin >> l >> r;
    g[l]++;
    g[r+1]--;
  }
  ll guardpoint = 0;
  ll attackpoint = 1e9;
  rep1(i, n) {
    guardpoint += g[i];
    if (guardpoint < 1) {
      cout << 0 << endl;
      return 0;
    }
    attackpoint = min(attackpoint, guardpoint);
  }
  cout << attackpoint << endl;
  return 0;
}

そしてD問題以降は

解けていません。というか、問題文が難しくて解けませんでした。

今後の方針

• アルゴ式の『数理素養』を引き続き進める
• アルゴ数学本や鉄則本の問題が難しいので、まずは予習として一通り読む
• 今後もコンテストには積極的に参加していきたいところ