paizaキャンペーン問題 Bランク 長テーブルのうなぎ屋【JavaScript】

paiza×Qiita記事投稿キャンペーン の 長テーブルのうなぎ屋 をJavaScriptで。

大まかな処理は以下の通り。

• ①全座席の空席状況 及び ②座りたい客の並び を2進数で扱う
• ①に対して②をビットANDで確認、入り込む余地があれば①に②をビットORして更新
• 立っているビット数を返して終了

ビット演算を使うことで、1グループ内のメンバー全員の着席可否チェックをループを使わず1回で判定することができます。

例として座席数6とした場合、席の状態を0b000000とします。
(ビット配置が分かりやすいよう6桁で示しましたが、実際には単に0で初期化するだけです)

まず4人のグループが入店、2番目の席から座ろうとしているとします。
1を4ビット左シフトして0b10000、そこから-1することで0b1111と、2進数で1が4つ並んだ値になります。
2番目の席から確保したいので2-1ビット左シフトして((1 << 4) - 1) << (2 - 1) で 0b11110を確保したい席とします。
席の状態と確保したい席をビットANDすると 0b000000 & 0b11110は0で空席であることが分かります。
空席なので、席の状態に確保したい席をビットORして更新すると、席の状態は 0b000000 | 0b11110 で 0b011110 になります。

次に2人のグループが5番目からの席を確保しようと入店したとします。
確保したい席は ((1 << 2) - 1) << (5 - 1) で 0b110000。
0b011110 & 0b110000は0b10000で0ではない(立っているビット=確保したい席のうち既に埋まっている席 が含まれている)ので更新はしません。

これをグループ数分繰り返し、最後に c.toString(2).match(/1/g).length で人数を出します。

実際のコードではNumberではビット数が足りないのでBigIntを使用し、最後と1番目の座席に跨る部分の処理を簡略化するために、席の状態、確保したい席ともに重複して2周分持たせています。
（入力データによっては3周分に近くなるケースもあります）

let c = 0n, n = BigInt, h, d, x, y;
process.stdin.some(l => {
  (0 + l).split('\n').map((s, i) => {
    const [a, b] = s.split(' ');
    if (s && i)
      c & (d = (x = (1n << n(a)) - 1n) << (y = n(b - 1)) | x << h + y) || (c |= d);
    else
      h = n(a);
  });
  console.log(c.toString(2).match(/1/g).length / 2);
});

可読性優先

let seatStatus = 0n; // 座席の状態
let seatsCount;      // 座席数
process.stdin.some(l => {
  (0 + l).split('\n').forEach((s, i) => {
    const [a, b] = s.split(' ');
    if (s && i) {
      let desiredSeats =         // 確保したい席
        ((1n << BigInt(a)) - 1n) // 人数 (3人なら0b111のように立ったビットの並びで表現)
        << (BigInt(b - 1));      // 確保したい位置の先頭

      // 確保したい席を2周分重複させる
      desiredSeats |= desiredSeats << seatsCount;

      // ビットANDで空席確認して空席ならビットORで更新
      if (!(seatStatus & desiredSeats)) seatStatus |= desiredSeats;
    }
    else
      seatsCount = BigInt(a); // 座席数
  });
  console.log(seatStatus.toString(2).match(/1/g).length / 2);
});

短縮版

c=0n;process.stdin.some(l=>{(0+l).split`\n`.map((s,i)=>([a,b]=s.split` `,s&&i)?c&(d=(x=(1n<<n(a))-1n)<<(y=n(b-1))|x<<h+y)||(c|=d):h=(n=BigInt)(a));console.log(c.toString(2).match(/1/g).length/2)})