【JavaScript】ABC398まとめ（A~D,F）

AtCoder Beginner Contest 398

ABCDFの5完（96分3ペナ）でした。
1139perfでレートは1048->1058（+10）となりました。
中2回空けてしまいましたが、コンテスト前にABC397のバチャをやって指をあっためておいたのがよかったかなと思います。
今回はABCDFをまとめます。

A - Doors in the Center

$N$に具体的な数値を入れて考えてみましょう。
例えば、$N=5$のとき、求める文字列は--=--です。また、$N=6$のとき、求める文字列は--==—-です。
ここで法則性が見えてきました。まず、左側と右側にある-の個数はそれぞれどちらも$\left\lfloor \frac{N-1}{2} \right\rfloor$で表すことができます。また、=の個数は$N$が偶数の時2個、奇数の時1個となります。
以上の観察結果をプログラムに落とし込むことでこの問題を解くことができます。
なお、for文で文字列をビルドしていってもよいのですが、JavaScriptではrepeatメソッドを利用すると簡潔に書けます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  let rep = Math.floor((N - 1) / 2);
  const ans = "-".repeat(rep) + "=".repeat(N % 2 === 0 ? 2 : 1) + "-".repeat(rep);
  console.log(ans);
}

Main(require("fs").readFileSync(0, "utf8"));

B - Full House 3

フルハウスになるためには、$A_1$〜$A_7$がどういう状態になれば良いかを考えましょう。
フルハウスというのは、値が$x$のカードが3枚、値が$y≠x$となる$y$のカードが2枚ある状態のことを指します。

したがって、「どの値が何回登場しているか」に加えて、「ある値が3回登場し、別の値が2回登場する」ことをmapで値を確かめながら進めても良いのですが、これを「3回以上登場する値が1つ以上、2回以上登場する値が2つ以上ある」と言い換えると、各値の出現回数を気にするだけでフルハウス判定ができるようになります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const A = input[0].split(" ").map(Number);
  // freq[i]:= 数字iの出現回数
  const freq = Array(14).fill(0);
  for (const a of A) freq[a]++;

  // f1:= 2回以上出現する数字の種類数
  // f2:= 3回以上出現する数字の種類数
  let [f1, f2] = [0, 0];
  for (let i = 0; i < 14; i++) {
    if (freq[i] >= 2) f1++;
    if (freq[i] >= 3) f2++;
  }
  if (f1 > 1 && f2 > 0) console.log("Yes");
  else console.log("No");
}

Main(require("fs").readFileSync(0, "utf8"));

C - Uniqueness

考えやすくするために、$A$を降順ソートした配列$sortedA$を作成しておきます。
また、後続の処理でバグらせないために一工夫入れて、始端と終端に番兵としてInfinityを入れておきます。

$A$の中での唯一の最大値は、$sortedA$を左端（無限大はスキップ）からみていき$sortedA_{i-1} \neq sortedA_i$ かつ $sortedA_i \neq sortedA_{i+1}$ を満たす初めての値$x$を取得することで簡単に求められます。

イメージ例）

sortedA = [Infinity, 6, 6, 5, 5, 4, 3, 1, 1, Infinity]

番兵の効果で、Infinityを除くsortedAの全ての値について
sortedA_{i-1}≠sortedA_{i}、sortedA_{i}≠sortedA_{i+1}、が確認できるようになっている。

この値$x$がわかれば、配列$A$の中で$x$は一意なので、全探索で$A_i=x$となるような$i$を求めることができます。

以上で、ソートがボトルネックとなり$O(NlogN)$なので十分高速にこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  const sortedA = A.slice().sort((a, b) => b - a);
  // 両端に番兵を追加
  sortedA.unshift(Infinity);
  sortedA.push(Infinity);

  // unique:= 一意の値
  let unique = -1;
  for (let i = 1; i < sortedA.length - 1; i++) {
    if (sortedA[i] !== sortedA[i + 1] && sortedA[i] !== sortedA[i - 1]) {
      unique = sortedA[i];
      break;
    }
  }

  let ans = -1;
  for (let i = 0; i < N; i++) {
    if (A[i] == unique) ans = i + 1;
  }
  console.log(ans === -1 ? -1 : ans);
}

Main(require("fs").readFileSync(0, "utf8"));

D - Bonfire

時間が1秒進むごとに、全ての煙の座標が変化します。したがって、愚直に全ての煙の座標を管理してしまうと$O(N^2)$となりTLEの可能性が高いです。

そこで、時間が変化しても常に変わらない不変量に着目しましょう。
この問題では、以前に生成した煙の形（相対座標）がそれにあたります。

S = NEES
以下、「B」上に焚き火と煙、「*」上に煙があり、「.」上に何もないことを表す。

.....
.....
..B..
.....
.....

↓ 風向きがNのため、下方向に煙が生成される

.....
.....
..*..
..B..
.....

↓ 風向きがEのため、左方向に煙が生成される

.....
.....
..*..
.B*..
.....

↓ 風向きがEのため、左方向に煙が生成される

.....
.....
..*..
B**..
.....

↓ 風向きがSのため、上方向に煙が生成される

.....
.....
B.*..
***..
.....

このように、焚き火の位置は動いているように見えますが、以前に生成した煙の形（相対座標）は変化していません。
したがって、この相対座標をsetで管理して、焚き火および高橋くんの位置を適切にずらすことによってこの問題を高速に解くことができそうだという予想が立ちます。

実装上の注意点としては次の通りです。

• 風向きとは逆方向に煙を追加する。　ここで、追加先の相対座標にすでに煙がある場合はスキップする。
• JavaScriptのsetはタプルやオブジェクトでの一致判定ができない（見かけ上は同じでも、異なる参照を持つため）。したがって、文字列にキャストしてからsetに渡す必要がある。

以上で、全体としては$O(N)$となり、十分高速にこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, R, C] = input[0].split(" ").map(Number);
  const S = input[1];
  const map = new Map([["N", 0], ["W", 1], ["S", 2], ["E", 3]]);
  const dr = [-1, 0, 1, 0];
  const dc = [0, -1, 0, 1];

  // set:= 追加された煙の相対座標
  // center:= 現在の相対座標(焚き火の位置)。ここを中心に煙を追加していく
  // ans:= 各煙が[R, C]上に存在するかどうかの配列
  const set = new Set();
  set.add(`${0} ${0}`);
  let center = [0, 0];
  const ans = new Array(N).fill(0);

  for (let i = 0; i < N; i++) {
    let dir = map.get(S[i]);
    // 風が吹いた方向の逆方向に煙を追加
    let rev_dir = (dir + 2) % 4;
    let [r, c] = center;
    let [nr, nc] = [r + dr[rev_dir], c + dc[rev_dir]];
    if (!set.has(`${nr} ${nc}`)) set.add(`${nr} ${nc}`);
    center = [nr, nc];

    // 煙が絶対座標[R, C]上に存在するかどうかを判定
    let target = [R + nr, C + nc];
    if (set.has(`${target[0]} ${target[1]}`)) ans[i] = "1";
    else ans[i] = "0";
  }
  console.log(ans.join(""));
}

Main(require("fs").readFileSync(0, "utf8"));

F - ABCBA

最短の回文は、事前にmax suffix palindrome（末尾の最長の回文）部分を求めておき、それを$suf$、残った部分を$pre$、$pre$を反転させた文字列を$revpre$と置くことで$pre+suf+revpre$のように書くことができます。

したがって、max suffix palindromeをどのように求めれば良いかですが、私は鉄則本を履修していたのでRolling Hashのアルゴリズムが第一に思い浮かびました。参考記事

※なお、私は実現可能な回文の長さには単調性があると勘違いして、最初は二分探索を実装して大幅に時間をロスしました。
例えば、AAABBBBBBのように末尾に同じ文字が連続する場合は確かに単調性があるのですが、ABCCBAのような場合は単調性がありません。

Rolling Hashであれば、事前に文字列のハッシュ配列を構築しておくことにより、任意の範囲を指定された時の回文判定が$O(1)$でできるようになるので、全体として$O(|S|)$でmax suffix palindromeを求めることができるようになります！

なお、ここで注意点として回文には以下に示すように、回文の文字数が奇数の「トマト型回文」と偶数の「キツツキ型回文」があります。
前者は「トマ＋マト＝トマト」のように左右が真ん中の文字列を共有しますが、後者は「キツ＋ツキ＝キツツキ」のように左右が真ん中の文字列を共有しません。
図に示すと以下のとおりです。

つまり、回文が奇数になる場合と偶数になる場合でオフセットが生じるのでそこだけ気をつける必要があるということです。
以上で、この問題をRolling Hashにより$O(|S|)$で十分高速にこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const rev_S = S.slice().reverse();
  const rh = new RollingHash(S.length);
  // 順方向のハッシュ配列と逆方向のハッシュ配列を生成
  const hashArray = rh.createHashArray(S.join(""));
  const rev_hashArray = rh.createHashArray(rev_S.join(""));

  let max = 0;
  for (let i = 0; i < S.length / 2 + 1; i++) {
    // max suffix palindromeを求める。奇数の時と偶数の時があるので両方確認する
    let rev_hash = rh.getHashValue(rev_hashArray, 0, i + 1);
    let odd_hash = rh.getHashValue(hashArray, S.length - 2 * i - 1, S.length - i);
    let even_hash = rh.getHashValue(hashArray, S.length - 2 * i - 2, S.length - i - 1);
    if (rev_hash === odd_hash) max = Math.max(max, 2 * (i + 1) - 1);
    if (rev_hash === even_hash) max = Math.max(max, 2 * (i + 1));
  }

  let pre = S.slice(0, S.length - max);
  let suf = S.slice(S.length - max);
  let rev_pre = pre.slice().reverse();
  console.log(pre.join("") + suf.join("") + rev_pre.join(""));
}
// RollingHashクラスは割愛

まとめ

久しぶりのrated参加でしたが、Dまで39分で解くことができ、Fも初期に作ったライブラリが非常に使いづらかったところをしっかり修正して時間内でACできたのでよかったです。
Eはインタラクティブで、以前どうしてもJavaScriptでflushがうまくできずに無限TLEを吐いたことがあるという地獄が頭をよぎったのでスルーしました。結果的に解説を見てもよくわからない問題だったのでその判断が奏功したと思います。
今回のまとめは以上です。