全探索 (AtCoder B問題)

JavaScript アルゴリズムとデータ構造

What

全探索は、全ての組み合わせを逐一、条件と一致するか確認するアルゴリズムです。

ここの問題を解いていく過程で学んだことや解法を記録しておきます。 qiita.com

Results

全て列挙しなくても解ける問題が多いと感じました。
以下、それぞれの問題に関して、方針や解法を記録しておきます。

ABC144 B_81

atcoder.jp

for文は1回で済みます。
与えられた数値に対して、1から9で割ります。その商が1から9の範囲内にあれば、true...このようにすれば解けます。

ABC150 B_CountABC

atcoder.jp

以下のように、正規表現で解けます (標準入力のプログラムは省略)。
エラー回避のため、マッチする文字列がないときは、空配列を与えるようにしています。

  const input = lines.split('\n')[1]
  console.log((input.match(/ABC/g) || []).length)

ABC122 B_ATCoder

atcoder.jp

入力された文字列の最初から、A, T, C, Gのいずれかの文字があるかどうか確認します。
該当しない文字に当たったら、'\n'で書き換えます。

一旦、配列を結合し、'\n'毎に配列を作りなおし、各要素の大きさだけの配列に変換します。
スプレッド構文を使い、一番大きな要素を出力すれば、完成です。

  let lengthArray = input.join('').split('\n').map(function(val){return val.length})
  console.log( Math.max(...lengthArray) )

なお、スプレッド構文は以下を満たします。配列の各要素を1つずつ取り出して評価したいときに、使えそうです。

console.log( Math.max(...arr) ===  Math.max.apply(null, arr))
//=> true

ABC136 B_Uneven Numbers

atcoder.jp

そんなに難しくないです。桁数 == 文字数が奇数のものを数え上げればできます。

  const input = lines.split('\n').map(Number)[0]
  let count = 0
  for(let i=1; i<=input; i++){
      if(i.toString().split('').length % 2 === 1){
          count++
      }
  }
  console.log(count)

ABC106 B_105

atcoder.jp

与えられた数値までの全数値 (奇数) を求める。求めた数値の約数を数え上げる。上記2つのために、for文を2回使います (または、与えられる数値の範囲が狭いため、if文で条件分けしても良さそうです)。

  const input = lines.split('\n').map(Number)[0]
  let count = 0

  // 入力した数値までの全数字を求める (奇数なのでi+=2)
  for(let i=1; i<=input; i+=2){
          let tmpCount = 0;

          // 求めた数値の全約数を求める
          for(let k=1; k<=i; k++){
              if(i%k === 0){
                  tmpCount++
              }
          }
          if(tmpCount === 8){
              count++
          }
  }
  console.log(count)

ABC120 B_K-th Common Divisor

atcoder.jp

それぞれの約数を求め、共通項をくくればできます。
Node.jsのバージョンが高ければ、includesメソッドで共通項を出力できます。

let divisorAB = divisorA.filter(function(element){return divisorB.includes(element);})

しかし、ABC120では、includesメソッドは使えませんでした。
計算量は少し多くなりますが、以下のように書き換えることもできます。

  var divisorAB = []
  for(var i=0; i<Math.max(divisorA.length,divisorB.length); i++){
    for(var k=0; k<Math.max(divisorA.length,divisorB.length); k++){
      if( divisorA[i] === divisorB[k]){
        divisorAB.push(divisorA[i])
        break;
      }
    }
  }

B問題は一旦これで終了なので、続きはまた後日投稿します。