seri::diary::competitive_programming

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

ABC162

ABC 参戦記録 TODO

atcoder.jp

しばらく間が空いてしまったが再開する．大学院卒業して仕事に復帰したら競プロどころじゃなくなってしまっていた．これから本気だす．

今回はC問題でやらかしてめちゃくちゃ順位落とした．．情けない．

結果

問題 ACまでに要した時間 AC WA TLE
A 2:22 1 0 0
B 4:18 1 0 0
C 62:07 1 0 0
D : 0 0 1
Rating 順位
538 (-26) 7427

解答

A

#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;

  while (N > 0) {
    int n = N % 10;
    if (n == 7) {
      cout << "Yes" << endl;
      return 0;
    }
    N /= 10;
  }

  cout << "No" << endl;

  return 0;
}

B

#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;
  ll ans = 0;
  REPI(i, 1, N + 1) {
    if (i % 3 == 0 || i % 5 == 0) {
      continue;
    }
    ans += i;
  }

  cout << ans << endl;

  return 0;
}

C

#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 K;
  cin >> K;
  if (K == 1) {
    cout << 1 << endl;
    return 0;
  }

  map<pair<int, int>, int> memo;
  ll ans = 0;

  REPI(i, 1, K + 1) {
    REPI(j, 1, K + 1) { memo.insert(make_pair(make_pair(i, j), __gcd(i, j))); }
  }

  for (auto it : memo) {
    REPI(k, 1, K + 1) { ans += memo.at(make_pair(it.second, k)); }
  }

  cout << ans << endl;

  return 0;
}

D

TLE

#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;
  string S;
  cin >> N >> S;

  map<pair<int, int>, int> C;

  REP(i, N) {
    char i_c = S.at(i);
    for (int j = i + 1; j < N - 1; ++j) {
      if (S.at(j) != i_c) {
        C.insert(make_pair(make_pair(i, j), j - i));
      }
    }
  }

  ll ans = 0;
  for (auto it : C) {
    pair<int, int> i_j = it.first;
    // cout << i_j.first << ":" << i_j.second << ":" << it.second << endl;
    for (int k = i_j.second + 1; k < N; ++k) {
      if (k - i_j.second == it.second) {
        continue;
      }
      if (S.at(k) != S.at(i_j.first) && S.at(k) != S.at(i_j.second)) {
        ++ans;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

ダメだった点

レギュレーションでgcc C++は -O2 オプション指定なのにローカルでつけておらず，C問題のK=200のケースが3秒以上かかっていて必死に最適化していて時間を浪費してしまった．

atcoder.jp

レギュレーションに従い，今後は常に g++ -std=gnu++17 -Wall -Wextra -O2 でコンパイルする．

なお普段はaliasを張って使っている．

alias cp14="clang++ -std=c++14 -Wall -Wextra -O2"
alias cp11="clang++ -std=c++11 -Wall -Wextra -O2"
alias gp14="g++-9 -std=c++14 -Wall -Wextra -O2"
alias gp17="g++-9 -std=c++17 -Wall -Wextra -O2"

良かった点

gcdのメモ化を思いついたのは偉いが結局 \mathcal{O} \left({N}^3 \right) でも間に合ったので早すぎる最適化に過ぎなかった．

おわりに

前回-63,今回-26とレーティングを落としまくっていてかなり凹んでいる．しかしようやく仕事のペースにも慣れてきたので挽回していきたい．