AtCoder Beginner Contest 303 A-EをTypeScriptで解く。
先週に引き続きAtCoder Beginner Contest 303に参加をした。
コンテスト自体はPythonで参加をしたのだけど、Typescriptで振り返り記事を書く。
結果
A-Dの４完ノーペナ、1972位のパフォ1102。
Highestを更新できたのでよかった。
Qlitreさんの日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）での成績：1972位
— Qlitre (@kuri_tter) May 27, 2023
パフォーマンス：1102相当
レーティング：884→908 (+24) :)
Highestを更新しました！#AtCoder （ABC303） https://t.co/QdHKtQDnTy
A - Similar String
文字列S,Tが与えられて似た文字列であるかどうか判定する問題。
それぞれの位置において、同じ文字か、"1"と"l"のペア、または"0"と"o"のペアであれば似た文字。
全ての位置で文字が「似た文字」であれば、SとTは「似た文字列」となる。
結構難しいと思った。予め1と0を'l'と'o'に変換しておけば、同じ文字列かどうか判定するだけでいいから簡単か。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const n = nextNum()
const s = next().split('')
const t = next().split('')
for (let i = 0; i < n; i++) {
if (s[i] == '1') s[i] = 'l'
if (s[i] == '0') s[i] = 'o'
if (t[i] == '1') t[i] = 'l'
if (t[i] == '0') t[i] = 'o'
}
const sChar = s.join('')
const tChar = t.join('')
if (sChar == tChar) {
log('Yes')
} else {
log('No')
}
}
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 - Discord
N人の参加者がM回の集合写真を撮る際に、特定の2人が一度も連続して並ばなかった場合、それらの2人が不仲である可能性があるという設定。
不仲である可能性がある2人組の数を求める。
グラフっぽく隣になったことがある人を記録して、(N-隣になったことがある人)を足し上げていけばいい。二回足されるので、最後に２で割るのが注意。
function main() {
const [n, m] = nextNums(2)
const friends: Record<number, Set<number>> = {}
for (let i = 1; i < n + 1; i++) {
friends[i] = new Set([i])
}
for (let i = 0; i < m; i++) {
const arr = nextNums(n)
for (let j = 1; j < n; j++) {
const a = arr[j]
const b = arr[j-1]
friends[a].add(b)
friends[b].add(a)
}
}
let ans = 0
for (let i = 1; i < n + 1; i++) {
ans += n - friends[i].size
}
log(Number(ans/2))
}C - Dash
N ,M ,H ,Kが与えられる。
高橋君は二次元平面の原点(0,0)にいる。初めの体力はH。
平面上にはM個の体力を回復するアイテムがあり、それぞれが特定の位置(x_i, y_i)に置かれている。
高橋君はN回の移動を行う。各移動は体力を1消費し、指示に従って四方のいずれかに1ステップ移動します。指示は文字列Sの各文字によって与えられ、'R'は右へ、'L'は左へ、'U'は上へ、'D'は下へ移動します。
高橋君の体力が負になると移動をやめ、倒れる。
移動した先にアイテムがあり、高橋君の体力がK未満の場合、そのアイテムを消費して体力がKになる。
M個のアイテムがあるのだが、Mの制約は２０万までと大きいので、ポジションが変わるたびに全探索するのは厳しい。
dict[x_pos]=Set(y_pos,y_pos2,,,)というように管理すると、高速に判定できる。
アイテムを取得したら消費するので、削除することを忘れないようにする。
function main() {
const [n, m, h, k] = nextNums(4)
const s = next()
const items: Record<number, Set<number>> = {}
// 初期化
for (let i = -200001; i < 200002; i++) {
items[i] = new Set()
}
for (let i = 0; i < m; i++) {
const [x, y] = nextNums(2)
items[x].add(y)
}
let now_x = 0
let now_y = 0
let rem = h
for (let i = 0; i < n; i++) {
const char = s[i]
rem -= 1
if (rem < 0) {
log('No')
exit()
}
if (char == 'R') now_x++
if (char == 'L') now_x--
if (char == 'U') now_y++
if (char == 'D') now_y--
if (items[now_x].has(now_y)) {
if (rem < k) {
rem = k
// 消費する
items[now_x].delete(now_y)
}
}
}
log('Yes')
}D - Shift vs. CapsLock
キーボードにはaキー、Shiftキー、CapsLockキーの3つのキーがある。
aキーの押下はXミリ秒を必要とし、CapsLockキーのランプがOFFの場合は文字列の末尾に'a'を追加し、ONの場合は'A'を追加する。
Shiftキーとaキーを同時に押す操作はYミリ秒を必要とし、CapsLockキーのランプがOFFの場合は文字列の末尾に'A'を追加し、ONの場合は'a'を追加する。
CapsLockキーを押す操作はZミリ秒を必要とし、CapsLockキーのランプの状態を切り替える。
与えられた'A'と'a'からなる目標文字列Sを作り出すのに必要な最短の時間を求める。
凄くDPっぽい感じがする。
dp[i][OFF or ON]=capslockキーがOFFもしくはONの時にi文字目を入力するのに最小の時間とすればできそうか。
場合分けすると、分かりやすい。
今がOFFのとき：
次の文字がa：Xを使う、Z+Yを使う
次の文字がA：Yを使う、Z+Xを使う
今がONのとき：
次の文字がa：Yを使う、Z+Xを使う
次の文字がA：Xを使う、Z+Yを使う
function minBigInt(numbers: bigint[]): bigint {
let min = numbers[0];
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] < min) {
min = numbers[i];
}
}
return min;
}
function main() {
const [x, y, z] = nextBigInts(3)
const s = next()
const dp: bigint[][] = []
for (let i = 0; i < s.length + 1; i++) {
const arr = new Array(2).fill(BigInt(10 ** 18))
dp.push(arr)
}
dp[0][0] = 0n
// 最初にcapslockを押したとする
dp[0][1] = z
for (let i = 0; i < s.length; i++) {
const nxtChar = s[i]
let costSame = 0n
let costChange = 0n
for (let j = 0; j < 2; j++) {
if (j == 0) {
if (nxtChar == 'a') {
costSame = x
costChange = z + y
} else {
costSame = y
costChange = z + x
}
} else if (j == 1) {
if (nxtChar == 'a') {
costSame = y
costChange = z + x
} else {
costSame = x
costChange = z + y
}
}
// ON OFFを切り替えずに押した場合
dp[i + 1][j] = minBigInt([dp[i + 1][j], dp[i][j] + costSame])
// ON OFFを切り替えた場合
dp[i + 1][1 - j] = minBigInt([dp[i + 1][1 - j], dp[i][j] + costChange])
}
}
const ans = minBigInt(dp[s.length])
log(String(ans))
}E - A Gift From the Stars
初期状態として星型のグラフがいくつかある場合を想定する。
以下の条件を満たす k+1 頂点 k 辺のグラフをレベル k (k≥2) の星と呼ぶ。
ある 1 つの頂点が、他の k 個の頂点と 1 本ずつ辺で結ばれている。それ以外の辺は存在しない。
このような状態から、すべての星形グラフが連結するまで、次の手順を繰り返す。
非連結の星形グラフの頂点を2つ選び、それらを結ぶ辺を追加する。ただし、選ばれた2つの頂点の次数は共に1である必要がある。
この手順を繰り返した後のグラフの情報が与えられる。
もともとの星型グラフのレベルを出力する、という問題。
解けなかったけど、とても良い問題だと思った。
まず星型のグラフを適当に書いてみる。
赤くなっているところが中心。
次にこれを次数が１のところを適当につなげていってみる。
青い線が追加した辺。
ここで重要な考察として、辺をつなげても、中心のレベル（=つながっている辺の数）は変わらない。
ということは、中心の頂点を特定できれば、入力から辺の数を数えるだけでいい、ということが分かる。
次に左下の頂点から各頂点への距離を出してみる。
各星は衛星同士がつながっている。
そのため、星の中心から別の星の中心への距離は、必ず３の倍数になる。
つまり、まず適当な中心を見つけて、BFSをして距離を出せば解けることが分かる。
class Node<T> {
public value: T;
public prev: Node<T> | null;
public next: Node<T> | null;
constructor(value: T) {
this.value = value;
this.prev = null;
this.next = null;
}
}
export class Deque<T> {
private head: Node<T> | null = null;
private tail: Node<T> | null = null;
private length = 0;
public append(value: T): void {
const node = new Node(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail!.next = node;
this.tail = node;
}
this.length++;
}
public appendleft(value: T): void {
const node = new Node(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head!.prev = node;
this.head = node;
}
this.length++;
}
public pop(): T | null {
if (!this.tail) {
return null;
}
const node = this.tail;
if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.tail = node.prev;
this.tail!.next = null;
node.prev = null;
}
this.length--;
return node.value;
}
public popleft(): T | null {
if (!this.head) {
return null;
}
const node = this.head;
if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.head = node.next;
this.head!.prev = null;
node.next = null;
}
this.length--;
return node.value;
}
public getLength(): number {
return this.length;
}
public toArray(): T[] {
const result: T[] = [];
let current = this.head;
while (current) {
result.push(current.value);
current = current.next;
}
return result;
}
}
function main() {
const n = nextNum()
const graph: Record<number, number[]> = {}
// 初期化
for (let i = 1; i < n + 1; i++) {
graph[i] = []
}
// 木を構築
for (let i = 0; i < n - 1; i++) {
const [u, v] = nextNums(2)
graph[u].push(v)
graph[v].push(u)
}
// 適当な開始する中心点を見つける
let firstCenter = 0
for (let i = 1; i < n + 1; i++) {
// 次数が１の頂点と接続している点が中心
if (graph[i].length == 1) {
firstCenter = graph[i][0]
break
}
}
// 両端キューを用意
const que = new Deque<number>()
// 頂点番号、距離を保持
que.append(firstCenter)
// 訪問済みの頂点を記録
const vis: Set<number> = new Set()
vis.add(firstCenter)
// 距離を記録
const dist: number[] = new Array(n + 1).fill(-1)
// 開始頂点を0にする
dist[firstCenter] = 0
// BFSする
while (que.getLength() > 0) {
const now = que.popleft()!
for (const ver of graph[now]) {
if (vis.has(ver)) continue
vis.add(ver)
dist[ver] = dist[now] + 1
que.append(ver)
}
}
// 中心点を調べる
const centerPoints: number[] = []
for (let i = 1; i < n + 1; i++) {
if (dist[i] % 3 == 0) centerPoints.push(i)
}
// レベルを記録する
const levels = []
for (const centerPoint of centerPoints) {
const level = graph[centerPoint].length
levels.push(level)
}
// ソートして出力
levels.sort((a, b) => a - b)
log(levels.join(' '))
}
解説によると簡単な別解もある。
次数が３以上の点は必ず中心になるという性質もあるらしい。
ということは、残った頂点はかならずレベル２の星を構成している。
さきほどの図でいくと、こういうイメージ。６個余ってるので、レベル２の星が２つあるという感じ。これは気づかなかった。天才か。
function main() {
const n = nextNum()
const graph: Record<number, number[]> = {}
// 初期化
for (let i = 1; i < n + 1; i++) {
graph[i] = []
}
// 木を構築
for (let i = 0; i < n - 1; i++) {
const [u, v] = nextNums(2)
graph[u].push(v)
graph[v].push(u)
}
const levels: number[] = []
// 使用頂点数
let useCount = 0
// レベル３以上を調べる
for (let i = 1; i < n + 1; i++) {
if (graph[i].length >= 3) {
levels.push(graph[i].length)
// その頂点自身を使っている
useCount++
// 接続している頂点を使っている
useCount += graph[i].length
}
}
// 残っている頂点数
const remainCount = n - useCount
// 星の数
const starCount = Number(remainCount / 3)
// level２を追加
for (let i = 0; i < starCount; i++) {
levels.push(2)
}
levels.sort((a, b) => a - b)
log(levels.join(' '))
}おわりに
AからEまでそれぞれに考えるポイントがあり、良い問題セットだったと思った。ではでは。
この記事が気に入ったらサポートをしてみませんか？