Javascriptで解くAtCoder Beginners Selection

AtCoder Beginners Selectionとは AtCoder 初心者向けに用意された11問の問題集です。
かくいう筆者も先日登録したばかりの初心者なので、さっそく解いてみます。

• 追記（2021-01-11)
  ABC083B - Some Sums の別解を載せました。

PracticeA - Welcome to AtCoder

公式に解答があるため割愛します。
問題というよりは AtCoder 自体の練習なので、あえてエラーになるようなものを提出してみても良いのではないでしょうか。

ABC086A - Product

シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

a と b どちらも奇数ならその積も奇数、どちらかが偶数なら積も偶数になります。
制約から32ビット整数で計算できる値なのでビット演算で解いてみましょう。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ a, b ] = input.split( " " ).map( v => parseInt( v, 10 ) )

const answer = ( a & b & 1 ) ? "Odd" : "Even"
console.log( answer )

ABC081A - Placing Marbles

すぬけ君は 1 , 2 , 3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には s i が書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

立ってるビットを数えればいいですね。
ちょうど入力が2進数なのでこれは楽です。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const n = parseInt( input, 2 )
const answer = ( ( n & 4 ) >>> 2 ) + ( ( n & 2 ) >>> 1 ) + ( n & 1 )
console.log( answer )

ABC081B - Shift only

黒板にN個の正の整数A1,...,ANが書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

• 黒板に書かれている整数すべてを，2で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

これも制約から32ビット整数で計算できるのでビット演算しましょう。
2で割れる回数は「立っているビットのうち一番下位のものより下位に連続する0の数」を数えればいいと思います。

少し複雑になった気もします。もっとシンプルな方法があるのでしょうか？

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ n, tmp ] = input.split( "\n" )
const a = tmp.split( " " ).map( v => parseInt( v, 10 ) )

//最大操作回数。初期値は31より大きければどんな数値でも大丈夫です。
let count = Number.POSITIVE_INFINITY

for ( let c of a ) {

  //「立っているビットのうち一番下位のものより下位に連続する0」の部分だけビットを立てます。
  c ^= c - 1
  c >>>= 1

  //立っているビットの数を数えます。
  c = ( c >>> 1 & 0x55555555 ) + ( ( c & 0x55555555 ) >>> 0 )
  c = ( c >>> 2 & 0x33333333 ) + ( ( c & 0x33333333 ) >>> 0 )
  c = ( c >>> 4 & 0x0F0F0F0F ) + ( ( c & 0x0F0F0F0F ) >>> 0 )
  c = ( c >>> 8 & 0x00FF00FF ) + ( ( c & 0x00FF00FF ) >>> 0 )
  c = ( c >>> 16 & 0x0000FFFF ) + ( ( c & 0x0000FFFF ) >>> 0 )

  if ( count > c ) {
    count = c
  }

}

console.log( count )

ABC087B - Coins

あなたは、 500 円玉を A 枚、 100 円玉を B 枚、 50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

素直に実装すると手持ちから出せる金額を全パターン計算してX円になるか計算する方法になるでしょう。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ a, b, c, x ] = input.split( "\n" ).map( v => parseInt( v, 10 ) )

let count = 0
//500円玉を0〜A枚出す
for ( let i = 0; i <= a; i++ ) {
  //100円玉を0〜B枚出す
  for ( let j = 0; j <= b; j++ ) {
    //50円玉を0〜C枚出す
    for ( let k = 0; k <= c; k++ ) {
      //合計金額が一致するかチェック
      if ( ( ( 500 * i ) + ( 100 * j ) + ( 50 * k ) ) === x ) {
        count ++
      }
    }
  }
}

console.log( count )

ABC083B - Some Sums

1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。

素直に実装すると各桁の和を計算するために文字列への再変換（もしくは除算）が必要なので、重い処理になります。
何か良いアルゴリズムはないでしょうか？

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ n, a, b ] = input.split( " " ).map( v => parseInt( v, 10 ) )

//総和
let sum = 0

for ( let value = 1; value <= n; value++ ) {

  //各桁の数値
  const sp = value.toString().split( "" ).map( v => parseInt( v, 10 ) )

  //各桁の和
  const spsum = sp.reduce( ( acc, cur ) => acc + cur, 0 )

  if ( spsum >= a && spsum <= b ) {
    sum += value
  }

}

console.log( sum )

追記（2021-01-11)
文字列への変換を行わないパターンも思いついたので載せます。

文字列への変換を行わないパターン

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ N, A, B ] = input.split( " " ).map( v => parseInt( v, 10 ) )

//総和
let sum = 0

let n = 1
//Nが最大10の4乗なので、最低5桁必要です。
const o = Array( 5 ).fill( 0 )
o[ 0 ] = n

for ( ; n <= N; n ++ ) {

  //各桁の和
  let $sum = 0
  for ( let i = 0, f = false; i < o.length; i ++ ) {
    $sum += o[ i ]
    if ( f ) continue
    if ( ++ o[ i ] < 10 ) f = true
    else o[ i ] = 0
  }

  if ( $sum < A || $sum > B ) continue
  sum += n

}

console.log( sum )

元がコンパクト過ぎるのもあって、特に性能は変わっていないです。
好みで選べばいいですね。

文字列への変換	実行時間(ms)	メモリ(KB)
あり	72	33940
なし	79	32232

ABC088B - Card Game for Two

N枚のカードがあります.i枚目のカードには,aiという数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

カードを高い順にソートして、Aliceから交互に取っていけば良さそうです。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ , tmp ] = input.split( "\n" )
const a = tmp.split( " " ).map( v => parseInt( v, 10 ) )

const score = {
  "Alice": 0,
  "Bob": 0,
}

//降順（得点の高い順）にソート
const cards = a.sort( ( a, b ) => b - a )

for ( const [ index, card ] of cards.entries() ) {

  //交互に高いものを取るので index が奇数の場合は後攻（Bob）が取る
  const player = ( index & 1 ) ? "Bob" : "Alice"
  score[ player ] += card

}

const answer = score[ "Alice" ] - score[ "Bob" ]
console.log( answer )

ABC085B - Kagami Mochi

X段重ねの鏡餅(X≥1)とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。
X段重ねの鏡餅(X≥1)とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。

問題文は長いですが、要は直径が重複した分の鏡餅を無視して数え上げれば良いので、単にSetに突っ込んでしまえば良いです。

計算するアルゴリズムを書いていないのでなんだかずるした気分です。;)

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ , ...d ] = input.split( "\n" ).map( v => parseInt( v, 10 ) )

//最後に空行があるので捨てます。
d.pop()

//重複している直径を一意にします。
const uniqueRiceCakes = new Set( d )

console.log( uniqueRiceCakes.size )

ABC085C - Otoshidama

日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

お札の枚数からあり得る合計金額が金額と一致するか総当りで見つけます。
ABC087B - Coinsとは条件の違いから若干のアレンジが加わりますが、考え方自体は同じです。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ N, Y ] = input.split( " " ).map( v => parseInt( v, 10 ) )

for ( let x = 0; x <= N; x ++ ) {
  for ( let y = 0; y <= N - x; y ++ ) {
    const z = N - x - y
    if ( ( x * 10000 ) + ( y * 5000 ) + ( z * 1000 ) === Y ) {
      console.log( `${ x } ${ y } ${ z }` )
      return
    }
  }
}

console.log( "-1 -1 -1" )

ABC049C - 白昼夢

英小文字からなる文字列Sが与えられます。Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことでS=Tとすることができるか判定してください。

• T の末尾に dream dreamer erase eraser のいずれかを追加する。

文字列Sがdream dreamer erase eraserで埋まっているか判定します。
素直に正規表現を使いましたが、パーサーを書いても面白そうです。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ S ] = input.split( "\n" )

const answer = S.match( /^(dream|dreamer|erase|eraser)*$/ ) ? "YES" : "NO"
console.log( answer )

ABC086C - Traveling

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 ( 0 , 0 ) を出発し、 1 以上 N 以下の各 i に対し、時刻 t i に 点 ( x i , y i ) を訪れる予定です。
AtCoDeerくんが時刻 t に 点 ( x , y ) にいる時、 時刻 t + 1 には 点 ( x + 1 , y ) , ( x − 1 , y ) , ( x , y + 1 ) , ( x , y − 1 ) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

まず、距離を算出し規定時刻までに到達可能か判定します。
次に、規定時間より早く着く場合は、その場を行ったり来たりして寄り道することで時間を潰せば良いでしょう。ただし、寄り道すると元のルートに戻らなければならないので、2の倍数分しか時間を潰せません。
なお、2の倍数とは、すなわち偶数です。ビット演算の出番ですね。

const input = require( "fs" ).readFileSync( "/dev/stdin", "utf8" )
const [ N, ...temp ] = input.split( "\n" )

//空行を捨てます。
temp.pop()

const plans = temp.map( line => {
  const args = line.split( " " ).map( v => parseInt( v, 10 ) )
  return {
    t: args[ 0 ],
    x: args[ 1 ],
    y: args[ 2 ],
  }
} )

const start = { t: 0, x: 0, y: 0, }

//実現不可能な予定が無いかチェックします。
for ( const [ index, plan ] of plans.entries() ) {

  const prev = index == 0 ? start : plans[ index - 1 ]
  const time = plan.t - prev.t
  const distance = Math.abs( plan.x - prev.x ) + Math.abs( plan.y - prev.y )

  //近すぎる場合の余る時間です。2の倍数なら寄り道で潰せます。
  const def = time - distance

  if ( ( distance > time ) || ( def & 1 ) ) {
    //目的地が遠すぎるか、寄り道で時間を潰せない場合です。
    console.log( "No" )
    return
  }

}

console.log( "Yes" )

おしまい

以上！
途中つまずいたところもありましたが、ビット演算がたくさん使えて満足です。
ただ Javascript ではこのレベルの小細工で効率が良くなるケースは稀なので、通常は可読性を重視して% 2や/ 2を使用した方が良いと思います。