AtCoder Beginner Contest 374
A~Dの4完(20分)でした。
1358perfでレートは783->856(+73)と大幅アップし入緑できました!
(入緑記事は後ほど公開します!)
今回はA~Dの解説を行います。
A - Takahashi san 2
入力は必ず4文字以上であることが保証されています。
なので後ろから文字を3つ取ってきて、san
と一致するかを確認すれば良いです。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const S = input[0].split("");
let ans = "";
for (let i = S.length - 3; i < S.length; i++) ans += S[i];
ans === "san" ? console.log("Yes") : console.log("No");
}
Main(require("fs").readFileSync(0, "utf8"));
B - Unvarnished Report
入力$S, T$のうち、文字列長が長い方の長さを$len$とすれば、1番目から$len$番目まで$S, T$の文字を比較して、文字が異なった時点でそのインデックスを出力し、異なるものがなければ0
を出力する方法で簡単に書けます。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const S = input[0].split("");
const T = input[1].split("");
let len = Math.max(S.length, T.length);
for (let i = 0; i < len; i++) {
if (S[i] !== T[i]) return console.log(i + 1);
}
console.log(0);
}
Main(require("fs").readFileSync(0, "utf8"));
C - Separated Lunch
bit全探索
を知っていますか?という問題です。
bit全探索
を知らない人向けに、少しわかりやすく解説してみます。
簡単のため、$N=5$で考えてみましょう。
$N$個の部署を$A,B$の2グループに分けるような場合、実は2進数表現の00000
〜11111
で全通りを列挙することができます。ここで、部署$i$($1≦i≦N$)は上から$i$番目の数値に対応し、0
であれば$A$グループ、1
であれば$B$グループに所属していることにします。例えば、10110
であれば、$[2,5]$は$A$グループ、$[1,3,4]$は$B$グループに所属していることになります。
グループ分けさえできてしまえば、あとは部署を先頭から1つずつみていき、所属するグループの方に部署の人数を足していけば両方のグループの人数が集計できますね。
下のACコードでは、あらかじめ会社全体の人数$total$を計算しておいて、ループでは$B$グループの人数$sum$だけ集計しておき、$A$グループの人数は$total-sum$で求めています。$sum$と$total-sum$のうち大きい方の最小値が問題で聞かれていることなので、ややこしいですが気をつけてください。
なお、$N≦20$ですが、グループ分けのパターンは高々$2^{20}$通りしかなく、$2^{10}≒10^{3}$なのでだいたい$10^6$くらいだとわかります。また、各グループ分けについて部署ごとに集計する必要があるので、全体としては$O(N*2^{N})$となり、問題なく間に合うことがわかりました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const K = input[1].split(" ").map(Number);
let total = K.reduce((acc, cur) => acc + cur, 0);
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 2 ** N; i++) {
let sum = 0;
for (let j = 0; j < N; j++) sum += K[j] * ((i >> j) & 1);
let max = Math.max(sum, total - sum);
ans = Math.min(ans, max);
}
console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));
D - Laser Marking
bit全探索
と、順列全探索
を知っていますか?という問題です。
なぜ、これらのテクニックを使うことになるのか初心者向けに解説します。
まず、問題をそのまま解くのは難しいので、$N$個の線分$[A_i,B_i]-[C_i,D_i]$を$N$個の点$[A_i,B_i]$に圧縮し、全ての点を踏破する問題に置き換えて考えてみます。
この問題において、もし点が3個ありそれぞれ$0,1,2$という名前がついているとすると、$[0,1,2]$,$[0,2,1]$,$[1,0,2]$,$[1,2,0]$,$[2,0,1]$,$[2,1,0]$のように$3!=6$通りの訪れ方があります。この訪れ方を全列挙する方法として、順列全探索を用います。全ての点を踏破する問題であれば、列挙した訪れ方をシミュレートして最短の移動時間を求めればよいです。
元に戻り、$N$個の線分$[A_i,B_i]-[C_i,D_i]$を全て描画する問題を考えましょう。 $N$個の点を踏破する問題と異なるのは、以下の2つです。
- 線分を描画する速度$T$と、ある線分からある線分まで移動する速度$S$は区別される
- 線分の$[A_i,B_i]$、$[C_i,D_i]$どちらをスタートにしてもよい
一つ目については、線分を描画するときは線分の長さを$T$で割り、描画していないときは移動距離を$S$で割れば対応できそうです。
二つ目については、線分の端点のどちらをスタート地点とするかを全列挙すればよく、実はこれもbit全探索でスマートに書くことができます。
例として、$N=3$の時を考えます。各線分について、$[A_i,B_i]$側をスタート地点とするか、$[C_i,D_i]$側をスタート地点とするかは、2進数表現000
〜111
でぱたーん全列挙できます。なお、0
は$[A_i,B_i]$側をスタート地点、1
は$[C_i,D_i]$側をスタート地点としていることを表します。
例えば、101
ならば1,3番目の線分は$[C_i,D_i]$側をスタート地点とし、2番目の線分は$[A_i,B_i]$側をスタート地点としていることになります。
以上のように、順列全探索
とbit全探索
を組み合わせることで、「線分をどの順番で描画するか」と「各線分について、どちらの方向で描画するか」の両方について全列挙することができます。全列挙ができたら、あとは設定された通りに描画していってかかった時間を計算すればよく、全体としては$O(N!×2^N)$でこの問題を解くことができます。今回は$N<=6$のため高々$46080$通りしかないので、この方法で十分に間に合いました。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, S, T] = input[0].split(" ").map(Number);
const A = [],
B = [],
C = [],
D = [];
for (let i = 0; i < N; i++) [A[i], B[i], C[i], D[i]] = input[i + 1].split(" ").map(Number);
const perms = generatePermutations(
Array(N)
.fill(0)
.map((_, i) => i)
);
const calcDist = (x1, y1, x2, y2) => Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
let ans = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < 2 ** N; i++) {
for (let j = 0; j < perms.length; j++) {
let sec = 0;
let x = 0;
let y = 0;
for (let k = 0; k < N; k++) {
if (i & (1 << k)) {
sec += calcDist(x, y, A[perms[j][k]], B[perms[j][k]]) / S;
sec += calcDist(A[perms[j][k]], B[perms[j][k]], C[perms[j][k]], D[perms[j][k]]) / T;
x = C[perms[j][k]];
y = D[perms[j][k]];
} else {
sec += calcDist(x, y, C[perms[j][k]], D[perms[j][k]]) / S;
sec += calcDist(C[perms[j][k]], D[perms[j][k]], A[perms[j][k]], B[perms[j][k]]) / T;
x = A[perms[j][k]];
y = B[perms[j][k]];
}
}
ans = Math.min(ans, sec);
}
}
console.log(ans);
}
function nextPermutation(arr) {
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
for (let j = arr.length - 1; j > i; j--) {
if (arr[j] > arr[i]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
const len = (arr.length - (i + 1)) >> 1;
for (let k = 0; k < len; k++) {
[arr[i + 1 + k], arr[arr.length - 1 - k]] = [arr[arr.length - 1 - k], arr[i + 1 + k]];
}
return true;
}
}
}
}
return false;
}
// 順列生成器。配列を配列として返すため、文字列が欲しい場合はjoin("")で結合する必要がある
// 配列用にスプレッド構文を使用しているが、遅いので文字列を出力する場合はjoin("")に書き換える
const generatePermutations = (arr) => {
let sorted = arr.sort();
const res = [[...sorted]];
while (nextPermutation(sorted)) res.push([...sorted]);
return res;
};
Main(require("fs").readFileSync(0, "utf8"));
余談ですが、本問題はabc369 - Eの類題となります。ベルマンフォード法を知っていれば今回のD問題のちょうどいい理解の確認になると思いますので、解いてない方は是非解いてみてください。