連続開催ABCの2日目である．しばらくABCはなさそうに見える．

結果

問題	ACまでに要した時間	AC
A	0:49	1
B	3:40	1
C	21:06	1
D	54:37	1

Rating	順位
671 (+34)	3481

解答

C

計算量は $\mathcal{O} \left(N+M\right)$ でいけそうだなと思ったので，双方向グラフとして道を表現して全探索した．
submitでは vector<bool> visitで到達した $H_i$ を記録していたけど，よく考えたらNGじゃない（道がつながっているHよりも高い） $H_i$ のみをリストアップすれば答えは求められた．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<ll> H(N);
  REP(i, N) { cin >> H.at(i); }

  vector<vector<int>> path(N);
  int a, b;
  REP(i, M) {
    cin >> a >> b;
    --a;
    --b;
    path.at(a).push_back(b);
    path.at(b).push_back(a);
  }

  int ans = 0;
  vector<bool> visit(N, false);
  REP(i, N) {
    if (path.at(i).size() == 0 || visit.at(i)) {
      continue;
    }

    visit.at(i) = true;
    ll h = H.at(i);
    bool highest = true;

    for (int const &d : path.at(i)) {
      if (H.at(d) >= h) {
        highest = false;
        break;
      }
    }
    if (highest) {
      for (int const &d : path.at(i)) {
        visit.at(d) = true;
      }
      ++ans;
    }
  }

  REP(i, N) {
    if (!visit.at(i)) {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

D

$X$ の最大値は10⁹なのでビビってしまうが，よく考えれば100を5乗するとその最大値よりも明らかに大きくなる．そのため直感的に探索範囲は大したことがないことが分かる．

また，仮に ${B}^5$ が10⁹だとすると， ${A}^5$ がとり得る最大値はたかだか $2 \times {10}^9$ である．よって，なので $-200 \leqq A, B \leqq 200$ の範囲を探索すればいいことになる．

しかしコンテスト中は，ここまでの考察があまりに短時間でできてしまったために，逆にビビって $[-1000,1000$ ]の範囲で全探索している．ビビらなければもっと早くACできたはず．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll X;
  cin >> X;

  vector<ll> A(1100), B(1100);
  REP(i, 1001) { A.at(i) = B.at(i) = pow(i, 5); }

  REP(i, 1001) {
    REP(j, 1001) {
      if (A.at(i) - B.at(j) == X) {
        cout << i << " " << j << endl;
        return 0;
      } else if ((-1) * A.at(i) - B.at(j) == X) {
        cout << -i << " " << j << endl;
        return 0;
      } else if (A.at(i) + B.at(j) == X) {
        cout << i << " " << -j << endl;
        return 0;
      }
    }
  }

  return 0;
}

E（解説AC）

解説読んでAC．

ポイントとしては一致させたい変数を事前計算しておく．

同じ $(i,j)$ に対して $A_i + A_j$ かつ $j-i$ を満たす組み合わせを数え上げれば解けるが，何も考えずに全探索すると $\mathcal{O} \left({N}^2\right)$ となりTLE．
そこで，以下のように変形した式の両辺をkey，valueにiまたはjを格納したmapにそれぞれ入れておくと，最終的に両者のkeyが一致するiまたはjの組み合わせを数えればよく， $\mathcal{O} \left(N \times log {N} \right)$ で解ける．

$\displaystyle j - i = A_j + A_i \\ \Leftrightarrow j - A_j = i + A_i \\$

このように分離する利点は，それぞれのmapのkeyが $i$ と $j$ にのみ依存し，両者が独立した集合になる点．つまり，それぞれのmapのkeyのみを比較し，valueに含まれているiまたはjの数を乗じるだけで組み合わせ数が分かるため計算がシンプルになる．

これがもしもとの条件のまま $j-i$ と $A_j + A_i$ をkeyとすると，valueにはiとjのpairのsetを入れておかねばならず，最後に組み合わせを数え上げる時の判定が面倒くさい．多分これでも解けなくはないが，空間計算量も増加するためメリットは無い．

ここで， $log {N}$ はmapへのinsertコストを考慮．最大要素数のvectorを用意してそこに格納していけば $\mathcal{O} \left(N \right)$ でも解ける気がする．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  map<ll, set<ll>> L;
  map<ll, set<ll>> R;
  ll a;
  for (ll i = 1; i <= N; ++i) {
    cin >> a;
    ll l = i + a;
    ll r = i - a;

    if (L.find(l) == L.end()) {
      set<ll> s;
      s.insert(i);
      L.insert(make_pair(l, s));
    } else {
      L.at(l).insert(i);
    }

    if (r > 0) {
      if (R.find(r) == R.end()) {
        set<ll> s;
        s.insert(i);
        R.insert(make_pair(r, s));
      } else {
        R.at(r).insert(i);
      }
    }
  }

  ll ans = 0;
  for (auto const &it : L) {
    if (R.find(it.first) != R.end()) {
      ans += it.second.size() * R.at(it.first).size();
    }
  }

  cout << ans << endl;

  return 0;
}

ダメだった点

Dに時間をかけすぎた．根拠のありそうな解析が済んだらさっさとsubmitした方が結果的に良かっただろうと思う．早い緑コーダーは30分程度でsubmitしていたのでそれぐらいで解けるべきであった．

良かった点

難易度が低めなABCだったと思うがそれでもとりあえずABCDの4完を達成できたのは良かった．Eも解ければもっと良かったが $\mathcal{O} \left({N}^2\right)$ 以外の解法が思いつかなかった．

おわりに

３ヶ月ぶりに最大レートを更新できた．
緑まであと129となり，平均+30のレートアップを5回達成すれば緑になれる．
こう書くとまだ道のりが長い気がするが，解ける問題を増やして一気にレートを100ぐらいポンと上げて緑入りするシナリオを狙いたい．
AtCoder ProblemsのBoot campを解いているのがいい感じに効いている．やはり数をこなさなければ自分のレベルだとABCで上に行けないことがよく分かる．

f:id:serihiro:20200504000558p:plain — 2020/05/03時点の進捗

seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC166

結果

解答

C

D

E（解説AC）

ダメだった点

良かった点

おわりに