AtCoder Beginner Contest 414
前回に引き続きunrated参加です。
ABCDの4完（42分1ペナ）でした。
AtCoder Rating Predictorは1211perfを示しています。
今回はA〜Dをまとめます。
A - Streamer Takahashi
下図のように、$X_i \le L$かつ$Y_i \ge R$のとき、リスナーは高橋くんの配信を全て視聴することができます。
$L<R$が保証されているため、これ以外の場合にリスナーが高橋くんの配信を全て視聴することはできません。
以下の解答コードでは、ドモルガンの法則を利用して$X_i > L$または$Y_i < R$のときにそのリスナー$i$をスキップとしています。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, L, R] = input[0].split(" ").map(Number);
const [X, Y] = [[], []];
for (let i = 0; i < N; i++) [X[i], Y[i]] = input[i + 1].split(" ").map(Number);
let ans = 0;
for (let i = 0; i < N; i++) {
if (X[i] > L || Y[i] < R) continue;
ans++;
}
console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));
B - String Too Long
問題はシンプルで、文字列$c_i$を$l_i$個順次結合していき、文字列$S$の長さが$101$以上になったらToo Longを出力すればよいです。
ただし、$l_i \le 10^{18}$と非常に大きいことが厄介で、基本的に$10^8$を超える結合回数になるとTLEになってしまうと思って良いです。
解決策として、$l_i > 100$の場合は文字列$S$の長さが$101$以上になることは確定なので、実際に文字列を連結する必要はなく、その場でToo Longを出力して終了すれば良いです。
以下の解答コードでは、$l_i > 100$のときその場でToo Longを出力する代わりに、$c_i$を$101$個だけ結合してループを抜け、文字列$S$の長さが$100$より大きければToo Longを出力しています。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const [c, l] = [[], []];
for (let i = 0; i < N; i++) {
[c[i], l[i]] = input[i + 1].split(" ");
}
let S = "";
for (let i = 0; i < N; i++) {
l[i] = BigInt(l[i]);
if (l[i] > 100n) {
S += c[i].repeat(101);
break;
} else S += c[i].repeat(Number(l[i]));
}
if (S.length > 100) console.log("Too Long");
else console.log(S);
}
Main(require("fs").readFileSync(0, "utf8"));
C - Palindromic in Both Bases
まず、JavaScriptではtoString(n)メソッドを利用することで、Number型プリミティブを$\text{n}$進数の文字列に変換することができます（$2 \le n \le 36$）。
Number.prototype.toString()
もし$N$以下の$10$進法における全ての回文を列挙できたとすると、toString(A)メソッドを利用することで、さらにそれらが$\text{A}$進法でも回文かどうかを判定して数え上げを行うことができます。
それでは、$10$進法における回文の高速な列挙方法を考えましょう。
$N \le 10^{12}$と$N$が非常に大きいため、$1$から$N$まで愚直に一つずつ回文かどうかを判定するのでは到底間に合いません。
そこで、回文の「真ん中より左の文字列は、真ん中より右の文字列を反転したものと等しい」という性質に着目しましょう。例えば、1221は12と21に分けることができ、21を反転させると12に等しいです。
つまり、右半分は左半分を反転させたものにすぎないので、左半分さえ全列挙できれば良さそうです。
1221であれば、12という情報だけで復元することができます。$N$の最大桁数は$12$なので、左半分の全列挙は$10^6$までの全探索で済みます。この計算量であれば、十分に間に合う目処が立ってきました。
しかし、以上の議論では桁数が奇数の場合を無視してきました。
桁数が奇数の場合は左半分の一番右の桁が、右半分の一番左の桁と重複すると考え、右半分の一番左の桁をあらかじめ削除して結合すればよいです。
例えば、12という文字列を反転させると21ですが、2は重複するため右半分からあらかじめ削除しておき、12$+$1$=$121という、桁数が奇数の回文を復元できました。
まとめると、$1$から$10^6$までの数字について、桁数が偶数の回文と奇数の回文を生成し、$\text{A}$進法においても回文になっているかどうかを確認し、回文かつそもそも$N$であれば問題の条件を満たす数字なので足し上げていきます。
回文復元に$O(\sqrt N logN )$、回文判定に$O(logN)$のため、全体計算量は$O(\sqrt N logN )$となり、これは十分に高速です。
ただし、上記の解法をJavaScriptで書いて提出するとアルゴリズムのオーダー的には問題ないにも関わらずTLEとなるので、本番ではAtCoderのルールに則りC++に変換してから提出してACできました。JavaScriptは競プロに向かない言語なので仕方ないでしょう。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const A = Number(input[0]);
const N = Number(input[1]);
const getAsinhou = (a, n) => {
return n.toString(a);
}
let ans = 0n;
for (let i = 1; i <= 10 ** 6; i++) {
if (i > N) break;
let s1 = Number(i.toString() + i.toString().split("").reverse().join(""));
let s2 = Number(i.toString() + i.toString().split("").reverse().slice(1).join(""));
let s1Asinhou = getAsinhou(A, s1);
let s2Asinhou = getAsinhou(A, s2);
if (isKaibun(s1Asinhou) && s1 <= N) ans += BigInt(s1);
if (isKaibun(s2Asinhou) && s2 <= N) ans += BigInt(s2);
}
console.log(ans.toString());
}
const isKaibun = (S) => {
for (let i = 0; i < S.length / 2; i++) {
if (S[i] !== S[S.length - 1 - i]) return false;
}
return true;
};
Main(require("fs").readFileSync(0, "utf8"));
#include <bits/stdc++.h>
using namespace std;
string getAsinhou(int a, long long n) {
if (n == 0) return "0";
string result = "";
while (n > 0) {
result = char('0' + (n % a)) + result;
n /= a;
}
return result;
}
bool isKaibun(const string& S) {
for (int i = 0; i < S.length() / 2; i++) {
if (S[i] != S[S.length() - 1 - i]) return false;
}
return true;
}
string reverseString(const string& s) {
string reversed = s;
reverse(reversed.begin(), reversed.end());
return reversed;
}
int main() {
int A;
long long N;
cin >> A >> N;
long long ans = 0;
for (int i = 1; i <= 1000000; i++) {
if (i > N) break;
string iStr = to_string(i);
string reversed = reverseString(iStr);
// s1: concatenate i + reverse(i)
string s1Str = iStr + reversed;
long long s1 = stoll(s1Str);
// s2: concatenate i + reverse(i).slice(1)
string s2Str = iStr + reversed.substr(1);
long long s2 = stoll(s2Str);
string s1Asinhou = getAsinhou(A, s1);
string s2Asinhou = getAsinhou(A, s2);
if (isKaibun(s1Asinhou) && s1 <= N) {
ans += s1;
}
if (isKaibun(s2Asinhou) && s2 <= N) {
ans += s2;
}
}
cout << ans << endl;
return 0;
}
D - Transmission Mission
この問題は貪欲法とUnionFindというテクニックで解くことができます。
まず、サンプル１をもとに問題の条件を整理しましょう。
わかりやすいように昇順ソートします。
例）サンプル１
7 3
5 10 15 20 8 14 15
↓ 昇順ソート
5 8 10 14 15 15 20
求めるべきは、ちょうど$3$つの基地局を設置して、電波強度の総和が最小となるような値です。
ここで、そのような最適状態においては明らかに以下の条件が成立します。
- 基地局の電波が届く範囲は重複しない
- 基地局の電波が届く範囲の左端と右端には必ず家がある
重複する部分や余っている部分がある場合はそれを削ることによって電波強度の総和をさらに小さくすることができるからです。
そうすると、この問題を次のように言い換えることができます。
問題文の言い換え
「$7$つの家を連続する$3$つのグループに分けた時、グループの左端から右端までの距離の総和の最小値はいくつか？」
例えば、サンプル１の場合は次のようにグループ分けしたときに最小値を得ます。
5 8 10 | 14 15 15 | 20
[5,8,10],[14,15,15],[20]に分けたときに最小値6を得る
では、どのような規則に従ってグループ分けをすることでこの最小値を得られるでしょうか。
全ての家が独立した$7$つのグループを初期状態とします。
隣接するグループを一回結合するたびにグループの数は一つずつ減っていくため、$3$つのグループに分けるためにはちょうど$4$回だけ隣接するグループを結合する必要があります。
つまり、$4$回結合させた結果、残った$3$つのグループの範囲$[l_i, r_i] (i=1,2,3)$について、$\sum(r_i-l_i)$が最小になれば良いのです。
$\sum(r_i-l_i)$が最小になるようにするにはどのような順序でグループを結合すれば良いかというと、結論としてはグループ間の距離が近いものから貪欲に結合していけば良いです。
その理由ですが、グループの結合によって$\sum(r_i-l_i)$がどのように変化するかを追うと明らかです。
5 | 8 | 10 | 14 | 15 | 15 | 20 Σ(r-l)=0
↓
5 | 8 | 10 | 14 | 15 15 | 20 Σ(r-l)=0
↓
5 | 8 | 10 | 14 15 15 | 20 Σ(r-l)=1
↓
5 | 8 10 | 14 15 15 | 20 Σ(r-l)=3
↓
5 8 10 | 14 15 15 | 20 Σ(r-l)=6
Σ(r-l)は、グループ結合時のグループ間距離分だけしか増加しない
したがって、グループ間距離の総和が最小となるような結合順序でグループ結合していけばよい
以上で、最小値を得るグループ化の手順と、最小値の求め方がわかりました。
実装としては以下の手順で行うとよいでしょう。
- 重複を削除した家の座標配列$X$を昇順ソートする
- 隣接する家同士の距離を計算し、配列$\text{edge}$に家のインデックスとともに格納する
- 配列$\text{edge}$を距離で昇順ソートする
- 距離の小さい順に
UnionFindで家を連結していく
4.で連結した辺の距離の総和が答えです。
ただし注意点があり、2.において重複削除後の家の個数が$M$以下の時、それぞれの家に基地局を置けば電波強度$0$を実現できることが確定するため0を出力して終了しましょう。
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const [N, M] = input[0].split(" ").map(Number);
const X = input[1].split(" ").map(Number);
const sortedX = Array.from(new Set(X)).sort((a, b) => a - b);
const newN = sortedX.length;
if (newN <= M) return console.log(0);
const uf = new UnionFind(newN);
const edge = [];
for (let i = 1; i < newN; i++) edge.push([sortedX[i] - sortedX[i - 1], i]);
edge.sort((a, b) => a[0] - b[0]);
let ans = 0;
for (let i = 0; i < newN - M; i++) {
const [d, idx] = edge[i];
uf.union(idx - 1, idx);
ans += d;
}
console.log(ans);
}
// UnionFindクラスは割愛する
まとめ
今回も水色パフォを得られたのはよい兆候だと思います。
しかし、online judge toolsが直らない限り、JavaScriptでrated参加する気にはあまりなれません。
レートではなく実力を上げることを目的として引き続き取り組んでいきたいと思います。