ABC106

前書き

こんばんは。
さて、私は競プロ部の幽霊部員として2年半やってきたわけです。
言い訳するなら、プログラミングをいざ始めると他のことが手につかなくなるので薬みたいなもんかなと思って怖くて手が出せずにいたわけです。
ただ、そろそろ言い訳をしているわけにも行かなくなったのと、もうそろそろチャレンジできる力がついたのかな（ついたことを願いたい）というのと、矛盾しますが色々な面で力不足を感じたため、再出発です。まずはコンテストから始めて見ましょうや。ということで。
3度目の挑戦（遅い！）

ABC106

問題リンクは以下。
AtCoder Beginner Contest 106 - AtCoder

A - Garden

中学数学とかでやったことのある問題です。
（全体）-（道2本）+（道の重なった部分）
つまり
A * B - (A + B) + 1
ですよね。ということで。AC。

#include <iostream>
#include <cmath>
using namespace std;

int main(){
int A, B;
cin >> A >> B;
cout << A*B-A-B+1 << endl;
return 0;
}

B - 105

わかりにくいのですが、

・自分自身も約数に含む
・自分以外の約数は全て自分 / 2 以下の数

上記2点を踏まえて、

・約数の数の初期値は1
・自分 / 2 の数まできたら計算終了

ということにしました。記憶が飛んで初期値1にするのを忘れてカッコつけられなかった。AC。

#include <iostream>
using namespace std;

int main(){
  int N, n = 1, counter, ans = 0;
  cin >> N;
  while(n <= N){
    counter = 1;
    for(int i = 1; i < n/2; i++){
      if(n % i == 0)  counter++;
    }
    if(counter == 8)  ans ++;
    n += 2;
  }
  cout << ans << endl;
  return 0;
}

C - To Infinity

overflowとかTLEとお友達の初心者なので、「5000兆」の文字を見たときは半ば諦めモードでしたが、
よくよく考えてみると2^(5000兆) >> 10^18なので、
1以外が現れるかそうでないかで場合分けすれば良いのです。なぁんだ。AC出来て嬉し嬉し。

#include <iostream>
#include <string>
using namespace std;

int main(){
    string S;
    long long int K, sum = 0, s;
    cin >> S >> K;
    for(long long int i = 0;i < (long long int)S.size(); i++){
      s = S[i] - '0';
      if(s == 1)  sum++;
      else  break;
    }
    if(K <= sum)  cout << 1 << endl;
    else cout << s << endl;
    return 0;
}

D - AtCoder Express 2

真面目にやろうとしてTLEになる
→LiをソートしてLi < pjになったらカット、とかすればいいんじゃね？→もちろんTLE（なんならWAしてしまった）
解説読んでなんとなく理解した気がするので明日、というか今日解説ACなるものしてみようと思います。

累積和について

累積和というワードを初めて知ったので（恥ずかしい）軽く。
要は、「累積和計算」という前処理をすることで、全体の計算量を減らすことができる、という利点があるみたいです。
こちらのありがたい記事を参照しました。
paiza.hatenablog.com

今回は、Li と Ri という2つのパラメータがあるので、二次元平面で累積和を考えてみました。

・まず、LiとRiをパラメータとして、二元配列にどんどん足していきます
・次に、累積和をcとして、求めます。
・最後に、累積和を利用して計算します。p = 1かどうかでの場合分けも忘れずにやりましょう。p = 1の時には引き算は必要ありませんからね。

#include <iostream>
#include <vector>
using namespace std;

int main(){

  int N, M, Q, counter, L, R;
  cin >> N >> M >> Q;
  int p[Q], q[Q];
  int train[N][N], c[N][N];
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      train[i][j] = 0;
      c[i][j] = 0;
    }
  }

  /*累積和*/
  for(int i = 0; i < M; i++){
    cin >> L >> R;
    train[L-1][R-1]++;
  }
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(j == 0)
        c[i][j] = train[i][j];
      else
        c[i][j] = c[i][j-1] + train[i][j];
    }
  }
  /*累積和ここまで*/

  for(int i = 0; i < Q; i++){
    cin >> p[i] >> q[i];
  }

  for(int i = 0; i < Q; i++){
    counter = 0;
    for(int j = p[i] - 1; j < q[i]; j++){
      if(p[i] - 2 >= 0)
        counter += (c[j][q[i] - 1] - c[j][p[i] - 2]);
      else
        counter += c[j][q[i] - 1];
    }
    cout << counter << endl;
  }
  return 0;
}

解説AC出来た！
満足したのでこのまま下宿先へ帰ります。