ABC150

atcoder.jp

結果

問題	ACまでに要した時間	AC	WA	TLE
A	04:57	1	0	0
B	07:15	1	0	0
C	32:49	1	0	0
D	:	0	0	0

Rating	順位
unrated	1917

解答

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 K, X;
  cin >> K >> X;
  if (K * 500 >= X) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

B

そのまんま．substr使うのとどっちが速度的に速いのかは検証してないけど，決め打ちで条件並べた方が間違いが少なくていいかなと思っている．

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

  int ans = 0;
  REP(i, N - 2) {
    if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

C

next_permutationの使い方を調べていて時間がかかってしまった．N=8程度ならN!をそのまま計算しても間に合うが，これがN=50とかだともっと効率よく辞書順を求める方法を考える必要がある．

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

  vector<int> order(N, 0);
  REPI(i, 0, N) { order[i] = i + 1; }
  int seq = 1;
  string key = "";
  map<string, int> perm;
  do {
    key = "";
    REP(i, N) { key += to_string(order[i]); }
    perm.insert(make_pair(key, seq));
    ++seq;
  } while (next_permutation(order.begin(), order.end()));

  // for (auto e : perm) {
  //   cout << e.first << ":" << e.second << endl;
  // }

  int a, b;
  char tmp_c;
  string tmp_s = "";

  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  a = perm.at(tmp_s);

  tmp_s = "";
  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  b = perm.at(tmp_s);

  cout << abs(a - b) << endl;

  return 0;
}

D

全然わからなくて死亡．あとで検討．

ダメだった点

D問題が全く手が出なかった．年末年始に勉強した合同式もそうだが，競プロでは（整）数論に強くないと解けない問題が結構あるようだ．

良かった点

ABCまでは割とスムーズに解けるようになったという感覚が得られた．しかしD問題までコンテスト中にACできなければ緑にはいけないであろう．まだまだ力不足．

おわりに