【AtCoder】ABC416 C - JavaScriptのN進数ロジックが正しいはずなのにWAになります
AtCoderの問題で、自分ではロジックが正しいと確信しているコードが、どうしてもWA（Wrong Answer）になってしまいます。
ローカルでのいくつかのテストケースは通過するのですが、提出するとWAとなります。
JavaScript特有の仕様を踏んでいるのか、あるいはロジックの根本的な見落としがあるのか分からず、皆様のお力をお借りしたく投稿します。
1. 問題のURL
ABC416 C - k-th string
https://atcoder.jp/contests/abc416/tasks/abc416_c
2. 提出してWAになったコード
（ローカルの input.txt とAtCoderの標準入力を自動で切り替えるテンプレートを使用しています）
'use strict';
const fs = require('fs');
const readline = require('readline');
const isAtCoder = process.platform === 'linux';
const inputStream = isAtCoder
? process.stdin
: fs.createReadStream('./input.txt');
const rl = readline.createInterface({
input: inputStream,
});
const input = [];
rl.on('line', (line) => {
input.push(line);
});
rl.on('close', () => {
const [n, k, x] = input[0].split(' ').map(Number);
// 入力されたSnをソート
const S = [];
for(let i=1; i<n+1; i++){
S.push(input[i]);
}
const sortedS = S.sort();
// xを0-indexedにする
let xLeft = x-1;
const nStringX = []; // N進数に変換したときの各桁の数字を格納
// xLeft を K桁のN進数に変換（上の桁から決定）し、nStringXに格納
for(let j=k-1; j>=0; j--){
const nPowJ = n**j;
const index = Math.floor(xLeft / nPowJ);
nStringX.push(index);
xLeft = xLeft % nPowJ;
}
// nStringXの各要素をsortedSのindexに対応させて結果を出力する
const resultS = [];
for(const l of nStringX){
resultS.push(sortedS[l]);
}
console.log(resultS.join(''));
});
3. 私の考えたロジック（アルゴリズム）
この問題は、N 個の文字列を「N 進数の K 桁の数字」として解釈する問題だと考えました。
- まず、入力された
N個の文字列Sを辞書順にソートします (sortedS)。
これがN進数における0からN-1までの「数字」に相当すると考えました。 - 問題文は
X番目（1-indexed）を求めていますが、プログラムでは 0-indexed で扱うため、xLeft = x - 1とします。 - この
xLeftを、「K桁のN進数」に変換します。- コードの
forループでは、n**(k-1)の位（一番上の桁）から順番に、xLeftをn**jで割った商をindex（その桁の数字）としています。 -
xLeftをn**jで割った余りを、次の桁の計算に回します。
- コードの
- これにより、
xLeftはnStringX = [d_k-1, d_k-2, ..., d_0]というN進数の各桁の数字（sortedSのインデックスに対応）に変換されます。 - 最後に、
nStringXの各要素lをインデックスとしてsortedS[l]を取り出し、join('')で連結して答えとしています。
4. 困っている点・不可解な点
ロジックは正しいと信じているのですが、どうしてもWAになってしまいます。
このロジックにはどのような欠陥があるのでしょうか？ あるいは、JavaScript特有の仕様で見落としている点があるのでしょうか？
どのような反例でこのコードがWAになるか、お心当たりのある方がいらっしゃいましたら、ご教示いただけますと幸いです。
よろしくお願いします。
0 likes
