AtCoder Beginner Contest 302 A-EをTypeScriptで解く。
先週に引き続きAtCoder Beginner Contest 302に参加をした。
コンテスト自体はPythonで参加をしたのだけど、Typescriptで振り返り記事を書く。
結果
A,B,C,D,Eの5完1ペナ。1290位のパフォ1318。
記録上、最高のパフォを叩き出せてよかった。
Qlitreさんのトヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)での成績：1290位
— Qlitre (@kuri_tter) May 20, 2023
パフォーマンス：1318相当
レーティング：822→884 (+62) :)
Highestを更新しました！#AtCoder #トヨタ自動車プログラミングコンテスト2023#2(ABC302) https://t.co/uMFVeqBP5q
A - Attack
体力がA の敵がいて、1 回攻撃をすることで敵の体力を B 減らすことが出来る。敵の体力を0以下にするために、最小で何回攻撃をする必要があるか答える問題。
難しいことは考えずに切り上げで割り算をすればいい。
珍しくシンプルな問題だと思った。A,BはBigInt型で処理するので、A/Bすると切り捨てで計算が行われることに注意する。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [a, b] = nextBigInts(2)
// bigint型だと切り捨てで行われる
let ans = a / b
// 割り切れない場合は1足す
if (a % b != 0n) {
ans++
}
log(String(ans))
}
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();
}B - Find snuke
H x Wのマス目が与えられて、マス目の中に、s, n, u, k, e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所がただ１つ存在する。
そのような場所のポジションを５行出力する、という問題。
とりあえず"s"が見つかったポジションから各方向へ全探索すれば答えが出せる。
ただ、250点ということで、予測はしていたものの重実装が要求される問題だ。
上下左右の動きだけでも結構キツイのに、斜めの方向も見なければいけない。
こういう時は各方向への移動の増減をあらかじめ配列で管理しておくと実装が少し楽になる。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [h, w] = nextNums(2)
const grid: string[] = []
for (let i = 0; i < h; i++) {
const s = next()
grid.push(s)
}
const directions: number[][] = [
// 上
[-1, 0],
//右上
[-1, 1],
//右,
[0, 1],
//右下,
[1, 1],
//下
[1, 0],
//左下
[1, -1],
//左,
[0, -1],
//左上,
[-1, -1]
]
for (let i = 0; i < h; i++) {
for (let j = 0; j < w; j++) {
const char = grid[i][j]
// s以外はみない
if (char != 's') continue
// 各方向を見る
for (const elm of directions) {
// 足し引きされる数
const [di, dj] = elm
const ans: number[][] = [[i, j]]
let tmp = 's'
let nowI = i
let nowJ = j
// 4つ見て文字をつくる
for (let cnt = 0; cnt < 4; cnt++) {
nowI += di
nowJ += dj
if (0 <= nowI && nowI < h && 0 <= nowJ && nowJ < w) {
tmp += grid[nowI][nowJ]
ans.push([nowI, nowJ])
}
}
if (tmp == 'snuke') {
for (const elm of ans) {
const [ansI, ansJ] = elm
log(ansI + 1, ansJ + 1)
}
exit()
}
}
}
}
}けっこうきつい。
C - Almost Equal
N個のM文字からなる文字列が与えられる。各文字は互いに異なる。
この文字の順番を並び替えて、以下の条件を満たすことができるかを判定する。
条件：
全ての1≤i≤N−1に対して、T_iを1文字だけ別の英小文字に変えてT_(i+1)にすることができる。
B問題に比べるとやり易い問題に思えた。
まずNの最大が8、Mの最大が5と非常に少ない
まず並び順の数は8!＝40,320。
それぞれでN回調べるのでｘ８で32万。それぞれの最大の5文字を調べて160万ほどか。つまり、全探索できる。
順列の生成はTypeScriptにはないので、関数を組んでおく。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
/**
*
* @param items
* @returns 順列をyieldして返す
*/
export function* permutations<T>(items: T[], prefix: T[] = []): Generator<T[]> {
if (items.length === 0) {
yield prefix;
} else {
for (let i = 0; i < items.length; i++) {
const newPrefix = prefix.concat(items[i]);
const remainingItems = items.slice(0, i).concat(items.slice(i + 1));
yield* permutations(remainingItems, newPrefix);
};
};
};
// 条件を満たすかチェック
function checkValid(s1: string, s2: string, m: number): boolean {
let count = 0
for (let i = 0; i < m; i++) {
if (s1[i] != s2[i]) count++
}
return count == 1
}
function main() {
const [n, m] = nextNums(2)
const charArr: string[] = []
for (let i = 0; i < n; i++) {
const char = next()
charArr.push(char)
}
// 順列を全探索
for (const perm of permutations(charArr)) {
let valid = true
for (let i = 0; i < n - 1; i++) {
const s1 = perm[i]
const s2 = perm[i + 1]
if (!checkValid(s1, s2, m)) {
valid = false
break
}
}
if (valid) {
log('Yes')
exit()
}
}
log('No')
}D - Impartial Gift
高橋君が、青木君とすぬけ君への贈り物をする。
青木君への贈り物の候補はN個あり、それぞれの価値はA_1, A_2, ..., A_N。
すぬけ君への贈り物の候補はM個あり、それぞれの価値はB_1, B_2, ..., B_M。
2人への贈り物の価値の差がD以下になるようにする。
高橋君が目標を達成できるかどうかを判断し、達成可能な場合は贈り物の価値の和の最大値を求める、そのような組み合わせが存在しないときは-1を出力する。
青木君への贈り物を全探索して、+Dを超えないような最大のすぬけ君への贈り物の価値を探す。
結論からいって、すごく二分探索っぽい。
Pythonなどではbisectモジュールを使えば一発だが、TypeScriptにそのようなものはないので、以下のような関数を組んでおく。
/**
*
* @param arr ソート済みの配列
* @param x 検索値
* @returns
* 値 x が最後に現れるインデックスを返す。
* x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
*/
export const bisectRight = (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 hi;
}例えば青木君への贈り物の価値が5で、すぬけ君への贈り物の価値が[1,3,5,7,9]だとする。
7でbisect_rightすることになるので、インデックスは4を返す。最大となるのはインデックス3の7となる。
別の例も考えてみよう。
[1,9]だと、インデックスは1、最大はインデックス0の1
[10,11,12]みたいなものだとインデックスは0。ということは 7以下の贈り物はない。
一般化するとbisect_rightしたインデックスが0の時は選べる贈り物はない。
そうでないときはインデックス-1した贈り物の価値が最大。
ただし、差の絶対値がDを超えてはならないことに注意する。
なお、贈り物の価値は10^18と大きいので、BigInt型での実装となる。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
/**
*
* @param arr ソート済みの配列
* @param x 検索値
* @returns
* 値 x が最後に現れるインデックスを返す。
* x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
*/
export const bisectRight = (arr: bigint[], x: bigint, 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 hi;
}
function main() {
const [n, m, d] = nextNums(3)
const aokiGift = nextBigInts(n)
const snukeGift = nextBigInts(m)
let ans = -1n
// 昇順で並び替える
snukeGift.sort((a, b) => Number(a - b))
for (const value of aokiGift) {
const idx = bisectRight(snukeGift, value + BigInt(d))
// 選べるギフトがない
if (idx == 0) continue
// 最大価値のギフト
const valueMax = snukeGift[idx - 1]
// 絶対値がD以内なら選べる
let diff = 0n
if (value >= valueMax) {
diff = value - valueMax
} else {
diff = valueMax - value
}
if (diff <= d) {
const sumValue = value + valueMax
if (sumValue > ans) ans = sumValue
}
}
log(String(ans))
}E - Isolation
初めにN頂点が与えられて、その後にQ個のクエリを処理していく。
各クエリの処理後に、他のどの頂点とも辺で結ばれていない頂点（「孤立頂点」）の数を出力する。
クエリは以下の2種類がある。
クエリ1 (u, v): 頂点uと頂点vを辺で結ぶ。このクエリが実行される直前の時点で、頂点uと頂点vは辺で結ばれていないことが保証されている。
クエリ2 (v): 頂点vと他の頂点との間の全ての辺を削除する。ただし、頂点v自体は削除されない。
制約条件として、N（頂点の数）は2以上3×10^5以下。
Q（クエリの数）は1以上3×10^5以下。
また、各クエリに含まれる頂点の番号u、そしてクエリ1の直前の時点で、頂点uと頂点vが辺で結ばれていないことが保証されている。
まず、明らかに孤立頂点の数はスタート時点ではN。
そこから、クエリに応じて、孤立頂点の増減を記録することを考える。
クエリ１の方はそのまま実装すればよさそう。
つながれるそれぞれの頂点が孤立していたら、孤立頂点の数をマイナス１する。
次に問題となる、クエリ２の方。
単純に考えると、まず指定された頂点は絶対に孤立になる。そのためプラス１。
つぎに指定された頂点とつながっている頂点から辺を取り除いて、孤立頂点になったらプラス１する。
一見重そうな実装に思える。
だが、クエリの回数とNの個数の最大は同じ。ということは最大の取り除かれる回数は、およそ最大のNの個数となる。
素直な実装で間に合う。
あとは取り除く動作を高速に行いたい。グラフ表現をする際に集合を用いて、要素の削除をすればいい。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [n, q] = nextNums(2)
const graph: Record<number, Set<number>> = {}
// graphの初期化
for (let i = 1; i < n + 1; i++) {
graph[i] = new Set()
}
let ans = n
for (let i = 0; i < q; i++) {
const t = nextNum()
if (t == 1) {
const [u, v] = nextNums(2)
// 孤立していたらマイナス
if (graph[u].size == 0) ans--
graph[u].add(v)
if (graph[v].size == 0) ans--
graph[v].add(u)
} else {
const u = nextNum()
// uが孤立していなかったらプラス
if (graph[u].size > 0) ans++
for (const v of graph[u]) {
// 取り除く
graph[v].delete(u)
// 孤立したらプラス
if (graph[v].size == 0) ans++
}
// 切り離す
graph[u].clear()
}
// 答えの出力
log(ans)
}
}おわりに
感覚的にはB問題がきつい問題セットだった。
先週に緑コーダーになって、引き続きスコアを伸ばすことができたので、よかった。
なお、入緑記事は個人ブログの方に書いた。
けっこう突っ込んで緑コーダーになるためにやってきたことを書いたつもり。
ぜひ、こちらも読んでみてほしい。ではでは。