AtCoder Beginner Contest 317 A-EをTypeScriptで解く。
久しぶりです！
ここのところは自分の日記の方でコンテストの振り返りを書いたりしていたのですが、やっぱりnoteで書いていくにしました。
コンテスト自体はPythonで参加をしたのですが、Typescriptで振り返り記事を書いていきます！
結果
A-E５完１ペナでパフォ1487相当でした。順位も1,111位とこれまでで、最高だった気がします。
Qlitreさんのゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）での成績：1111位
— QLITRE (@kuri_tter) August 26, 2023
パフォーマンス：1487相当
レーティング：1089→1136 (+47) :)
Highestを更新しました！#AtCoder #ゲームフリークProgrammingContest2023（ABC317） https://t.co/gdeuU5dDbS
私事ですが、先週の金曜日に痔の手術を受けまして、コンディションが不安でした。しかし、良い施術だったのかコンテスト中はあまり痛みを気にせずに楽しめました。先生に感謝です。
それでは早速コンテストの振り返りを行っていきます。
A - Potions
N個の傷薬とモンスターの体力H、Xが与えられます。
傷薬を使うと体力Hが増加します。体力がX以上になる最小の傷薬の番号を出力する、という問題です。
傷薬自体はソートされた状態で与えられるので、単純に検証していって、最初にX以上になる番号を出力すればよいです。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [n, h, x] = nextNums(3);
const arr = nextNums(n);
for (let i = 0; i < n; i++) {
if (arr[i] + h >= x) {
log(i + 1);
exit();
}
}
}
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 - MissingNo.
ナオヒロ君はもともとN+1個の連続した整数を持っていたが、１個なくしてしまった。残った整数が与えられるので、なくした整数を求める、という問題です。
制約を見ると、答えは一意になる、とあるので、単純に抜けている番号が途中にあります。素直に前後を比較します。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const n = nextNum();
const arr = nextNums(n);
arr.sort((a, b) => a - b);
for (let i = 1; i < n; i++) {
const now = arr[i];
const prev = arr[i - 1];
if (now - prev > 1) {
const ans = prev + 1;
log(ans);
exit();
}
}
}C - Remembering the Days
N個の街と、その街を結ぶM個の道路が与えられます。道路にはそれぞれかかる長さが与えられます。
好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求める、という問題です。
この手の問題は最短距離を求めるものが多いように思いますが、今回は最大距離を求めるという問題です。
制約に目を向けてみると、Nの最大値が10と小さいので、順列全列挙をして、探索するのが簡単でしょうか。
ただ、Pythonなどではitertools.permutationで標準で呼び出せますが、TypeScriptにはないので、dfsで全探索をします。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [n, m] = nextNums(2);
const graph: Record<number, number[][]> = {};
// グラフの構築
for (let i = 0; i < m; ++i) {
let [a, b, c] = nextNums(3);
a--;
b--;
if (graph[a] == undefined) graph[a] = [];
if (graph[b] == undefined) graph[b] = [];
graph[a].push([b, c]);
graph[b].push([a, c]);
}
function dfs(u: number, length: number, vis: boolean[]): number {
let maxLength = length;
// 訪れたのでtrue
vis[u] = true;
if (graph[u] == undefined) {
vis[u] = false;
return length;
};
for (let [v, c] of graph[u]) {
if (vis[v]) continue;
// 未訪問なら訪問する
maxLength = Math.max(maxLength, dfs(v, length + c, vis));
}
// 戻ってきたらfalse
vis[u] = false;
// 最長の長さを返す
return maxLength;
}
const vis: boolean[] = new Array(n).fill(false);
let ans = 0;
for (let i = 0; i < n; i++) {
ans = Math.max(ans, dfs(i, 0, vis));
}
log(ans);
}個人的にdfsが苦手なので、しっかりと書けるように練習をしていきたいです。
D - President
N個の選挙区があり、それぞれに高橋君の有権者X人と青木君の有権者Y人が与えられます。またその選挙区が持っている議席数がZとして与えられます。
選挙区全体で過半数の議席数を得るには、最低で何人、青木派から高橋派に鞍替えさせる必要があるか？という問題です。
一見して貪欲っぽいかな？と思いました。しかしながら、例えば議席数が多い順で…とやると、その選挙区でたくさんの鞍替えが必要になるかもしれません。すこし考えると単純な貪欲で解けないことが分かります。
鞍替え人数、議席数、それぞれの選挙区という三つの要素を考える必要があるので、動的計画法で解けそうな気がします。議席数Zの最大は10^5までと比較的小さく、選挙区は1-100までなので、以下のようにできそうです。
DP[i][j] : i番目の選挙区で議席数ｊを獲得する時の最小の鞍替え人数
よくあるナップサック問題と同じような感じの遷移で解いていくことができます。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const n = nextNum();
const costs: number[] = [];
const seats: number[] = [];
let totalSeat = 0;
for (let i = 0; i < n; ++i) {
const [x, y, z] = nextNums(3);
// zを獲得するのに必要な人数を計算
const tot = x + y;
const half = Math.ceil(tot / 2);
const cost = Math.max(0, half - x);
costs.push(cost);
seats.push(z);
totalSeat += z;
}
const inf: number = 10 ** 11
const dp: number[][] = [];
for (let i = 0; i <= n; ++i) {
const arr: number[] = new Array(totalSeat + 1).fill(inf);
dp.push(arr);
}
dp[0][0] = 0;
// 配るdp
for (let i = 0; i < n; i++) {
const cost = costs[i];
const seat = seats[i];
for (let j = 0; j <= totalSeat; j++) {
dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j]);
if (j + seat <= totalSeat) {
dp[i + 1][j + seat] = Math.min(dp[i + 1][j + seat], dp[i][j] + cost);
}
}
}
let ans = inf;
const half = Math.ceil(totalSeat / 2);
for (let i = half; i <= totalSeat; ++i) {
ans = Math.min(ans, dp[n][i]);
}
log(ans);
}
E - Avoid Eye Contact
以下のマスからなるH x W行のグリッドが与えられます。
. : 空きマス。進入できる。
# : 障害物。進入できない。
>, v, <, ^ : それぞれ東・南・西・北を向いている人がいるマス。進入できない。人の視線は
1マス分の幅を持ち、人が向いている方向にまっすぐ伸び、障害物や別の人に遮られる。
S : スタート地点。進入できる。
G : ゴール地点。進入できる。Sからスタートして人の視点に入らずにGまでたどり着けるか、たどり着ける場合は最小の移動数を出力する、という問題です。
これは面白い！と思いました。
今回はゲームフリーク社のコンテストということもあり、ポケモンのネタです。トレーナーの視線にみつかるとバトルが始まる、という例のやつです。
さて、問題に目を向けると、HとWは制約が2000までと比較的小さいです。そのため、事前に侵入できないマスをマーキングしておけば間に合いそうな感じがします。
一番計算量が大きいのがこういう感じでしょうか。
最大のマス目数が4,000,000ほどで、それぞれの方角で約4,000,000塗られる可能性があります。それでも合計は20,000,000ほどなので、なんとか間に合うかな、という数字です。
あとは地道にBFSをすると正解にたどり着けます。
割と重実装な問題ですが、それぞれの方角の目線とインデックスを合わせる形で進む方角の変化量を用意しておくとちょっとすっきりするでしょうか。
こうしておくと、目線マスにぶつかった時にインデックスを取得すれば、if文の数が減ります。
// 方角
const dirChar: string[] = ['>', 'v', '<', '^']
// 方角ごとの変化量
const di: number[][] = [[0, 1], [1, 0], [0, -1], [-1, 0]]import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [h, w] = nextNums(2);
// gridの入力を受け取る
const grid: string[][] = [];
for (let i = 0; i < h; ++i) {
const row = next().split('');
grid.push(row);
}
// スタートとゴール
let startR = 0
let startC = 0
let goalR = 0
let goalC = 0
// 侵入できない場所を記録する
const blocked: boolean[][] = [];
for (let i = 0; i < h; ++i) {
const row: boolean[] = new Array(w).fill(false)
blocked.push(row)
}
// 方角
const dirChar: string[] = ['>', 'v', '<', '^']
// 方角ごとの変化量
const di: number[][] = [[0, 1], [1, 0], [0, -1], [-1, 0]]
// 前処理
for (let r = 0; r < h; ++r) {
for (let c = 0; c < w; c++) {
const char = grid[r][c];
if (char == '.') continue
if (char === "#") {
blocked[r][c] = true;
} else if (char == 'S') {
startR = r
startC = c
} else if (char == 'G') {
goalR = r
goalC = c
} else {
// 方角マスにぶつかった
blocked[r][c] = true
// 進む方角を取得してblockedを更新する
const idx = dirChar.indexOf(char)
const addR = di[idx][0]
const addC = di[idx][1]
let nr = r + addR
let nc = c + addC
while (0 <= nr && nr < h && 0 <= nc && nc < w) {
if (grid[nr][nc] == '.') {
blocked[nr][nc] = true
nr += addR
nc += addC
} else {
break
}
}
}
}
}
// BFSする
const que: number[][] = []
// 距離を記録する配列
const dist: number[][] = []
for (let r = 0; r < h; ++r) {
const row: number[] = new Array(w).fill(-1)
dist.push(row)
}
// スタート地点の距離は0
dist[startR][startC] = 0
// スタート地点をqueに入れる
que.push([startR, startC])
while (que.length > 0) {
const [r, c] = que.shift()!
// 4方向に移動する
for (let i = 0; i < 4; ++i) {
const nr = r + di[i][0]
const nc = c + di[i][1]
if (0 <= nr && nr < h && 0 <= nc && nc < w) {
if (!blocked[nr][nc] && dist[nr][nc] == -1) {
que.push([nr, nc])
dist[nr][nc] = dist[r][c] + 1
}
}
}
}
log(dist[goalR][goalC])
}
おわりに
F問題からはさっぱり分からずでした。壁を感じ始めています。ではでは。
この記事が気に入ったらサポートをしてみませんか？