競技プログラミング「AtCoder」をJavaScriptでやってみた その6

ABC181-B

問題「黒板にある整数を書く作業をN回、i回目の操作はAi以上Bi以下の整数を１つずつ、合計Bi – Ai + 1個の整数を書く。N回の操作で黒板の整数の合計は？」

N
A1 B1
.
.
AN BN

2
1 3
3 5

1回目の操作で1,2,3を書き、2日目の操作で3,4,5を書いてこの合計は1+2+3+3+4+5=18になります。まず1行の合計を出すアルゴリズムを考えますが、数的処理では有名な公式を使います。例えば1,2,3,4,5,6,7,8,9,10の合計は55で、これは11×10÷2=55 先頭と末尾の数字を足して、要素数を掛けて２で割ります。個数が奇数でも偶数でも使えますので2,3,4,5,6,7,8,9,10の合計は54で、12×9÷2=54

今回の問題に当てはめるとこれをfor文でループします。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item)=>item.split(" ").map(Number));
  const N = items[0];
  let ans = 0;
 
  for(let i = 1; i <= N; i++) {
    ans += (items[i][0] + items[i][1]) * (items[i][1] - items[i][0] + 1) / 2;
  }
   console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

この他にも書き方があるのかもしれませんが、この解法がコード量少なく書けるはずです。という意味ではこの問題も数学的でした。

ABC180-B

問題「N次元空間の点(x1, x2, …xN)があり、原点からこの点までのマンハッタン距離 :
|x1|+…+|xN|、ユークリッド距離 : √|x1|**2+…+|xN|**2、チェビシェフ距離 : max(|x1|,…,|xN|)を求めよ。」

となんのことだかわかりませんが、この計算をすればいいです。入力は

N
x1……xN

なので値の扱いはシンプルです。例1で「ただ計算すればいいね」がわかります。

2
2 -1

マンハッタン距離 : |2|+|−1|=3

ユークリッド距離 : √|2|**2+|−1|**2=2.236067977499789…

チェビシェフ距離 : max(|2|,|−1|)=2

となるのですが、絶対値や平方根は見たことないですが、これもJavaScript技で対応できます。

'use strict'
function main(input) {
  input = input.trim().split("\n");
 
  let items_1 = input[1].split(" ").map( (x) => Math.abs(Number(x)) );
  let manhattan = items_1.reduce((a,b) => {
    return a + b;
  });
  console.log(manhattan);
 
  let items_2 = input[1].split(" ").map( (x) => Number(x) * Number(x) );
  let euclid_item = items_2.reduce((a,b) => {
    return a+b;
  });
  console.log(Math.sqrt(euclid_item));
  
  console.log(Math.max(...items_1));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

同じinput[1]に対して異なる処理をしてitems_1, items_2としているのも複雑に感じるかと思います。Math.abs()で絶対値にしたものを、mapなので全てにかけて配列items_1に入れて、

それに対しこれも初めて登場 reduceを使い足し上げていくのですが、まず(a, b)に(0, 2)が入り0+2=2が次のaになり、(2, 1)で2+1=3となります。最初のaに初期値を設定しておいてその初期値に配列要素を足したり引いたりなど処理を加えることもできますが、今回は初期値無しです。ちなみにaを累積値と呼びます。

次は順番飛ばしてチェビシェフ距離を求めます。絶対値の最大のものを求めるので全ての要素が絶対値の状態になっているitem_1をスプレッド構文で展開してそれに対しMath.max(…items_1)となります。

最後にユークリッド距離はその要素同士を２乗つまり掛け合わせたものをitem_2に配列で入れて、これもreduceで足し上げていきeuclid_itemとしました。例2では207と大きな数字になっています。この時点では要素同士をそれぞれ2乗したものの合計ですので、これを平方根にかけます。見慣れないsqrtですが、これで平方根ですので、Math.sqrt(euclid_item)とします。

ABC179-B

問題「サイコロ2個振る、をN回繰り返しゾロ目が3回連続ででるか判定」

N
D1,1 D1,2
.
.
DN,1 DN,2

これは問題文わかりやすいので例は省略します。合計3回以上ではなく3回連続をどう実装するかがポイントです。同じだったら“連続”という変数をインクリメントするアルゴリズムにしました。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item)=>item.split(" ").map(Number));
  let N = items[0];
  let ans = "No";
  let cont = 0;
  
  for(let i = 1; i <= N; i++) {
    if (items[i][0] === items[i][1]) {
      cont++;
      if (cont === 3) {
        ans = "Yes";
      }
    } else {
      cont = 0;
    }
  }
  console.log(ans);
 
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

ansの“No”とcontの0を用意して、for文で欲しいのは2行目からなのでiは1からNまで回します。items[i][0]がサイコロ1つ目、items[i][1]がサイコロ2つ目を意味しこれが同じだったらcont++でインクリメント、elseはcontを0にします。逆のcont–だと最初の方で揃わないとマイナスになってしまうのでcont=0としています。

途中のインクリメントの直後でさらにif文を使いcontが3になったらansを”Yes”に置き換えて、breakで終了です。

ちなみに初めは“連続”なのでlet continue = 0; としていましたが「let continue = 0; SyntaxError: Unexpected strict mode reserved word at wrapSafe」と表示されました… これはJavaScriptのStrictモードに引っかかったみたいです。コード先頭の’use strict’が原因かな？と思いましたが、これを消しても「let continue = 0; SyntaxError: Unexpected token ‘continue’ at wrapSafe」あまり効果はなく、結局continueをcontに変えるとエラーは消えました。

ABC178-B

問題「整数a,b,c,dがあり、a≦x≦b, c≦y≦dを満たす整数x, yのx × y の最大値はいくらか？」

制約a,b,c,d共に -10**9から10**9まで、入力は「a b c d」

例2「3 5 -4 -2」だと3×-2で-6が最も大きくなります。大きい方5と大きい方-2だと-10になるので注意。先にコードを載せます

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item)=>item.split(" ").map(BigInt)); 
  let [a, b, c, d] = items[0];
  let answers = [];
  
  answers.push(a*c, a*d, b*c, b*d);
  let maxAnswer = answers[0];
  for(let i = 0; i <= 3; i++) {
    if(maxAnswer < answers[i]) {
      maxAnswer = answers[i];
    }
  }
  console.log(maxAnswer.toString());
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

空の配列answers = []にa*c, a*d, b*c, b*dをpushしていき、maxAnswerをとりあえずanswers[0]にしておいて、for文でanswers[i]の方が大きかったらmaxAnswerを更新する。

アルゴリズムとしてはこれだけでシンプルなのですが…10の9乗という大きな値のためその扱いがポイントでした。失敗も含めて記しておきます。

ちなみにコードテストでNumberにしたitemsはいつも通り[[3, 5, -4, -2]]でしたが、BigIntにしたitemsは[[3n, 5n, -4n, -2n]]でした。JavaScriptの仕様なのでしょうかBigIntを3nといった文字列で返してくるようです。BigIntの時は注意が必要でtoString()を思い出す、と勉強になりました。

ABC177-B

問題「2つの文字列S, Tがある。TがSの部分文字列となるように、Sの文字の最小でいくつを書き換えるか？」

制約はTはSの長さ以下、S,T共に英小文字のみ　

S
T

と長い文字列も入る可能性もあり2行です。例１は

cabacc
abc

Sの４文字目aをcに書き換えればabcになるので最小は１ですが、アルゴリズムがなかなか浮かびませんでした。違った文字数をカウントしてループの度にその数字の小さい方を競わせますが、難易度は高めだと思います。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let S = input[0];
  let T = input[1];
  let ans = T.length;
  
  for(let i = 0; i <= S.length - T.length; i++) {
    let diff = 0;
    for(let j = 0; j < T.length; j++) {
      if(T[j] !== S[i + j]) {
        diff++;
      }
    }
    ans = Math.min(diff, ans);
  }
  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

例1をもとに解説します。どこをどう書き換えるにしてもTの文字数abcより長いことはないので、ansにはT.lengthのまず「3」が入っています。

2重ループだし、for文の条件が難しいので苦戦します… 部分文字列ははみ出すことはないのでiはS.length – T.lengthまでループ、ここはイメージしにくいと思うので後で表にします。ここでdiffを0にセットしますが、これは先のループが来るたびに毎回行います。

次のループjはT.lengthまで正確にはT[0]T[1]T[2]まででいいので「<」で大丈夫です。

if(T[j] !== S[i + j]) この部分が難しいポイントでTの[j]番目はa,b,cでいいですが、S[i+j]とは何でしょうか？表で記します。改めて入力の確認ですが

cabacc
abc

となっています。コードに揃えたので(j, i)の順で書いていますが、jは0,1,2の繰り返しなのでTはa,b,c…の繰り返しです。Sは0+0=0は最初の文字c、1+0=1は2文字目aということを意味します。

(j, i)   T[j] !== S[i + j]
0, 0     a         c
1, 0     b         a　　　　3
2, 0     c         b

0, 1     a         a
1, 1     b         b       1
2, 1     c         a

0, 2     a         b
1, 2     b         a       2
2, 2     c         c

0, 3     a         a
1, 3     b         c       1
2, 3     c         c

これらが違ったらdiffをインクリメントですので、iが０の時のdiffは３、iが1の時のdiffは1、iが2の時のdiffは2、iが3の時のdiffは1、となります。実際にMath.min(diff, ans)の上でconsole.log(diff)をすると、3 1 2 1が出てきます。ループの度にansとdiffを比べより小さいdiffがあったらansを更新する、という流れです。こういった表を実際に紙に手書きでも書いて見ないとイメージしにくい問題でした。