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)})