【JavaScript】ABC395まとめ（A~C,E）

AtCoder Beginner Contest 395

ABCEの4完（92分3ペナ）でした。
1018perfでレートは1051->1048（-3）となりました。
B~DはひとつもすんなりACできずに大事故もありましたが、Eをギリギリで解くことができたのでひとまず死は免れました。
AtCoder Replayによると、E問題正解直前まで灰パフォだったようです（危なすぎる）。
今回はABCEをまとめます。

A - Strictly Increasing?

for文で狭義単調増加が破綻していないかどうかを確認しましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number[input[0]];
  const A = input[1].split(" ").map(Number);
  for (let i = 0; i < N - 1; i++) {
    if (A[i] >= A[i + 1]) return console.log("No");
  }
  console.log("Yes");
}

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

B - Make Target

小さい正方形で内部を何度も塗りつぶすことでも解くことができそうですが、$O(N^3)$なので、謎のこだわりのある私は$O(N^2)$で解くことを考えました。

まず、最初に#で全てのマスを塗っておきます。
その後、一つ内側の正方形領域の枠を.で塗ります。
その次に、一つ飛ばして二つ内側の正方形領域の枠を.で塗ります。

例）N=8
########
########
########
########
########
########
########
########
↓
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#......#
########
↓
########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

すっきり書けて、$N$が大きい時にはパフォーマンスの観点で良いのですが、添字の管理がややこしいのでこの問題を解くのにはおすすめしません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const ans = new Array(N).fill(0).map(() => new Array(N).fill("#"));
  // 丁寧に白塗りする箇所を指定することで、O(N^2)とした
  for (let i = 1; i < N / 2; i += 2) {
    for (let j = i; j < N - i; j++) {
      ans[i][j] = ".";
      ans[N - i - 1][j] = ".";
      ans[j][i] = ".";
      ans[j][N - i - 1] = ".";
    }
  }
  for (let i = 0; i < N; i++) console.log(ans[i].join(""));
}

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

C - Shortest Duplicate Subarray

まず、同じ値を2つ含むような連続部分列の長さの最小値は、左端、右端が同じ値である必要があります。
また、最小値の状態で同じ値は左端、右端だけであり、それ以外のペアで同じ値になることはありません。

NG例①
3 4 5 3 8 → 末尾の8を削って「3 4 5 3」とした方が明らかに短いので最小となりえない
NG例②
3 4 5 3 6 4 3 → 4 5 3 6 4や、3 4 5 3、3 6 4 3の方が明らかに短いので最小となりえない

以上を考慮した高速なアルゴリズムを考えます。
まず、$1〜10^6$までの値の出現位置を記録する配列$where$を考えます。
例えば、$A=[3,4,5,4,3,6,3]$であれば以下の通りです。

例）
where[3]=[0,4,6]
where[4]=[1,3]
where[5]=[2]
where[6]=[5]

配列$where$は配列$A$を一回走査するだけで作成できるので$O(N)$です。
この情報を元に、同じ値を左端、右端にもつ連続部分列の候補を全探索します。
先ほどの具体例$A=[3,4,5,4,3,6,3]$のケースで説明します。

$i$	$where[i]$	左端	右端	連続部分列の長さ
$3$	$[0,4,6]$	$A[0]$	$A[4]$	$5$
同上	同上	$A[4]$	$A[6]$	$3$
$4$	$[1,3]$	$A[1]$	$A[3]$	$3$

上の表を見てください。
全ての候補のうち連続部分列が最小となるものは$i=3$のときの$A[4]-A[6]$、もしくは$i=4$のときの$A[1]-A[3]$、いずれにせよ$3$となります。
このようなアルゴリズムを利用することにより、全体として$O(N)$でこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  let max = Math.max(...A) + 1;
  // where[i]:= iが出現するindexの昇順配列
  const where = new Array(max).fill(0).map(() => []);
  for (let i = 0; i < N; i++) where[A[i]].push(i);

  let ans = Infinity;
  for (let i = 0; i < max; i++) {
    if (where[i].length < 2) continue;
    // 隣接するindexの差が最小のものを探す
    for (let j = 1; j < where[i].length; j++) {
      ans = Math.min(ans, where[i][j] - where[i][j - 1] + 1);
    }
  }
  console.log(ans === Infinity ? -1 : ans);
}

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

余談ですが、この問題を誤読して「連続部分列の最大値」としてこの問題を解いてしまっていたので3ペナしてしまいました。誤読にはくれぐれもご注意ください。。。

E - Flip Edge

頂点倍加、または拡張ダイクストラという典型アルゴリズムを用います。
すなわち、「1.頂点$1$から頂点$N$までは入力で示された通りの向きで有向辺が存在」して、「2.頂点$N+1$から頂点$2N$まではそれを反転させた向きで有向辺が存在」するとみなします。これらの辺のコストは全て$1$ですが、「3.コスト$X$をかけて、頂点$i$から頂点$i+N$もしくは頂点$i+N$から頂点$i$への移動ができるような有向辺」を追加します。

具体例を示します。
下図の1.が黒辺、2.が緑辺、3.が青辺にあたります。

このように仮想的に頂点を追加して考えることで、本問題はスタート地点である頂点$1$から、元のグラフのゴール地点の頂点$N$または反転されたグラフのゴール地点の頂点$2N$までの最短経路問題に帰着します。辺の重みは$1$と$X(≦10^9)$の二種類があるため、ダイクストラ法を利用します。
そうすると全体計算量は$O((N+M)logN)$となりこの問題を十分高速に解くことができました。

なお、以下の解法では自前のDijkstraライブラリを使用していますが、このご時世AIで誰でも自作できると思いますので、まだ作っていないと言う方は自作にチャレンジしてみてください。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M, X] = input[0].split(" ").map(Number);
  const [u, v] = [[], []];
  for (let i = 0; i < M; i++) [u[i], v[i]] = input[i + 1].split(" ").map(Number);

  // 元のグラフ + 辺を反転したグラフ = 2N頂点のグラフを考える
  const dijkstra = new Dijkstra(N * 2);

  // 同じグラフ間での移動
  for (let i = 0; i < M; i++) {
    dijkstra.addEdge(u[i], v[i], 1);
    dijkstra.addEdge(v[i] + N, u[i] + N, 1);
  }

  // 反転グラフへの移動
  for (let i = 1; i <= N; i++) {
    dijkstra.addEdge(i, i + N, X);
    dijkstra.addEdge(i + N, i, X);
  }

  dijkstra.run(1);
  // 元のグラフの頂点Nだけでなく、反転グラフの頂点2Nも答えとみなす
  let ans = Math.min(dijkstra.dist[N], dijkstra.dist[N * 2]);
  console.log(ans === Number.MAX_SAFE_INTEGER ? -1 : ans);
}
// ダイクストラ法のライブラリは割愛

まとめ

D問題はラベルを入れ替えると言う方針自体はすぐに立ったのですが、適当に実装するとどうしてもサンプル3が合わず、頭が破壊されたのでEに行きました。
Eは残り8分くらいでACできたのでなんとか事なきを得ましたが、Cまでで事故っていたので本当にヒヤヒヤしました。
直近はあまりにも私生活が忙しすぎて今週のABC参加をどうするか考えているのですが、もし後日unrated参加としても記事は更新したいと思います。