【JavaScript】ABC401まとめ（A~C）

AtCoder Beginner Contest 401

ABCの3完（10分0ペナ）でした。
985perfでレートは1045->1039（-6）となりました。
Cまでの簡単な問題を爆速で解くことによって耐えていますが厳しい状況です。
明日はコンテスト前にそこそこ精進できそうなので、次回はがんばります！
今回はA〜Cをまとめます。

A - Status Code

$S$をNumber型で受け取り、$200$以上$299以下$であればSuccess、それ以外ならFailureを出力しましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = Number(input[0]);
  if (S >= 200 && S <= 299) console.log("Success");
  else console.log("Failure");
}

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

B - Unauthorized

求める値は、「認証エラーとなる回数」すなわち「ログインしていない状態で非公開ページにアクセスした回数」です。
この問題では、ログインしたかどうかのboolean変数isLoginを定義しておいて、入力に応じて以下のように処理内容を分岐させることで解くことができます。

• loginのとき：isLoginをtrueに設定
• logoutのとき：isLoginをfalseに設定
• publicのとき：なにもしない（ログイン有無によらずページを開けるため）
• privateのとき：isLoginがfalseであれば、認証エラーカウント+1する

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

  let isLogin = false;
  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (S[i] === "login") isLogin = true;
    else if (S[i] === "logout") isLogin = false;
    else if (S[i] === "private") if (!isLogin) ans++;
  }

  console.log(ans);
}

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

C - K-bonacci

これは、差分更新という典型の問題です。
$A_i$〜$A_{K+i}$までの和を$sum$とおくと、$A_{i+1}$〜$A_{K+i+1}$までの和は$sum+A_{K+i+1}-A_i$と表すことができます。そのため、$A_i$をメモ化しながら$A_{K+i+1}$を逐次求めていくことができれば、$O(N)$でこの問題を解くことができそうです。

問題は$A_N$の$10^9$で割ったあまりを求める点ですが、今回は加法と減法しか使わないため、$A_i$が負にならないよう$10^9$を足して調整しつつ、逐一$10^9$の剰余を計算することで結果に整合しつつ$A_i$を求めていくことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const A = new Array(N + 1).fill(1);
  let sum = K;
  const mod = 10 ** 9;
  for (let i = K; i <= N; i++) {
    A[i] = sum % mod;
    sum += A[i] - A[i - K] + mod;
    sum %= mod;
  }

  console.log(A[N]);
}

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

まとめ

D問題はコーナーケースに全く気づくことができず、結局7ペナ出して解くことができませんでした。
土曜夜の90分間を無為に過ごすというとても贅沢な時間の使い方をしてしまったことに反省しつつ、次回こそはレート増加目指してがんばります