AtCoder精選良問「D - Unique Username」Diff 1309
この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。
問題リンク
問題概要
文字列探索系の問題。
まず入力は以下のようなルール。
N個の文字列S1,S2,…SNが与えられる
M個の文字列T1,T2,…TMが与えられる
そして以下の条件に合致するXを出力する
N 個の文字列 S1,S2,S3...SNを好きな順番で並び変えたものを、S'1,S'2,S'3...S'Nとする。
XはS'1{一つ以上の"_"}{S'2}{一つ以上の"_"}{S'3}{一つ以上の"_"}...{S'N}というルールで作る。
Xは3文字以上16文字以内
XはT1,T2…TMに含まれない
考え方
Nの制約が8と小さくXの最大長も16と少ないので、なんとなく全探索ができそうだなーということをまず考える。
まずNの順番を好きに並び替える、という部分で計算量を見積もる。
順列並び替えの生成なので8!=40,320通り。愚直に探索したとしても、間に合いそう。
順列についてはPythonなどではitertools.permutationを使えば簡単に生成できる。
TypeScriptでは以下のような関数を用意すれば同じようなことができる。
/**
*
* @param items
* @returns 順列をyieldして返す
*/
export function* permutations<T>(items: T[], prefix: T[] = []): Generator<T[]> {
if (items.length === 0) {
yield prefix;
} else {
for (let i = 0; i < items.length; i++) {
const newPrefix = prefix.concat(items[i]);
const remainingItems = items.slice(0, i).concat(items.slice(i + 1));
yield* permutations(remainingItems, newPrefix);
};
};
};問題となるのはそれぞれの文字の間に{一つ以上の"_"}をくっつける部分。
例えば入力が以下のような場合
choku
daiそれぞれの文字数は5と3なので、16文字以内でありうる"_"の数は1～8となる。入力が２文字しかなければこれでいいが、たとえば３文字あったらどうだろう。
choku
dai
san合計の文字数は11文字なので、残りで打てる"_"の数は5文字。二か所打つ必要があるので、組み合わせを考えると、[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[3,1],[3,2],[4,1]というようになる。
文字の並び替えは比較的簡単にできそうなので、入力に応じて、打てる"_"の組み合わせを列挙することがこの問題の肝となる。
たとえば配列の長さが決まっていれば全列挙することはできる。こういう感じになるだろう。
function main() {
const numbers: number[][] = []
// たとえば長さが３で足して５以下になる組み合わせ
const limit = 5
const length = 3
for (let a = 1; a <= limit - (length - 1); a++) {
for (let b = 1; b <= limit - a - 1; b++) {
for (let c = 1; c <= limit - a - b; c++) {
numbers.push([a, b, c])
}
}
}
log(numbers)
}[
[ 1, 1, 1 ], [ 1, 1, 2 ],
[ 1, 1, 3 ], [ 1, 2, 1 ],
[ 1, 2, 2 ], [ 1, 3, 1 ],
[ 2, 1, 1 ], [ 2, 1, 2 ],
[ 2, 2, 1 ], [ 3, 1, 1 ]
]Nの制約が8と小さいのでひたすらパターンを書いてもなんとかいけそうな感じはある。しかし、こういうケースでは再帰的な関数を書くのが一般的なようだ。
const dfs = (remain: number, depth: number, length: number): number[][] => {
// 残りがなかったら何も返さない
if (remain <= 0) return []
// 最後まで達したら残りのありうる数字を返す
if (depth == length) {
const ret = []
for (let i = 1; i <= remain; i++) {
ret.push([i])
}
return ret
}
const ret = []
for (let i = 1; i <= remain; i++) {
// 再帰的に生成する
for (const j of dfs(remain - i, depth + 1, length)) {
ret.push([i, ...j])
}
}
return ret
}dfs関数では残りの数字をあらわすremainと今みている配列の長さをあらわすdepthと返す配列の長さのlengthを受け取る。
再帰には終了条件を記述する必要がある。
まず残りが０以下だったら作れる数字がないので、空の配列を返すようにする。
// 残りがなかったら何も返さない
if (remain <= 0) return []次にdepthが配列の長さに達した時は、ありうる数字を全て返す。例えば合計が5以下の配列で、最後に達した時に3残っていたとすると、[1],[2],[3]を返す必要がある。
// 最後まで達したら残りのありうる数字を返す
if (depth == length) {
const ret = []
for (let i = 1; i <= remain; i++) {
ret.push([i])
}
return ret
}あとは再帰的に数字を繰り返せばいい。
const ret = []
for (let i = 1; i <= remain; i++) {
// 再帰的に生成する
for (const j of dfs(remain - i, depth + 1, length)) {
ret.push([i, ...j])
}
}この関数を使う時は以下のように合計値、深さ1、配列の長さを指定する。
log(dfs(5,1,3))例えばdepth=1,i=1のときには、次にdfs(remain=4,depth=2,length=3)が呼び出される。
そうすると、その中で二つめのiが１から4まで繰り返される。
二つ目のiが1の時はdfs(remain=3,depth=3,length=3)が呼び出される。
そうするとdepth==lengthの終了条件がtrueになり、[1],[2],[3]が返される。
return されたので、depth=2のi=1にこの返り値が含まれてでdepth=1にreturnされる
[1,…[1]]=>[1,1]
[1,…[2]]=>[1,2]
[1,…[3]]=>[1,3]
そしてdepth=1に戻ってくる。
[1,…[1,1]]=>[1,1,1]
[1,…[1,2]]=>[1,1,2]
[1,…[1,3]]=>[1,1,3]
これを再帰的に繰り返していくことで、合計N以下の長さLの数字の組み合わせを列挙することができる。
実装
あとはこの関数を使って問題を解いていく。
コーナーケースとしてN=1の場合に注意をする。
import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
/**
*
* @param items
* @returns 順列をyieldして返す
*/
export function* permutations<T>(items: T[], prefix: T[] = []): Generator<T[]> {
if (items.length === 0) {
yield prefix;
} else {
for (let i = 0; i < items.length; i++) {
const newPrefix = prefix.concat(items[i]);
const remainingItems = items.slice(0, i).concat(items.slice(i + 1));
yield* permutations(remainingItems, newPrefix);
};
};
};
const dfs = (remain: number, depth: number, length: number): number[][] => {
// 残りがなかったら何も返さない
if (remain <= 0) return []
// 最後まで達したら残りのありうる数字を返す
if (depth == length) {
const ret = []
for (let i = 1; i <= remain; i++) {
ret.push([i])
}
return ret
}
const ret = []
for (let i = 1; i <= remain; i++) {
// 再帰的に生成する
for (const j of dfs(remain - i, depth + 1, length)) {
ret.push([i, ...j])
}
}
return ret
}
function main() {
const [n, m] = nextNums(2)
// S1,S2,...SNを記録
const arr: string[] = []
// 文字数の合計数を記録
let lengthSum = 0
for (let i = 0; i < n; i++) {
const char = next()
arr.push(char)
lengthSum += char.length
}
// 使われている文字を集合にする
const taken: Set<string> = new Set()
for (let i = 0; i < m; i++) {
taken.add(next())
}
// コーナーケース
if (n == 1) {
const leng = arr[0].length
if (!taken.has(arr[0]) && 3 <= leng && leng <= 16) {
log(arr[0])
} else {
log('-1')
}
process.exit()
}
// 残りの打てる"_"の数
const remainLength = 16 - lengthSum
// 組み合わせをdfsで全列挙。それぞれの文字の間に"_"を打つので、長さはn-1
const numbers: number[][] = dfs(remainLength, 1, n - 1)
// 順列を繰り返す
for (const chars of permutations(arr)) {
// 打てる"_"を全通り探索
for (const nums of numbers) {
// 答え候補
let tmp = ''
// 答えを生成
for (let i = 0; i < n - 1; i++) {
tmp += chars[i]
tmp += '_'.repeat(nums[i])
}
// n-1の繰り返しなので、最後の文字をくっつける
tmp += chars[n - 1]
// 使われていない
if (!taken.has(tmp)) {
// 3文字以上16文字以下なら出力して終了
if (3 <= tmp.length && tmp.length <= 16) {
log(tmp)
process.exit()
}
}
}
}
// ここまで来たら当てはまるものがない
log('-1')
}
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();
}この記事が気に入ったらサポートをしてみませんか？