AtCoder Beginner Contest 084 - takahiro_itazuriの公倍数的ブログ

はじめに
A - New Year
- 自分の解答
- 改善点
B - Postal Code
C - Special Trains
D - 2017-like Number
最後に

はじめに

AtCoderのBeginner Contest 084の解説と勉強です。
問題はこちらを参照してください。

A - New Year

四則演算をするだけの問題。
流石にこの問題ができない人はいないと思うので、解説はしません。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int M;
  std::cin >> M;

  std::cout << 24 + (24 - M);
  return 0;
}

改善点

特になし

B - Postal Code

入力が正しいか判定するタイプの問題。
今回の郵便番号以外にもパスワードに対して、似たような問題を見たことがあります。

自分の解答

char型は-128~127が割り当てられており、これらの数字は文字コードの一つであるASCIIコードを示しています。
ASCIIコードでは、0~9の数字の文字は48~57のコードが割り当てられているため、比較演算子を利用して大小判定をすることで、文字のチェックが行えます。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int A, B;
  string S;
  cin >> A >> B;
  cin >> S;

  bool bCheck = true;
  rep(i, A + B + 1) {
    if (i == A) {
      if (S[i] != '-') bCheck = false;
    }
    else {
      if ('0' > S[i] || S[i] > '9') bCheck = false;
    }
  }

  if (bCheck) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

改善点

上のコードでは、全部の文字を判定した後に、YesかNoかを出力しています。
しかし、正しくない文字が存在した時点でNoを出力し、終了すれば速く終了する可能性が高まります。

改善後のコード

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int A, B;
  string S;
  cin >> A >> B;
  cin >> S;

  rep(i, A + B + 1) {
    if (i == A) {
      if (S[i] != '-') { // 正しくない時点で終了する
        cout << "No" << endl;
        return 0;
      }
    }
    else {
      if ('0' > S[i] || S[i] > '9') { // 正しくない時点で終了する
        cout << "No" << endl;
        return 0;
      }
    }
  }

  // 最後まで来たら正しい
  cout << "Yes" << endl;
  return 0;
}

C - Special Trains

ここらへんから少し日本語をちゃんと読む必要が出てきました。
ですが、「最強最速アルゴリズマー養成講座」から言わせると、シミュレーションをするだけの簡単な問題です。

駅$i$に開通式開始$t$秒後に到達したとき、駅$i+1$に向かう列車に乗れるのが開通式開始何秒後かを考えると解けます。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int N;
  vi T;
	
  cin >> N;

  rep(i, N - 1) {
    int c, s, f;
    cin >> c >> s >> f;
		
    // 駅iが出発点の時に駅i+1に到着する時間
    T.pub(s + c);

    // 駅0～駅i-1を出発点とした場合に駅i+1に到着する時間
    if (i != 0) {
      rep(j, i) {
        // 最初の出発時間sから電車は時間間隔fで出発しているので
        // 駅iを出発する時間が駅iに到着時間を越すまでループを回す
        int buf = s;
        while (buf < T[j]) {
          buf += f;
        }
        // 駅iを出発する時間に駅i+1に着くまでの時間を足す
        T[j] = buf + c;
      }
    }
  }

  // 元々最後の駅にいた場合
  T.pub(0);

  rep(i, N) {
    cout << T[i] << endl;
  }

  return 0;
}

改善点

$S_i$は$F_i$で割り切れることが保証されていることを利用すると、上のコードのwhile文の部分を簡略化することができます。
現在時刻$t$に対して、$t$%$F_i$は駅$i$を最後に出た列車の発車時刻からの経過時間になります。
したがって、乗車する列車の発車時間は$t+F_i-t$%$F_i$で求めることができます。

f:id:takahiro_itazuri:20171231003630p:plain

改善後のコード

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int N;
  vi T;
	
  cin >> N;

  rep(i, N - 1) {
    int c, s, f;
    cin >> c >> s >> f;
		
    T.pub(s + c);

    if (i != 0) {
      rep(j, i) {
        //ここを訂正
        //while (buf < T[j]) {
        //	buf += f;
        //}

        int t = T[j];
        if (t < s) t = s;
        else if (t % f != 0) t = t + f - t % f;
        T[j] = t + c;
      }
    }
  }
  
  T.pub(0);

  rep(i, N) {
    cout << T[i] << endl;
  }

  return 0;
}

D - 2017-like Number

素数判定ができればできる問題。

自分の解答

僕は「合成数$x$（素数でない数）は$p \leqq \sqrt{x}$を満たす素因子$p$を持つ」性質と「素数は6の倍数の前後に存在する」性質を利用して、$[2, \sqrt{x}]$の範囲の数で$x$を割り切れるかを判定するコードを書きました。
しかし、TLE(Time Limit Exceeded)になってしまいました。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<math.h>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

bool check(int val) {
  if (val == 3) return true;
  if (val % 3 == 0) return false;

  int s = (int)sqrt(val);
  for (int i = 6; i - 1 <= s; i += 6) {
    if ((val % (i - 1)) == 0) return false;
    if ((val % (i + 1)) == 0) return false;
  }

  return true;
}

int main() {
  int Q;
  cin >> Q;
  vi count;

  rep(i, Q) {
    int c = 0;
    int l, r;
    cin >> l >> r;

    if (l <= 3) c++;
    if (((l + 1) % 4) == 0) { l += 2; }
    for (int q = l; q <= r; q += 4) {
      int p = (q + 1) / 2;
      //cout << "p = " << p << ", " << "q = " << q << endl;

      if (q == 1 || p == 1) continue;
      if (p == 2) continue;
      if (p % 2 == 0) continue;
      if (!check(p)) continue;
      if (!check(q)) continue;

      c++;
    }
		
    count.pub(c);
  }

  rep(i, count.size()) {
    cout << count[i] << endl;
  }

  return 0;
}

改善点

上のコードの場合、入力Qの数が増えていくにつれて、何度も素数であるか判定するため、時間が非常にかかります。

公式の解説には以下のようになっていました。
「エラトステネスの篩」を利用して、予め必要な素数を全て求めておきます。
次に$[3, 100000]$の範囲で条件を満たすものをメモしておきます。
さらに、そのメモに基づいて累積和を求めておきます。
累積和を利用することによって、特定の範囲内に何個条件を満たすものが存在するかがすぐに求めるようになります。
このアルゴリズムであれば、一度事前計算を終えると、各クエリに対して累積和の配列に2回アクセスし、差分を取るだけで良くなり、クエリの数が増加しても、計算量が急に増したりしなくなります。

改善後のコード

#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>
#include<math.h>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

bool f[100001];
int c[100002];
int N, L, R;

int main() {
  // 素数であるかどうか
  //   false: 素数である
  //   true : 素数でない
  for (int i = 2; i <= 100000; i++) {
    if (!f[i]) {
      for (int j = i + i; j <= 100000; j += i) {
        f[j] = true;
      }
    }
  }

  // 2017-like numberであるかどうか
  for (int i = 3; i <= 100000; i += 2) {
    if (!f[i] && !f[(i + 1) / 2]) c[i]++;
  }

  // 累積和
  for (int i = 3; i <= 100000; i++) {
    c[i] += c[i - 1];
  }

  scanf("%d", &N);
  vi result;
  while (N--) {
    scanf("%d %d", &L, &R);
    printf("%d\n", c[R] - c[L - 1]);
  }

  return 0;
}

最後に

問4の累積和をメモしておく方法は非常に勉強になりました。
今回はここで終わります。