競技プログラミング練習記 No.57【ABC106練習】

初回 -> はじめに

ABC106を解きました。
4完です！
D問題は解説を見て解きました。

問題	時間	アルゴリズム	実行時間
A	1min	-	6ms
B	6min	約数	6ms
C	5min	-	9ms
D	-	二次元累積和	57ms

まとめ

先にまとめを載せます。これ自体は最後に書いてます。

Nがiで割り切れた時、NはN/iでも割り切れますね。
つまり、「N以下のの約数が8個」は「√N未満の約数が4個」と言い換えることができます。

二次元累積和についてはこちらのページの「4. 二次元累積和」がわかりやすかったです。
累積和を何も考えずに書けるようにする！

A - Garden

  int a, b;
  cin >> a >> b;
  cout << (a - 1) * (b - 1);

道をずらして畑の端にもってきた場合の面積と求める面積は同じですね。
この時の面積は縦横それぞれA-1とB-1になります。

B - 105

  int n;
  cin >> n;
  int ans = 0;
  int num = 1;
  while(num += 2, num <= n)
  {
    int cnt = 1;
    for(int i = 3; i * i < num; i += 2)
    {
      cnt += (num % i == 0);
    }
    ans += (cnt == 4);
  }
  cout << ans;

約数が8個なので、実際に割り切れた数字の個数を数えます。
また、Nがiで割り切れた時、NはN/iでも割り切れますね。
つまり、「N以下のの約数が8個」は「√N未満の約数が4個」と言い換えることができます。
平方数を除くため、√N「未満」であることに注意です。

見るべき数は奇数であることから、コードではfor文の範囲を調整して少し高速化しています。

C - To Infinity

  string s;
  ll k;
  cin >> s >> k;
  for(int i = 0; i < k; ++i)
  {
    if (s[i] != '1')
    {
      cout << s[i];
      return;
    }
  }
  cout << s[k - 1];

5000兆回繰り返します。
例えば2は長さが2倍ずつ増えていくので、5000兆回繰り返した後の長さは2^5000兆ですね。
Kの上限は10^18ですが、2^5000兆はこれを余裕で超えています。
1のみが長さが変わりません。

つまり、Sを先頭から見ていって、1以外が来ればその値が答えになります。
K文字目まですべて1であれば、答えは1になります。

D - AtCoder Express 2

int dp[505][505];

  int n, m, q, l, r, ql, qr;
  cin >> n >> m >> q;
  for(int i = 0; i < m; ++i)
  {
    cin >> l >> r;
    dp[l][r]++;
  }

  for(int y = 1; y <= n; ++y)
  {
    for(int x = 1; x <= n; ++x)
    {
      dp[y][x] += dp[y][x - 1];
    }    
  }

  for(int x = 1; x <= n; ++x)
  {
    for(int y = 1; y <= n; ++y)
    {
      dp[y][x] += dp[y - 1][x];
    }    
  }

  for(int i = 0; i < q; ++i)
  {
    cin >> ql >> qr;
    ql--;
    cout << dp[qr][qr] - dp[ql][qr] - dp[qr][ql] + dp[ql][ql] << endl;
  }

dp[l][r]には、区間[l, r]より前に区間が終わる電車の本数が入ります。
例えば、dp[3][4]には[1,2][2,3][1,4]などの区間が含まれます。

これは二次元累積和という考え方を使っています。
二次元平面で考えて、dp[l][r]には座標(0, 0)と座標(l, r)を通る長方形の内側にある電車の本数が入ります。
クエリでql, qrが与えられたときは、座標(ql, ql)と座標(qr, qr)を通る長方形の内側にある電車の本数が答えになります。

これを求めると
dp[qr][qr] - dp[ql - 1][qr] - dp[qr][ql - 1] + dp[ql - 1][ql - 1]
という式になり、答えがわかります。

二次元累積和についてはこちらのページの「4. 二次元累積和」がわかりやすかったです。
累積和を何も考えずに書けるようにする！

以上です。ありがとうございました。