ABC149

atcoder.jp

結果

開始時刻を間違えて20時40分ぐらいから慌てて解きはじめたのだが，後述するPCトラブルも相まって状況は最悪だった．

問題	ACまでに要した時間	AC	WA	TLE
A	46:21	1	1	0
B	71:41	1	3	0
C	81:23	1	0	0
D	:	0	0	0

Rating	順位
unrated	3118

解答

A

まさかのWAを決めてしまった．こんなもん何を間違える要素があるんじゃいと思うが問題文を焦って読んで出力する文字列の順序を間違えた．笑えない．

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

  string S, T;
  cin >> S >> T;

  cout << T << S << endl;

  return 0;
}

B

単純に考えれば以下のステップで解けるクッソ簡単なシミュレーションである．

• A = max(A-K, 0)
• A > K ? K = 0 : K = A - K
• B = max(B-K, 0)

しかし後述するように予期せぬ自体に焦っていたせいかWAを3回も出してしまった．A > KのケースでBが操作されないパターンを想定し忘れるとか，普段なら絶対やらないようなミスをしていた．これがratedなコンテストならこの時点でrating減少は避けられなかった．猛反省すべき結果である．．

#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 ans_0, ans_1, A, B, K;
  cin >> A >> B >> K;
  ans_0 = A;
  ans_1 = B;

  ans_0 = max(A - K, 0ll);
  if(A < K){
    K -= A;
    ans_1 = max(B - K, 0ll);
  }

  cout << ans_0 << " " << ans_1 << endl;

  return 0;
}

C

C問題まで来てようやく落ち着きを取り戻したのかこれはすんなり解けた． 素数判定をする処理はであり，2から10,000の範囲であれば次の素数に遭遇するまでインクリメンタルに素数を求めていっても大した計算量にはならないと判断してnaiveに実装すれば解ける問題．

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

bool is_prime(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return false;
    }
  }

  return true;
}

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

  int X;
  cin >> X;

  int ans;
  while (true) {
    if(is_prime(X)){
      ans = X;
      break;
    }else{
      ++X;
    }
  }

  cout << ans << endl;

  return 0;
}

ところで，{} な整数集合において，素数がどの程度の間隔で含まれる気になったので調べてみた．最小1，最大114，平均値12.74，中央値10，標準偏差10.28という結果となった．そのため，最悪ケースでも113回素数判定をすれば良く，計算量が113 * となったとして10⁵なので十分間に合うことが確認できた．

1から10⁶の範囲における素数を昇順で並べた時の前の素数との差分をplotした図．予行軸は素数の出現順を示し，縦軸は1個前の素数との差分を示す．最大で114であった．

雑な検証用コード．10⁶まで求めても手元のmacbook proで1秒未満で完了した．

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int n) {
  if (n < 4) {
    return true;
  }

  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  int seq = 1;
  int last_prime_number = -1;
  for (int i = 2; i <= 1000000; ++i) {
    if (is_prime(i)) {
      if (last_prime_number != -1) {
        cout << seq << ',' << i - last_prime_number << endl;
      } else {
        cout << seq << ',' << i << endl;
      }
      ++seq;
      last_prime_number = i;
    }
  }

  return 0;
}

D

ダメだった点

良かった点

おわりに

20時開始だったのを21時開始と間違えて盛大にやらかした．また，OSをCatalinaにアップデートした後にXCodeのアップデートを忘れていた為にローカルでC++のコードをコンパイルできないトラブルも発生した．その結果，散々な結果となった．システムトラブルでunratedになったのは不幸中の幸いであった．