ABC406 B, C問題の別解法（C言語）

ABC406で解説解とは違う方法を説明してみます。自分が理解して解いた方法であるということで、この方法が良いというわけではありません。

B問題

• 1≦N≦100
• 1≦K≦18
• 1≦A_i≦10^K

で、A_iをi=1～Nまで掛け算していく。ただし、計算中に桁がKを超えたら1にする。

ここで、計算結果<10¹⁹なので、long longでいいが、計算中に桁がKを超える場合というのをどうやって判定するか、が問題。計算結果の桁数がKを超えるとlong longでは扱えない。

計算を桁ごとにやっていくことにすれば、各桁の値が0～9の配列で計算できるので、それでやっていく。計算は筆算の手順で行う。

まず、整数を0～9の各桁の配列にしていく。表示桁を1で初期化する。

  int disp[k];                  /* display digit */
  for (int i = 0; i < k; i++)
    disp[i] = 0;
  disp[0] = 1;                  /* initialize */

A_iを入力して、K桁のdigitに分解して、各桁を配列に入れていく。なお、以降はＮ回の繰り返しループの中で行う。

  int ai;
  scanf("%d", &ai);             /* get multiplier */
  int a[k];                     /* multiplier digit */
  for (int i = 0; i < k; i++) {
  	a[k] = ai % 10;
  	ai /= 10;
  }

配列どうしを筆算の要領で掛け算していく。

  int m[k*2];                   /* result digit */
  for (int i = 0; i < k*2; i++)
    m[i] = 0;
  for (int i = 0; i < k; i++) {
  	for (int j = 0; j < k; j++) {
  	  int tmp = disp[i] * a[j];
  	  m[i+j] += tmp % 10;       /* add lower digit */
  	  m[i+j+1] += tmp / 10;     /* carry add to upper digit */
  	}
  }

掛け算の結果がK桁をオーバーフローしているか判断する。

  int ovf = 0;
  for (int i = k; i < k*2; i++) {   /* for over k */
    if (m[i] > 0)               /* exist over k digit */
      ovf = 1;
  }

オーバーフローしていなければ、K桁以下を表示する。オーバーフローしている場合は1のみ表示する。

  if (ovf == 0) {               /* not overflow */
  	for (int i = 0; i < k; i++) /* copy k digits to disp */
  	  disp[i] = m[i];
  } else {
  	for (int i = 0; i < k; i++) /* clear k digits */
  	  disp[i] = 0;
  	disp[0] = 1;                /* reset value = 1 */
  }

Ｎ回の掛け算が終わったら、上位桁から表示していく。このとき、上位桁の0は表示しないようにする。

  int z = 0;                    /* zero digit flag */
  for (int i = 0; i < k; i++) {
    if (z == 0 && disp[(k-1) - i] == 0)
      continue;                 /* not display zero value */
    printf("%d", disp[(k-1) - i]);
    z = 1;                      /* once none zero, set 1 */
  }
  printf("\n");

C問題

i=1～NのA_iについて、

1. 部分列の長さは4以上

• A₁ < A₂
• A_i-1 < A_i > A_i+1 が一か所
• A_i-1 > A_i < A_i+1 が一か所

となる部分連続列の数を求める問題。

3.4.の条件は下の図の赤丸で示したところ、つまり折れ線で描いたときに極大と極小の位置折れ線の範囲に極大と極小が1箇所ずつ存在する範囲、となる。

極大値と極小値の累積数を求めておく。そうすると、部分裂の左端をl、右端をrとしたときに3.4.の条件は、それぞれ

• hi[r-1] - hi[l] == 1
  
• lo[r-1] - lo[l] == 1
  

と書ける。そこで、lとrを更新していきながら、上式の条件を満たす数を数えていく。

lとrの更新は、

• l = 0, r = 3からスタート
• 2.の条件が成立するまで、lをインクリメント
• 1.3.4の条件が成立するまでrインクリメント ... lを左端として条件が成立する最短のrが得られる
• この状態から、3.4の条件が成立する右端の範囲の数（nvar）を求める
• 1.2.3.4の条件が成立している限り、左端lをインクリメント。この条件が成立しているとき、連続部分列の数はnvarずつ増えていく

としながら、l < n-3 && r < n が成立している間更新を繰り返していく。

l, rを更新していく部分のコードです。

  ll ans = 0;
  int l = 0, r = 3;             /* left boundary = 0, right bouudary = 3 */
  while (l < n-3 && r < n) {
    while (l < n-3 && p[l] >= p[l+1])
      l++;                      /* l increment until a[i] < a[i+1] */
    while (r < n && r < l+3)
      r++;                      /* r increment until length = 4 */
    while (r < n && !(hi[r-1] - hi[l] == 1 && lo[r-1] - lo[l] == 1))
      r++;                      /* r increment until tilde exist */
    int cnt = 0;
    while (r + cnt < n &&       /* count number of r boundary */
	   (hi[(r + cnt) - 1] - hi[l] == 1 &&
	    lo[(r + cnt) - 1] - lo[l] == 1))
      cnt++;
    while (l < n-3 && p[l] < p[l+1] && l <= r-3 &&
	   (hi[r-1] - hi[l] == 1 && lo[r-1] - lo[l] == 1)) {
      ans += cnt;               /* increment by number of r boundary */
      l++;                      /* with increasing l */
    }
  }