Photo by
テオドール・ジェリコー / メトロポリタン美術館
AtCoder Beginner Contest 294 A-EをTypeScriptで解く。
AtCoder Beginner Contest 294に参加をした。
コンテスト自体はPythonで参加をしたのだけど、Typescriptで振り返り記事を書く。Typescriptの勉強中なので…。
結果として今回は2ペナ４完だった。パフォーマンスは724。
全体の感想
D問題か解けるか、どうか、というくらいの実力なので、D問題まで解けたので個人的に満足だった。E問題は1TLEがとり切れず。
比較的解きやすい問題が多かったのだろうか、D問題が灰Diff、E問題が茶Diffのセットだったのは、珍しい。
A - Filter
数列の中から偶数だけを抽出する問題。
一つずつ調べて答えの配列に加える。
import { createInterface } from "readline";
import * as fs from "fs";
function main() {
const n = nextNum()
const arr = nextNums(n)
const ans: number[] = []
for (const num of arr) {
if (num % 2 == 0) {
ans.push(num)
}
}
console.log(ans.join(' '));
}
let inputs = "";
let inputArray: string[];
let currentIndex = 0;
function next() {
return inputArray[currentIndex++];
}
function nextNum() {
return +next();
}
function nextBigInt() {
return BigInt(next());
}
function nexts(length: number) {
const arr = [];
for (let i = 0; i < length; ++i) arr[i] = next();
return arr;
}
function nextNums(length: number) {
const arr = [];
for (let i = 0; i < length; ++i) arr[i] = nextNum();
return arr;
}
function nextBigInts(length: number) {
const arr = [];
for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
return arr;
}
// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
const stream = createInterface({
input: process.stdin,
output: process.stdout,
});
stream.on("line", (line) => {
inputs += line;
inputs += "\n";
});
stream.on("close", () => {
inputArray = inputs.split(/\s/);
main();
});
} else {
inputs = fs.readFileSync("/dev/stdin", "utf8");
inputArray = inputs.split(/\s/);
main();
}自分はこのような素朴な実装で解いたが、filterメソッドを使うとより簡潔に書ける。
function main() {
const n = nextNum()
const arr = nextNums(n)
const ans = arr.filter((num) => num % 2 == 0)
console.log(ans.join(' '));
}B - ASCII Art
二次元配列が与えられて、アスキーアートを生成する問題。
ABCD…Zという文字列を生成してインデックスから変換すれば答えが出せそうだ。愚直に入力しても良いが、String.fromCharCodeメソッドを使って、Unicode文字コードを文字列に変換する方法を取ってみる。
Array.from({ length: 26 }, (_, index) => String.fromCharCode(65 + index))とすると、['A', 'B', … 'Z']という配列が得られる。
function main() {
const [h, w] = nextNums(2)
const upperCase = Array.from({ length: 26 }, (_, index) => String.fromCharCode(65 + index))
for (let i = 0; i < h; i++) {
const arr = nextNums(w)
const ans: string[] = []
for (const num of arr) {
if (num == 0) {
ans.push('.')
} else {
ans.push(upperCase[num - 1])
}
}
console.log(ans.join(''));
}
}ちなみにテストケースの出力がかわいい。こういう遊び心があるのがAtCoderの面白い点でもある。
................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................C - Merge Sequences
問題文が長くて戸惑う。
よくよく読んでみると、以下のような問題であることが分かる。
数列AとBが与えられる。
それぞれの数列の数字は全て異なる
数列CはAとBを合わせてsortしたもの
元の数列A,Bのそれぞれの数字がCで何番目になるかを出力
狭義単調増加列とは、数列の各項が前の項よりも大きくなるような数列のことを指すようだ。
AとBの大きさは最大で10,000程度なので、Cの最大は20,000。
線形探索をすると間に合わないので二分探索を用いる。
Typescriptには二分探索ライブラリがないようなので、あらかじめ関数化しておくと、こういう問題で役に立つ。
/**
*
* @param arr ソート済みの配列
* @param x 検索値
* @returns
* 値 x が最初に現れるインデックスを返す。
* x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
*/
export const bisectLeft = (arr: number[], x: number, lo: number = 0, hi: number = arr.length): number => {
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
function main() {
const [n, m] = nextNums(2)
const aList = nextNums(n)
const bList = nextNums(m)
const cList = aList.concat(bList)
cList.sort((a, b) => a - b)
const ansA: number[] = []
for (const num of aList) {
const idx = bisectLeft(cList, num) + 1
ansA.push(idx)
}
const ansB: number[] = []
for (const num of bList) {
const idx = bisectLeft(cList, num) + 1
ansB.push(idx)
}
console.log(ansA.join(' '));
console.log(ansB.join(' '));
}D - Bank
一見してなんらかのデータ構造を使う問題に見える、面白そう。
自分は銀行というよりは病院の窓口のイメージが浮かんだ。
呼ばれたけど受付にいかない人がいる、その人が再度呼ばれても受付に行かない可能性がある、というのがミソ。
1 : 受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる。
2 x : 人 x が初めて受付に行く。(ここで、人 x はすでに 1 回以上受付に呼ばれている。)
3 : すでに受付に呼ばれているが受付に行っていない人のうち、最も小さい番号の人が再度呼ばれる。
C++のstd::setのような順序付き集合を使えば簡単に解けそうである。しかし、TypeScriptには標準での実装がない。
その他にもheapや両端キューを用いて解くこともできそうだが、同じくTypeScriptには標準では用意されていない。
問題の制約から矛盾したクエリは起こらないようなので、素朴な実装で解いてみる。
例えば受付に行った人を集合で管理して３のクエリで呼ぶ人のインデックスをインクリメントしていく方法をとってみる。以下のようになった。
function main() {
const [n, q] = nextNums(2)
let person = 1
const clear = new Set()
const waiting: number[] = []
let idx = 0
for (let i = 0; i < q; i++) {
const query = next()
if (query[0] == '1') {
waiting.push(person)
person++
} else if (query[0] == '2') {
const x = Number(next())
clear.add(x)
}
else {
for (let j = idx; j < waiting.length; j++) {
// 既に受付に行っている
if (clear.has(waiting[j])) continue
console.log(waiting[j]);
// 次はここから始めればいい
idx = j
break
}
}
}
}そのほか、データ構造を持っていれば、あまり難しいことを考えなくても解ける。例えばheapを使う場合は以下のようになる。
export class BinaryHeap<T> {
public heap: T[];
private compare: (a: T, b: T) => number;
constructor(compareFn: (a: T, b: T) => number) {
this.heap = [];
this.compare = compareFn;
}
public push(value: T): void {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
public pop(): T | undefined {
const last = this.heap.pop();
if (this.heap.length > 0) {
const result = this.heap[0];
this.heap[0] = last!;
this.sinkDown(0);
return result;
} else {
return last;
}
}
private bubbleUp(index: number): void {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (this.compare(element, parent) >= 0) {
break;
}
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
private sinkDown(index: number): void {
const element = this.heap[index];
const length = this.heap.length;
while (true) {
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
let leftChild: T, rightChild: T;
let swapIndex = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (this.compare(leftChild, element) < 0) {
swapIndex = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if ((swapIndex === null && this.compare(rightChild, element) < 0) ||
(swapIndex !== null && this.compare(rightChild, leftChild!) < 0)) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) {
break;
}
this.heap[index] = this.heap[swapIndex];
this.heap[swapIndex] = element;
index = swapIndex;
}
}
public size(): number {
return this.heap.length;
}
}
function main() {
const [n, q] = nextNums(2)
let person = 1
const clear = new Set()
const waiting: BinaryHeap<number> = new BinaryHeap((a, b) => a - b)
let idx = 0
for (let i = 0; i < q; i++) {
const query = next()
if (query[0] == '1') {
waiting.push(person)
person++
} else if (query[0] == '2') {
const x = Number(next())
clear.add(x)
}
else {
while (waiting.size() > 0) {
const p = waiting.pop()
if (!p) break
if (clear.has(p)) continue
console.log(p);
// もう一回呼ばれる可能性があるのでheapに入れる。
waiting.push(p)
break
}
}
}
}色々な解き方がある問題は面白い。
個人的にけっこう難しいと思った。
灰Diffだったのがちょっと信じられないでいる。
E - 2xN Grid
ランレングス圧縮っぽい問題。
展開後の長さが10**12なので、まともに探索すると当然TLEになる。
コンテスト中は上段の範囲を辞書に記録して探索する方法を取ったが、１テストケースでTLEを起こし突破できなくて悔しい思いをした。
解説で同時探索していく方法が紹介されていたので、そちらを実装してみる。なんとなくそれぞれの区間に始まりと終わりを持たせると、後の計算が簡単そうである。
例えば入力で以下のようにあった場合。
1 4
2 1
3 3できあがる数列は[1, 1, 1, 1, 2, 3, 3, 3]
それぞれの数字ごとに以下のような二次元配列で管理していくことを考える。
[
[1, 0, 3],
[2, 4, 4],
[3, 5, 7],
]実装すると以下のようになる。
数字と区間が重なったときは早く終わる方から遅く始まる方を引けば区間の長さが計算できそうだ。あとはそれぞれの比較において、早く終わる方を次の区間にずらしていくイメージ。
実装すると以下のようになった。
function main() {
const [l, n, m] = nextNums(3)
const top: number[][] = []
let fromIdx = 0
for (let i = 0; i < n; i++) {
const [num, length] = nextNums(2)
top.push([num, fromIdx, fromIdx + length - 1])
fromIdx += length
}
const bottom: number[][] = []
fromIdx = 0
for (let i = 0; i < m; i++) {
const [num, length] = nextNums(2)
bottom.push([num, fromIdx, fromIdx + length - 1])
fromIdx += length
}
let topIdx = 0
let bottomIdx = 0
let ans = 0
while (topIdx < n && bottomIdx < m) {
const [topNum, topFrom, topTo] = top[topIdx]
const [bottomNum, bottomFrom, bottomTo] = bottom[bottomIdx]
// 数字が違う=>先に終わるインデックスをインクリメント
if (topNum != bottomNum) {
if (topTo < bottomTo) {
topIdx++
} else if (bottomTo < topTo) {
bottomIdx++
// 同じ場合は両方次の数字へ
} else {
topIdx++
bottomIdx++
}
} else {
// 数字が同じで重なっている範囲がある
// 早い終わり - 遅い始まりを足す
ans += Math.min(topTo, bottomTo) - Math.max(topFrom, bottomFrom) + 1
// 同様にインクリメント
if (topTo < bottomTo) {
topIdx++
} else if (bottomTo < topTo) {
bottomIdx++
} else {
topIdx++
bottomIdx++
}
}
}
console.log(ans);
}インクリメントの部分と配列をつくる処理が重複している。
関数に切り出すと、すっきりする。
const countUp = (t: number, b: number, ti: number, bi: number): number[] => {
if (t < b) return [ti + 1, bi]
if (b < t) return [ti, bi + 1]
return [ti + 1, bi + 1]
}
const getArr = (n: number): number[][] => {
const arr: number[][] = []
let fromIdx = 0
for (let i = 0; i < n; i++) {
const [num, length] = nextNums(2)
arr.push([num, fromIdx, fromIdx + length - 1])
fromIdx += length
}
return arr
}
function main() {
const [l, n, m] = nextNums(3)
const top = getArr(n)
const bottom = getArr(m)
let topIdx = 0
let bottomIdx = 0
let ans = 0
while (topIdx < n && bottomIdx < m) {
const [topNum, topFrom, topTo] = top[topIdx]
const [bottomNum, bottomFrom, bottomTo] = bottom[bottomIdx]
if (topNum != bottomNum) {
const [t, b] = countUp(topTo, bottomTo, topIdx, bottomIdx)
topIdx = t
bottomIdx = b
} else {
ans += Math.min(topTo, bottomTo) - Math.max(topFrom, bottomFrom) + 1
const [t, b] = countUp(topTo, bottomTo, topIdx, bottomIdx)
topIdx = t
bottomIdx = b
}
}
console.log(ans);
}ではでは。
この記事が気に入ったらサポートをしてみませんか？