AtCoder Beginner Contest 106

AtCoder Beginner Contest 106 - AtCoder

A - Garden

問題

A - Garden

考察

縦、横の長方形から縦、横の長方形と縦、横の長方形を切り取った残りの面積を求める。これらの長方形は平行移動しても残りの面積が不変であるから、端に寄せれば残りは縦、横の長方形となる。

コード

int main(){
  ll a,b;
  cin >> a >> b;
  cout << (a-1)*(b-1) << endl;
  return 0;
}

B - 105

問題

B - 105

考察

以上以下の奇数で約数を8個もつものの個数を答える。約数の個数をカウントする関数を書いて、ループで回せばよい。

コード

ll cnt_n(ll n){
  ll cnt = 0;
  for(int i = 1; i <= n; i++){
    if(n%i==0) cnt++;
  }
  return cnt;
}
 
int main(){
  ll n;
  cin >> n;
  ll cnt = 0;
  for(int i = 1; i <= n; i+=2){
    if(cnt_n(i)==8){
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

C - To Infinity

問題

C - To Infinity

考察

与えられた文字列に対し、1以外の文字は無限に付け足されると考えてよく、そのとき文字目に何が現れるかを答える。したがって左から順に見ていって文字目までに1しかなければ答えは1だが、それ以外の文字が現れたら即時にその文字が答えとなる。

コード

int main(){
  str s;
  cin >> s;
  ll k;
  cin >> k;
  REP(i,s.length()){
    if(s[i]!='1'&&k>i){
      cout << s[i] << endl;
      return 0;
    }
  }
  cout << 1 << endl;
  return 0;
}

D - AtCoder Express 2

問題

D - AtCoder Express 2

考察

区間に含まれる個の区間が与えられ、その後回別途与えられる区間内に、個のうちいくつの区間が含まれるかをそれぞれ答える。はまで大きくなりうるので、各クエリに対しては以下で答える必要がある。
各クエリに対してで答えるには、区間に含まれる区間の個数を配列としてもっておけばよい。この配列を効率よく計算する方法を考える。
個与えられる区間のうちの1つをとする。ここで、この区間が答えとしてカウントされるようなクエリの条件は、クエリをとしてである。したがって、これを満たすようなすべてのに対してを1加えるという操作を行えば、配列が完成する。しかし、これに必要なオーダーはとなって、個の区間に対して繰り返すには大きすぎる。
そこで、区間に対して加算されるの範囲は長方形であることに着目する。このような場合、累積和を用いるとオーダーを落とすことができる。と同じサイズの配列を用意し、先ほどの1加える範囲の最初にを、最後にを行ごとに置いておく。すると、の累積和を取っていけば求めたかったが現れる。の生成が、累積和の計算がなので間に合う。

コード

int main(){ll n,m,q;
  cin >> n >> m >> q;
  ll array[n][n+1];
  ll sum[n][n+1];
  fill(array[0],array[n],0);
  REP(i,m){
    ll l,r;
    cin >> l >> r;
    l--, r--;
    for(ll k = 0; k <= l; k++){
      array[k][r]++;
      array[k][n]--;
    }
  }
  ll val = 0;
  REP(i,n){
    REP(j,n+1){
      val += array[i][j];
      sum[i][j] = val;
    }
  }
  REP(i,q){
    ll p,q;
    cin >> p >> q;
    p--, q--;
    cout << sum[p][q] << endl;
  }
  return 0;

雑感

今回は運良くかなり好調で、24分で全完できました。累積和が使える問題の頻度は結構高い気がします。
継続は力なりなので、毎週参加していきたいです。