AtCoder Beginner Contest 318 A-EをTypeScriptで解く。
今週もAtCoderの振り返りです。
コンテスト自体はPythonで参加をしたのですが、Typescriptで振り返り記事を書いていきます。
結果
A-D 4完、パフォ1016相当、2909位となりました。
ここのところ連続してHighestを更新できていたのですが、今回はレートが下がってしまいました。
QlitreさんのTHIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）での成績：2909位
— QLITRE (@kuri_tter) September 2, 2023
パフォーマンス：1016相当
レーティング：1136→1124 (-12) :(#AtCoder #THIRDプログラミングコンテスト2023アルゴ（ABC318） https://t.co/LghSsvfrFm
それでは早速振り返りを行っていきます。
A - Full Moon
N,M,Pが与えられて最初のM日目に満月が見られます。その後はP日ごとに満月を見ることができます。N日目までに何回満月を見られるかを出力する問題です。
A問題ということを考えると少し難しいと思いました。
幸いにしてNの制約はそこまで大きくないので、for文などで探索的に解くのが簡単でしょうか。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [n, m, p] = nextNums(3);
let ans = 0;
for (let i = 0; i < 1000000; i++) {
if (m + i * p <= n) {
ans++;
} else {
break;
}
}
log(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 - Overlapping sheets
座標平面上に N 枚の長方形のシートが張られていま。各シートが覆う長方形領域の各辺は x 軸または y 軸に平行です。
i 枚目のシートは以下の条件を満たす領域を覆っています
x 座標の範囲: A_i ≤ x ≤ B_i
y 座標の範囲: C_i ≤ y ≤ D_i
少なくとも1枚以上のシートによって覆われている領域の面積を S を出力する問題です。
２次元いもす法がちらつく問題でしたが、Nの制約とA,B,C,Dの制約は100までと小さいので、愚直に全探索してマーキングしても充分に間に合います。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const n = nextNum();
const grid: number[][] = [];
for (let i = 0; i < 150; i++) {
const arr = new Array(150).fill(0);
grid.push(arr);
}
for (let i = 0; i < n; i++) {
const [a, b, c, d] = nextNums(4);
for (let i = c; i < d; i++) {
for (let j = a; j < b; j++) {
grid[i][j] = 1;
}
}
}
let ans = 0;
for (let i = 0; i < 150; i++) {
for (let j = 0; j < 150; j++) {
ans += grid[i][j];
}
}
log(ans);
}C - Blue Spring
高橋君は、N 日間の鉄道旅行を計画しています。各日について、彼は運賃の通常料金を支払うか、または 1 日周遊パスを 1 枚使用するかを選択できます。
各日の通常料金は F_i 円であり、また、1 日周遊パスは D 枚セットで P 円で購入可能です。このパスは 1 枚ずつ、任意の日に使用できます。
適切な選択をしてN 日間の旅行でかかる最小金額を求めるという問題です。
問題の意味を理解するのに時間がかかりましたが、まさに青春18切符ですね。予め配列をソートしておいて、周遊券を使った場合が得な場合は周遊券を使う、というように貪欲的なアプローチで解くことができます。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const [n, d, p] = nextNums(3);
const arr = nextNums(n);
// 降順でソート
arr.sort((a, b) => b - a);
const stack = [];
let ans = 0
let sumVal = 0;
for (let i = 0; i < n; ++i) {
// stackに数字を加える
stack.push(arr[i])
sumVal += arr[i];
// stackの長さがdになったら、合計とPの小さい方を加算する
if (stack.length == d) {
ans += Math.min(sumVal, p);
stack.length = 0;
sumVal = 0;
}
}
// stackに残った数字を加算する
if (stack.length > 0) {
const sumVal = stack.reduce((a, b) => a + b, 0);
ans += Math.min(sumVal, p);
}
log(ans);
}D - General Weighted Max Matching
与えられた N 頂点の重み付き無向完全グラフにおいて、頂点 i と頂点 j (i < j) を結ぶ辺の重みを D_i,j とします。
次の条件を満たすように、いくつかの辺を選ぶ際に、選んだ辺の重みの総和として考えられる最大値を求めたいです。
選んだ辺の端点は全て異なる。
Nの大きさが16までと小さいので、bitDPを使って解きました。
dp[mask]:集合の最大重み
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";
function main() {
const n = nextNum();
// edgeを用意
const edges: number[][] = [];
for (let i = 0; i < n; ++i) {
const arr = new Array(n).fill(0);
edges.push(arr);
}
for (let i = 0; i < n - 1; i++) {
const arr = nextNums(n - i - 1);
for (let j = 0; j < n - i - 1; j++) {
edges[i][i + j + 1] = arr[j];
edges[i + j + 1][i] = arr[j];
}
}
const dp: number[] = new Array(1 << n).fill(-1);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); ++mask) {
if (dp[mask] == -1) continue;
for (let i = 0; i < n; ++i) {
// iが含まれている場合はスキップ
if (mask & (1 << i)) continue;
for (let j = i + 1; j < n; ++j) {
// jが含まれている場合はスキップ
if (mask & (1 << j)) continue;
// iとjの間の辺を使ってmaskを更新する
const newMask = mask | (1 << i) | (1 << j);
dp[newMask] = Math.max(dp[newMask], dp[mask] + edges[i][j]);
}
}
}
let ans = 0;
for (const num of dp) {
ans = Math.max(ans, num);
}
log(ans);
}E - Sandwiches
整数列が与えられて以下の条件を満たすi, j, kの組み合わせ数を求める問題です。
1 < i< j < k <= N
Ai = Ak
Ai != Aj
タイトルの通り、サンドイッチのように同じ数字にはさまれたインデックスの組み合わせ数を求めるイメージでしょうか。
数字ごとにインデックスを記録するところまでは思いついたのですが、そこからの計算方法を思いつくことができませんでした。
以下は解説を見ながらの整理となります。
例えばある数字が以下のインデックスで配置されていることを考えます。
2 8 10 12まず、２と８の間には５個の数字（３～７）があるので、８まで来た時には、５個だけ答えを増やせます。
次に１０まで来た時はどうでしょうか。
まず、明らかに左端を２、右端を１０としたときに（３～７）を選択できます。
そのため、まず５個だけ答えを増やせます。
続いて、１０と８の間の９も選択できるようになったので、
２－９－１０
８－９ー１０
この２個も答えに加えられる。
元々の５個に加えて計７個答えを増やせます。
最後に１２まで来た際は、これまでの７個に加えて、
２－１１－１２
８－１１－１２
１０－１１－１２
この３つも追加できるようになります。
まとめると、
出現個数 cnt
最後のインデックス pre
答えに足せる組み合わせ数 inc
の三つを記録していくと答えを足し上げていけそうです。
答えに足せる組み合わせ数 incはcnt[num] * (i-pre[num]-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);
// 出現個数
const cnt = new Array(n + 1).fill(0);
// 最後のインデックス
const pre = new Array(n + 1).fill(0);
// 答えに足す増分
const inc = new Array(n + 1).fill(0);
let ans = 0;
for (let i = 0; i < n; i++) {
const num = arr[i];
// これまでの出現個数 * (今回のインデックス - 前回のインデックス - 1)だけ答えを増やせる
inc[num] += cnt[num] * (i - pre[num] - 1);
ans += inc[num];
cnt[num]++;
pre[num] = i;
}
log(ans);
}おわりに
E問題ができそうでできなかったのが悔しい、この悔しさをばねに引き続き精進していこうと思います。ではでは。
この記事が気に入ったらサポートをしてみませんか？