【JavaScript】AtCoder に登録したら次にやること ～これだけ解けば十分闘える！過去問精選 10 問～を解いた感想

## はじめに
インターンのコーディング面接をJavaScriptで受けることになったので、その対策として[AtCoder に登録したら次にやること ～これだけ解けば十分闘える！過去問精選 10 問～](https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F)を解いてみました。あんまり解説を見ずに自力で解いたので、綺麗なアルゴリズムじゃないのでご了承ください！他に良い解法があったらぜひコメントお願いします！

## 【1問目】ABC086A - Product
![スクリーンショット 2023-05-21 20.34.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/b7e76c7e-9235-c3da-59a9-d56a7cea10c1.png)

```javascript
const main = input => {
  input = input.split(" ");
  a = parseInt(input[0], 10);
  b = parseInt(input[1], 10);
  
  if(a % 2 == 0 || b % 2 == 0){
    console.log("Even");
  }
  else{
    console.log("Odd");
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  
```
特に言うことないです。

## 【2問目】ABC081A - Placing Marbles 
![スクリーンショット 2023-05-21 19.50.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/8a8cbb47-c7a8-2c9b-ff9c-dcd4394c4549.png)

![スクリーンショット 2023-05-21 19.51.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/8a3888ed-7023-a3b9-d37f-0fdd8b059351.png)

```javascript
const main = (input) => {
  count = 0;
  if (input[0] == "1") count++;
  if (input[1] == "1") count++;
  if (input[2] == "1") count++;

  console.log(count);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### 入力を文字列のまま処理
入力に整数が出てくると脳死でキャストしそうになるが、この場合完全に無駄なので文字列のまま処理。for文でも書けるけど、入力が定数オーダーの場合はかえってこんな感じでもいいなと感じた。3つしかないし、いいよね。

## 【3問目】ABC081B - Shift only

![スクリーンショット 2023-05-21 19.57.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/4b495f9b-f7a9-8271-bc7a-e9fa7a6276f5.png)

![スクリーンショット 2023-05-21 19.57.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/37f6baa5-a915-6c26-2c6c-504a57b7f9c9.png)

```javascript
const main = (input) => {
  input = input.split("\n");
  numbers = input[1].split(" ");

  count = 0;

  while (numbers.every((num) => num % 2 == 0)) {
    numbers = numbers.map((num) => num / 2);
    count++;
  }

  console.log(count);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### every関数
```array.every(callback function)```と書くことで、配列の全ての要素がコールバック関数の条件を満たすときのみ```true```を返し、それ以外は```false```を返すメソッド。これを使って、配列の全ての要素が偶数の時のみ2で割る操作を繰り替えす、といった感じ。

### map関数
```array.map(callback function)```と書くことで、配列の全ての要素に対して順番にコールバック関数の処理を実行し、実行後の要素からなる新しい配列を返すメソッド。

### foreachではダメなのか
***ダメでした。*** map関数の部分を、```numbers.foreach(num => num / 2)```としたところ、実行時間制限超過エラーが出てダメでした。不思議ですね。

## 【4問目】ABC087B - Coins

![スクリーンショット 2023-05-21 20.18.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/4117ac41-a5e2-6ddc-8c52-76d10c037c2c.png)
![スクリーンショット 2023-05-21 20.18.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/7259297b-4b4a-4177-1a55-917e26b197c6.png)

```javascript
const main = (input) => {
  input = input.split("\n");
  a = parseInt(input[0]);
  b = parseInt(input[1]);
  c = parseInt(input[2]);
  x = parseInt(input[3]);

  count = 0;

  for (i = 0; i <= a; i++) {
    for (j = 0; j <= b; j++) {
      for (k = 0; k <= c; k++) {
        if (500 * i + 100 * j + 50 * k == x) {
          count++;
        }
      }
    }
  }

  console.log(count);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### 全探索
気合いの全探索。入力によって実行時間が爆発する可能性がありそうだけど、提出したら通ったのでOK。

## 【5問目】ABC083B - Some Sums

![スクリーンショット 2023-05-21 20.21.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/3cbc97cb-e0fb-4477-0bc7-c3f8cae99d66.png)
![スクリーンショット 2023-05-21 20.21.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/de2a4e62-b013-9d79-74b3-a638a94ad123.png)

```javascript
const main = (input) => {
  input = input.split(" ");
  n = parseInt(input[0]);
  a = parseInt(input[1]);
  b = parseInt(input[2]);

  total = 0;
  for (i = 1; i <= n; i++) {
    num = i.toString();

    sum = 0;
    for (digit of num) {
      sum += parseInt(digit);
    }

    if (a <= sum && sum <= b) {
      total += i;
    }
  }

  console.log(total);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

###  ```for(element of array)```構文
### 文字列型へのキャスト```toString()```

## 【6問目】ABC088B - Card Game for Two
```javascript
const main = (input) => {
  input = input.split("\n");

  n = parseInt(input[0]);
  cards = input[1].split(" ");

  sumAlice = 0;
  sumBob = 0;

  cards = cards.map((card) => parseInt(card));
  cards.sort((a, b) => b - a);

  for (i = 0; i < n; i++) {
    if (i % 2 == 0) {
      sumAlice += cards[i];
    } else {
      sumBob += cards[i];
    }
  }

  console.log(sumAlice - sumBob);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### ```array.sort()```
### 配列のインデックスによる条件分岐

## 【7問目】ABC085B - Kagami Mochi
```javascript
const main = (input) => {

  input = input.trim().split("\n");
  input.shift(); 
  numbers = input;
  
  numSet = new Set(numbers);
 
  console.log(numSet.size);
};
 
main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### 標準入力を最初に```trim()```する
### ```Set```（集合）で重複要素を排除する

## 【8問目】ABC085C - Otoshidama
```javascript
const main = (input) => {
  input = input.trim().split(" ");
  n = parseInt(input[0]);
  y = parseInt(input[1]);

  findloop: for (i = 0; i <= n; i++) {
    for (j = 0; j <= n - i; j++) {
      k = n - i - j;
      total = 10000 * i + 5000 * j + 1000 * k;
      if (total == y) {
        console.log("%d %d %d", i, j, k);
        break findloop;
      } else if (i == n) {
        console.log("-1 -1 -1");
      }
    }
  }
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### 2重ループからのbreak

## 【9問目】ABC049C - 白昼夢
![スクリーンショット 2023-05-22 12.18.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/f922d3a2-35ae-428f-4e9c-3f76e96a251f.png)

これは難しすぎて流石に解説見ました。

### 考え方
直感的に思いついたのは、**「Sの先頭から見ていって、```dream```, ```dreamer```, ```erase```, ```eraser```のどれかと一致したらその部分を削除してまた繰り返す…」** みたいなことすればいけそうじゃね…？？？

でもすぐにこんな壁にぶちあたった。

「先頭5文字を見て```dream```だったとしても、それが、```dream```なのか```dreamer```なのかわかんねえな…」

「なら、7文字目まで見れば```dream```か```dreamer```かは判定できそうやな。いや待て、それが```dreamer```なのか、```dream```+```er```（```erase```の先頭の```er```）なのか区別できないやんけ」

「ふむふむ。（解説に手を伸ばす）」

なんと、**Sを後ろから見ていく** らしい。そうすれば5or7文字見た時点で必ず指定した単語に一致するか判定できるとのこと。

今回は、後ろから見る代わりに、4つの単語と文字列Sを**反転させて前から見ていく**ことにした。

```javascript
const main = (input) => {
  s = input.trim();
  s = s.split("").reverse();

  words = ["dream", "dreamer", "erase", "eraser"];
  words = words.map((word) => word.split("").reverse().join(""));

  tmp_word = "";

  for (i = 0; i < s.length; i++) {
    tmp_word += s[i];
    if (words.includes(tmp_word)) {
      tmp_word = "";
      continue;
    } else if (tmp_word.length >= 7) {
      break;
    }
  }

  if (tmp_word == "") {
    ans = "YES";
  }else{
    ans = "NO";
  }

  console.log(ans);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### 文字列の反転
```s.split("").reverse().join("")```で文字列を反転して、後ろから読んだ状態にできた。

## 【10問目】ABC086C - Traveling
![スクリーンショット 2023-05-22 11.39.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/63ff6a5d-b9ad-c253-83a3-1a37d2c1576c.png)
![スクリーンショット 2023-05-22 11.39.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2932655/9294442e-9274-18d9-0aa1-791fafbd6c2e.png)

### 考え方
整理すると、**「単位時間あたりに1回だけ、二次元平面上の隣あった格子点に移動できるAtCoDeer君が、入力で与えられるチェックポイントを時間通りに通過できるかを判定」** する問題。


旅行プランが**実行可能かどうか**を出力すれば良いので、どのような条件の時に実行可能か実行不可能かを考えれば良い。わざわざ「原点スタートで左右上下の4通りの移動が考えられるからどれかに移動する繰り返し処理を…」みたいなことはしなくてよさそう。


入力に対して上から2地点ずつ処理していく。現在地を```current```、次の目的地を```next```とする。次の目的地に到達可能な場合は次の2つの条件が考えられる。

1. ```nextにいる時刻``` - ```currentにいる時刻``` > ```currentとnextの距離```
2. ```nextにいる時刻``` - ```currentにいる時刻``` と ```currentとnextの距離```の偶奇が一致

まず1について。単位時間で1の距離しか移動できないので、使える時間よりも距離の方が大きかったらそもそも遠すぎて到達できない、ということ。

2について。時間内に到達はできるが、目標の時刻ではないため、時間が余ってしまった場合を考える。余った時間が2の倍数なら、**「右に1移動してから左に1移動する」** という処理を目標の時刻まで繰り返せば良い。もし余った時間が2の倍数でない場合は、ピッタリに到達することは不可能となる。


```javascript
const main = (input) => {
  input = input.trim().split("\n");
  output = "Yes";

  n = input[0];

  // 現在地 (最初は原点)
  current = {
    t: 0,
    x: 0,
    y: 0,
  };

  // 入力を上から順に判定
  for (i = 1; i <= n; i++) {
    next_info = input[i].split(" ");

    // 次の目的地
    next = {
      t: parseInt(next_info[0]),
      x: parseInt(next_info[1]),
      y: parseInt(next_info[2]),
    };

    dif_t = next.t - current.t; // 現在時刻から次の目的地到達までの時間
    dist = Math.abs(next.x - current.x) + Math.abs(next.y - current.y); // 現在地から次の目的地までのマンハッタン距離

    if (dif_t < dist || (dist - dif_t) % 2 != 0) { // 条件1 or 条件2 のどちらかを満たせない場合
      output = "No";
      break;
    } else {
      current = next;
    }
  }

  console.log(output);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));
```

### マンハッタン距離
定義は[こちらの記事](https://manabitimes.jp/math/1127)がわかりやすかった。直線距離ではなく、二次元平面上の格子点上を辿った時の最短距離のことらしい。碁盤の目状の街を考えるとわかりやすい。

### ```Math.abs()```
これを使うと引数で指定した式の絶対値を返してくれる。