AtCoder Beginner Contest 102

はじめに

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

A - Multiple of 2 and N

Aはいつも通り簡単です。$N$が$2$の倍数となるときだけ注意です。

自分の回答

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

int N;

int main() {   
  scanf("%d", &N);
  if (N % 2 == 0) printf("%d\n", N);
  else printf("%d\n", N * 2);
  return 0;
}

改善点

特になし。

B - Maximum Difference

Bも簡単です。
入力を受け取ったら、順次最大値を最小値を更新し、最後にそれらの差を出力します。

自分の回答

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

using namespace std;

using ull = unsigned long long;
using vi = vector<int>;

int N;
int minval, maxval;

int main() {
  scanf("%d", &N);

  minval = 1000000001, maxval = -1;
  int buf;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &buf);
    if (buf < minval) minval = buf;
    if (buf > maxval) maxval = buf;
  }

  printf("%d\n", maxval - minval);  
  return 0;
}

改善点

特になし。

C - Linear Approximation

Cも簡単なはずだったのですが、勘違いをしてしまったせいで時間のすべてを溶かしてしまいました。

まず最初に気づくべき点は、以下のように考える点です。
$$ abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + \cdots + abs(A_N - (b+N)) \\ = abs((A_1 - 1) - b) + abs((A_2 -2) - b) + \cdots + abs((A_N - N) - b)$$
したがって入力を受け取った時点で引き算をしてしまい、$B_n = A_n - n$という整数列$B$に対して、以下を最小化する問題に帰着させます。
$$ abs(B_1 - b) + abs(B_2 - b) + \cdots + abs(B_N - b) $$

自分の回答

今回僕がはまってしまったのは、この最小化を実現する$b$が整数列$B$の平均値だと勘違いしてしまったということです。この回答で提出すると、特定の問題においてWAとなってしまいます。基本的になぜWAなったかは自分で気づかなけらばいけなく、時間中には平均を出すときの桁落ちなどの誤差やオーバーフローなどを直し続けているうちに終了してしまいました。

改善点

なんでこのミスに気づかなかったのか。

ここでは簡単のため、最小化したい目的関数を$f(b)$としておきます。まずは平均ではうまく行かない例をあげようと思います。整数列$B=\left\{ -5, -4, 5 \right\}$のとき、平均は$-2$であるため$f(-2)=12$であり、中央値は$-4$であるため$f(-4)=10$となり、平均がうまく行っていないことがわかります。

なぜこんなことが起こるかを考えましょう。先程よりさらにわかりやすい例として、$B=\left\{-6, -6, 6 \right\}$を考えたとき、平均は$-3$、中央値は$-6$です。まず、$-6$から$6$の間の値を取るべきであることは簡単にわかると思います。また$-6$と$6$の間のテキトーな数$b$を選んだとき、最初の$-6$と$b$の差の絶対値と$6$と$b$の差の絶対値を足すと$12$になることがわかります。したがって、２つ目の$-6$までの距離を最小にする数のが良いのです。その結果、$-6$を選ぶことが正解であることがわかります。

もう少し考察してみましょう。先程の整数列$B$に新たに$4$を加えて、$B=\left\{-6, -6, 4, 6 \right\}$としてみましょう。先程と同じように$b$が$-6$以上$6$以下であることは容易にわかります。先程と同様にこの場合、$-6$と$b$の差の絶対値と$6$の差の絶対値の和は$12$で一定となることがわかります。したがって、新たな整数列$B'=\left\{ -6, 4 \right\}$を考え、これらとの差の絶対値の総和を最小化させる問題に帰着させることができます。このような論法を繰り返すことによって、最終的に$B'$の要素を２つか１つにすることができます。要素が１つとなった場合は、その値自体が答えであり、要素が２つだった場合でも、その差の絶対値の総和は変化しないので、どちらを答えても$f$の値は変わりません。

このように整数列の端から１要素ずつ削っていく作業を繰り返すことは中央値を求めることに等しくなります。したがって、本問題は中央値を取ればよいのです。

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

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define REP(i,n) FOR(i,0,n)

int N;
int A[200000];

int main() {
  scanf("%d", &N);
  REP(i,N) {
    scanf("%d", &A[i]);
    A[i] -= (i + 1);
  }

  sort(A, A+N);
  int med = A[(N/2)];
  
  unsigned long long result = 0;
  REP(i,N) result += abs(A[i] - med);
  printf("%llu\n", result);
  return 0;
}

今回の問題のように最初から難しい入力を考えるのではなく、最小のセットから問題を解いてみることが非常に重要になることが多々あります。

D - Equal Cut

Dは配点が600点だった割には簡単な問題でした。整数列$A$を４つに切り分けて、各領域ごとの総和の差が最小になるような切り分け方を応える問題でした。

自分の回答

今回はCに時間をかけてしまって、Dを解くことができませんでした。

改善点

このような複数のものを同時に最適化する問題は、小問題に帰着できることがほとんどです。

２つの領域に分けるという問題であれば、左右の領域の差が最小となるように、仕切りを左から線形探索していきます。今回与えられているのは整数列であるため、左から線形に探索していくと、左側の和は単調に増えていき、右側の和は単調に減っていきます。したがって、左側の和が右側の和より大きくなる手前か直後が差を最小化する場所になります。

ここで元の問題に戻りますと、４つの領域に分けるためには、３つの仕切りが必要であり、もし仮に真ん中の仕切りの場所が決まったとした場合、その真ん中の仕切りの左右の領域において、それぞれもう１つの仕切りを作ることとなります。このように真ん中の仕切りさえ決まれば簡単に解けることがわかります。

それでは真ん中の仕切りをどうやって決めるかとなるのですが、これは線形探索で構いません。ただし、線形探索ですべての計算を行うには、若干のテクニックが必要となります。

テクニックの１つ目は特定の領域の総和の計算は$O(1)$で計算する方法です。本来であれば総和はすべての要素にアクセスする必要があるため$O(N)$の計算量が必要です。ですが、今回のような値が変化しない配列を対象とする場合、事前に累積和配列$B$を用意しておくことで、領域の最初のインデックス$i_{start}$と$i_{end}$がわかったとき、その領域に含まれる全要素の和は$B[i_{end}] - B[i_{start}]$で求めることができ、この計算量は$O(1)$です。

テクニックの２つ目は余計な要素を探索する必要はないということです。真ん中の仕切りを１つずつずらしていくとき、その真ん中の仕切りによって区切られる２つの領域のうち、左側は単調に増え、右側は単調に減っていきます。したがって、左右の領域を更に分ける際には１つ前のとき求めた仕切りの位置から探索し始めてよいことがわかります。具体的に見るために、左側の領域に着目すると、１つ前のときに求めた答えは左右の和の差が最小となるように求められており、今回真ん中の仕切りが１つ左に移動したことにより、左側の領域の右側の和が大きくなったことがわかります。したがって、前回の求めた仕切りの位置から再度探索しても良いことがわかります。

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<limits>
using namespace std;
using uint = unsigned int;
using ll = long long;

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define REP(i,n) FOR(i,0,n)

uint N;
ll A[200001];
uint l, c, r;

ll getVal() {
  ll prev_diff, curr_diff;
  ll cval = A[c], eval = A[N];

  // left side
  prev_diff = numeric_limits<ll>::max();
  while (1) {
    curr_diff = abs((cval - A[l]) - (A[l] - 0));
    if (curr_diff > prev_diff) {
      --l;
      break;
    }

    prev_diff = curr_diff;
    ++l;
    if (l >= c) {
      --l;
      break;
    }
  }

  // right side
  prev_diff = numeric_limits<ll>::max();
  while(1) {
    curr_diff = abs((eval - A[r]) - (A[r] - cval));
    if (curr_diff > prev_diff) {
      --r;
      break;
    }

    prev_diff = curr_diff;
    ++r;
    if (r >= N) {
      --r;
      break;
    }
  }

  // calc val
  ll sum[4];
  sum[0] = A[l] - 0;
  sum[1] = cval - A[l];
  sum[2] = A[r] - cval;
  sum[3] = eval - A[r];
  ll maxval = *max_element(sum, sum+4);
  ll minval = *min_element(sum, sum+4);
  return maxval - minval;
}

int main() {
  scanf("%u", &N);

  A[0] = 0;
  REP(i,N) {
    scanf("%llu", &A[i+1]);
    A[i+1] += A[i];
  }

  ll minval = numeric_limits<ll>::max();
  for (l = 1, c = 2, r = 3; c <= N - 2; ++c) {
    if (r <= c) r = c + 1;   
    ll val = getVal();
    if (val < minval) minval = val;
  }

  printf("%llu\n", minval);
  return 0;
}

総評

Cでの勘違いが大きなミスとなってしまいました。今回はDもそこまで難しくなかったため、本当に悔しいです。リアルタイムで問題に挑戦している時は、ある程度諦めも必要で、次の問題に切り替えていくことも重要であると思いました。次回からはそのようにしていこうと思います。

修行のために古い問題も解くことにしました。

それに際して、GitHubリポジトリを作成しました。GitHubページでは、僕が解いたこれまでのコードをすべて見ることができます。またtips.mdには競技プログラミングをするときの使える技を（英語ですが）公開しています。随時こちらも更新していく予定です。GitHubに公開してあるコードはコメント等はほとんどなく、かなり最適化されたものとなっていますので、詳しい解説をご覧になりたい方は引き続き、こちらのブログも見ていただけたらと思います。

前回コメントをくださった方がいらっしゃって、非常に嬉しく思いました。
もし私の記事を見て良かったと思ってくださったら、是非「スター」をつけていってください。また読者登録もよろしくお願いします。今後の活動を続けていくモチベーションになります。