1年半くらい前に一時期AOJをやっていた。最近また少しずつだけれども頑張って提出するようにしている。ブログのネタもないので全部じゃないけど特に覚えておきたいようなやつは書き残しておこうと思う。

問題


ラウンドロビンスケジューリングをシミュレートするという問題。

AOJ: ALDS1_3_B

所感


所感など

  • 静的型付き言語でやりたいけどNode.jsだと書いて実行するのが楽なのでJSでやっている
    • エントリーポイント書かなくていいというのも楽
  • 一つ前の記事で書いた循環キューを使って提出すると制限時間超過になってしまった
    • これは遅いであろうというのは書いた時点ではわかっていたけど超過になるとは思ってなかった
    • ので、現在の要素の数をカウントする処理を簡素に書き直して提出した
      • 5.99sec -> 00.08sec まで改善した
  • この記事書くにあたって利用規約確認すると提出したコードは商業利用禁止になっていた
    • その他は特に言及されていないので問題なさそう

コード


以下、提出したコード

コード部のライセンスはAOJの利用規約に準拠します

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class CircularQueue {
constructor(capacity) {
this._capacity = capacity;
this._items = new Array(capacity);
this._head = 0;
this._tail = 0;
this._count = 0;
}

enqueue(item) {
if (this._count >= this._capacity) {
throw new Error("Exceeded capacity");
}

this._items[this._tail] = item;

if (this._tail === this._capacity) {
this._tail = 0;
} else {
this._tail = this._tail + 1;
}
this._count++;
}

dequeue() {
if (this.isEmpty()) {
throw new Error("No items");
}

const head = this._items[this._head];
this._items[this._head] = undefined;

if (this._head === this._capacity) {
this._head = 0;
} else {
this._head = this._head + 1;
}
this._count--;

return head;
}

isEmpty() {
return this._count === 0;
}
}

const x = require('fs').readFileSync('/dev/stdin', 'utf8').split("\n");
x.pop(); // 最後の行が空のため消す
const qms = parseInt(x.shift().split(" ")[1]);

const tasks = x.map(y => y.split(" "));
const cq = new CircularQueue(tasks.length);

tasks.forEach(e => {
cq.enqueue(e);
});

let totalTime = 0;
while (!cq.isEmpty()) {
const a = cq.dequeue();
const t = a[1] - qms;
if (t > 0) {
totalTime = totalTime + qms;
cq.enqueue([a[0], t]);
} else {
totalTime = totalTime + (t > 0 ? qms : parseInt(a[1]));
console.log(`${a[0]} ${totalTime}`);
}
}