問題リンク

Tasks - AtCoder Beginner Contest 106

はじめに

この記事では、各問題の考えの流れが大まかに書かれている。後述するが、3完だったためD問題のみ少し深めに書いた。

問題へのリンクは上の目次等を活用してほしい。

結果

今回は3完2WAで788位だった。

f:id:task4233:20180819112825p:plain

最近のコンテストはダメダメなので、悲しくなってくる。

それはさておき、改めて問題を見直してみると双子コンとしてはそこまで邪悪でなかったように感じた。

このコンテストは全完したかった……

問題

A - Garden

算数の問題。
(A - 1) * (B - 1) で、解が求められる。

ちなみに、灰色の部分の面積は
A * B - (A - 1) * (B - 1) と書くとバグが少なそう。

B - 105

「N以下の奇数oに対して、約数をちょうど8つ持つoの数を求めよ」という問題。

「奇数oが約数をちょうど8つ持つこと」は、
「 $\sqrt{o}$ 以下に、oを割り切れる数がちょうど4つ存在すること」と同義である。

したがって、oという奇数をforループで回し、
$\sqrt{o}$ までで割り切れる数を数えるために更にforループで回すので、
$O(N\sqrt{N})$ で解くことができた。

C - To Infinity

問題を見て、非常に大きな回数だけ変化することから、 K文字目までに1があるか否かを判定すれば良いということはすぐにわかった。

ただし、K文字目までを探索範囲にしてしまうと範囲外アクセスをしかねないので、右端の要素はstd::max(K, S.size())とした。

D - AtCoder Express 2

ACできなかった問題。
少し詳しめに書く。

問題文

N個の都市とM本の電車が存在している。
M本の電車のうちの電車iは $L_i$ から $R_i$ の閉区間を走っている。
ここで、都市番号pと都市番号qが与えられた時、走る区間が完全に含まれる列車の本数、
言い換えれば $p_i ≦ L_j$ かつ $R_j≦q_i$ が成立するような列車の本数について、Q個の質問にそれぞれ答えよ。

制約

1 ≦ N ≦ 5 $\times$ 10²
1 ≦ M ≦ 2 $\times$ 10⁵
1 ≦ Q ≦ 1 $\times$ 10⁵
1 ≦ $L_i ≦ R_i$ ≦ N (1 ≦ i ≦ M)
1 ≦ $p_i ≦ q_i$ ≦ N (1 ≦ i ≦ Q)

方針決め

厄介なのは、「1 ≦ Q ≦ 1 $\times$ 10⁵」であること。
すなわち、クエリを受け取ってからできる操作は高々「10²〜10³程度」しかないということである。

したがって、事前に与えられたデータに処理を加えて、O(1)からO(10³)程度で解を求められるようにする必要がある。

事前に行うデータ処理の方針を立てる

前処理の1つとして、累積和を取るという方法がある。
累積和を取れば、O(1)で区間[ $p_i$ , $q_i$ ]に含まれる列車の本数を求めることが可能となる。

まず、累積和を取る下準備として二次元配列d[MAX_N][MAX_N]を用意する。
各要素の意味は、
d[列車jの停車駅の左端 $L_j$ ][列車jの停車駅の右端 $R_j$ ] である。

そして、この配列の累積和を取っていく。
累積和の取り方については、親切にも問題文にヒントが書かれていた。
それは、

都市 $p_i$ から都市 $q_i$ までの区間に, 走る区間が完全に含まれる列車の本数.
言い換えれば, $p_i ≤ L_j$ と $R_j ≤ q_i$ が両方成りたつような列車jの本数.

という部分である。

ここから、累積和の取り方は、

$L_j$ について、前に積み上げる
(なぜなら、 $L_j$ が $p_i ≤ L_j$ を満たしているとき、同時に $L_j$ +1 も $p_i ≤ L_j$ +1を満たしているため)
$R_j$ について、後ろに積み上げる
(なぜなら、 $R_j$ が $R_j ≤ q_i$ を満たしているとき、同時に $R_j$ -1も $R_j$ -1 $≤ q_i$ を満たしているため)

という方針が立つ。

実装する

以上の内容を実装すると、以下のようになる。

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)

const int MAX_N = 575;

// d[l][r]
int d[MAX_N][MAX_N];

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

  CIN(N, M, Q);
  REP(i, M) {
    CIN(L, R);
    L--; R--;
    d[L][R]++;
  }

  // 後ろから前に積み上げる(iはNから0に下がっていく)
  RREP(i, N + 1) {
    REP(j, N + 1) {
      d[i][j] += d[i + 1][j];
    }
  }

  // 前から後ろに積み上げる(jは0からNに上がっていく)
  REP(i, N + 1) {
    REP(j, N + 1) {
      if (j > 0) {
    d[i][j] += d[i][j - 1];
      }
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    p--; q--;
    cout << d[p][q] << endl;
  }

  return 0;
}

別解法(BIT)

BITを二次元で持つことでもっと簡単にかける。
BITについては蟻本やslideshareを漁れば良いと思う。

以下、ソースコード。

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

template< class Abel > class BIT {
public:
  BIT(int _n) : N(_n) { init(); }

  void init() {
    // [1, N]の範囲なので、+1する必要がある
    bit.clear();
    bit.resize(N + 1, 0);
  }

  void add(int i, Abel x) {
    while (i <= N) {
      bit[i] += x;
      i += i & -i;
    }
  }

  Abel sum(int i) {
    Abel sm = 0;
    while (i > 0) {
      sm += bit[i];
      i -= i & -i;
    }
    return sm;
  }

  Abel getSum(int _x, int _y) {
    return sum(_y) - sum(_x - 1);
  }

private:
  int N;
  vector< Abel > bit;
};



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

  CIN(N, M, Q);
  vector< BIT< int > > bit(N + 1, BIT< int >(N + 1));

  REP(i, M) {
    CIN(L, R);
    REP(j, L + 1) {
      bit[j].add(R, 1);
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    cout << bit[p].sum(q) << endl;
  }
  
  return 0;
}

感想

コンテスト中のコードを見てきたが、方針は正しかったのに、実装でiとjの添字を逆にしたり、ループの向きを逆にしたりしていた。

先ほど見たときは割とすぐに見つけられたので、コンテスト中の焦りで目が曇ったのだろうと思う。

本番に弱いというよりかは、場数が少ないことによるものだと思うので、今後は積極的に海外コンにも参加しようと思う。

task4233のめも

書きたいことをつらつらと

ABC106 - 参加記録