競技プログラミング「AtCoder」をJavaScriptでやってみた その5

ABC187-B

問題「xy平面上にN個の点がある。点iは(xi,yi)で同じ点はない。点iと点jを通る直線の傾きが -1以上1以下である(i,j)はいくつか」

N
x1 y1
.
.
xN yN

問題文では趣旨がわからないかもしれません、全ての点と点の傾きを出して-1以上1以下である組み合わせの個数を出します。例１は

3
0 0
1 2
2 1

全ての点なので(0, 0)と(1, 2)の傾きは2、(0, 0)と(2, 1)の傾きは1/2、(1, 2)と(2, 1)の傾きは-1なので答えは2個です。全ての点に対する全ての点なので2重ループを使います。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item)=>item.split(" ").map(Number));
  let N = items[0];
  let ans = 0;
  
  for(let i = 1; i <= N; i++) {
    const xi = items[i][0];
    const yi = items[i][1];
    for(let j = i + 1; j <= N; j++) {
      const xj = items[j][0];
      const yj = items[j][1];
      const tilt = (yj - yi) / (xj - xi);
      
      if (tilt >= -1 && tilt <= 1) {
        ans++;
      }
    }
  }
  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

最初のfor文は2行目が欲しいのでitem[1]にするためlet i = 1からNまで回します。先の点をAとするなら点Aは( xi, yi)で例１なら(0, 0)です。次のループは先ほどのループの”次の行の数字”が欲しいのでlet j = i + 1と定義します。後の点をBとするなら点Bは(xj, yj)で、例１では(1, 2)になります。

傾きはyの長さをxの長さで割るので(yj – yi) / (xj – xi); これが -1以上かつ1以下である時にその点と点のペアをカウントするのでans++でインクリメントします。

ABC186-B

問題「縦Hマス、横Wマスあります。上からi行目、左からj列目のマスにはブロックがAij個あります。全てのマスを同じ個数のブロックにするには最小で何個のブロックを取り除くか？」

ブロックAij個というわかりにくい書き方をしていますが、各マスに数字が書いてあって数字を揃えるゲーム、と同じことです。問題文に“取り除く”しかないので足すことはできないようです。入力は

H W
A1,1 A1,2 … A1,W
:
:
AH,1 AH,2 … AH,W

例１では

2 3
2 2 3
3 2 2

3と書いてあるマスを１つずつ減らせば２で揃えることができそうです。揃えるのに最小は2つのブロックを減らす、なので答えは「2」です。今回は新しいJavaScript技であるconcatが登場です

"use strict";
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item) => item.split(" ").map(Number));
  let H = items[0][0];
  let W = items[0][1];
  let array = [];
  let ans = 0;

  for (let i = 1; i <= H; i++) {
    array = array.concat(items[i]);
  }

  array.sort((a, b) => a - b);
  let min = array[0];

  for (let j = 0; j < array.length; j++) {
    ans += array[j] - min;
  }
  console.log(ans);
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

空の配列array = []を用意して、for文で2行目からHまでループし、そこに「2つ以上の配列を結合する」ためarray = array.concat(items[i]);で1つの配列にします。例1ではこの時点で[2, 2, 3, 3, 2, 2]となっています。これをsortで小さい順に並び替えて[2, 2, 2, 2, 3, 3]、その先頭array[0]をminとします。

次に別のfor文を始めます。let j = 0; j < array.lengthの間 ans += array[j] – min をすると最初は2-2で0、次も2-2で0ですが……5番目は3-2 = 1、6番目も3-2 = 1になって足し上げているので答えは「2」になります。どんなに大きい数でも最小で引けば“最小にするための差”が求められるので、それをansに足していきます。

ABC185-B

問題「スマホバッテリー容量Ｎであり、時刻 0.5, 1.5, 2.5…(n+0.5)を迎える毎にバッテリー残量が1ずつ減ります。充電満タンで時刻0に外出し、途中Ｍ回カフェを訪れ、時刻Ｔに帰宅します。カフェにはAからＢまで滞在します。カフェに滞在している時は充電、n+0.5を迎える毎にバッテリーが1ずつ増加しますが、満タンの場合は増えも減りもしない。残量が０になることなく帰宅できるか？」

問題文も長くわかりにくいですが、アルゴリズムも複雑な難問です… 入力は

N M T
A1 B1
A2 B2
:
AM BM

例１のどの数字が何に該当するのか、把握して考える必要があります。

10 2 20
9 11
13 17

この間残量０になっていないので“Yes” 途中で一回でも０になったらその後カフェで充電もできませんので”No”になります。家出発時のバッテリーが満タンなのでそれをmax_batで記憶しておき、家・カフェなど出発時をnowにして、for文の中の – now がポイントでしょうか。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input.map((item)=>item.split(" ").map(Number));
  let N = items[0][0];
  let M = items[0][1];
  let T = items[0][2];
  const max_bat = N;
  let now = 0;
  let ans = "Yes";
 
  for (let i = 1; i <= M; i++) {
    let used = N - (items[i][0] - now);
    if(used <= 0) {
      ans = "No"
      break;
    }
    
    N  = used + (items[i][1] - items[i][0]);
    now = items[i][1];
    if(N > max_bat) {
      N = max_bat;
    }
  }
    
    N = N - (T - items[M][1]);
    if(N <= 0) {
      ans = "No";
    }
  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

for文はカフェによる回数Ｍまでループします。今ある残量Ｎからカフェ到着時の時間(nowは0)例1ではused = 10 – 9 – 0でカフェ１到着時は残量が１、この時点で0以下ならansは”No”にして終了breakです。

次に充電のアルゴリズムに移ります。先ほどのusedに(items[i][1] – items[i][0])つまり滞在時間を足して(1 + 11 – 9 = 3)、nowをカフェ出発時間に更新します。そしてここでもif文、Nが記憶しておいたmax_batを超えたらNはmax_batにして、for文ループの先頭に戻ります。

2周目のループに入り、カフェ1出発時の残量Nは３です。カフェ２到着時は3 –( 13 – 11 )で１になります。13-11は歩いた時間で 1周目では意味がなかったですが、- nowはここで活きてきます。まだ終わりではありません、帰宅時は別のアルゴリズムです。

最後のカフェ出発時の残量Nから歩いた時間(帰宅時間 – 最後のカフェ出発時刻)を引いた残りがNでこれもif文で0以下ならansは”No”です。所々if文で細かい判定もあり、1周目と2周目以降で – now の意味も加わってきて難しい問題だと思います。

ABC184-B

問題「N問のクイズがある。初めX点持っていて、正解すると1点増え、不正解だと1点減る。持ち点が０の場合は減らない。結果が文字列Sで与えら、左から正解ならoで不正解ならxで表されている。最終的な点数は？」

N X
S

という入力で例１は

3 0
xox

3問あって、初め0点からスタートするが、1問目xだけど持ち点0なので減らず、2問目oで1点に、３問目xで1点減って持ち点は0なので、出力するのは「0」になります。さきほどの185Bに比べれば簡単な問題です。

'use strict'
function main(input) {
  input = input.trim().split("\n");
  let items = input[0].split(" ");
  let ox = input[1].split("");
   
  let N = items[0];
  let X = items[1];
  let score = X;
  
  for (let i = 0; i < N; i++) {
    if(ox[i] === "o") {
      score++
    } else {
      score--;
      if(score <= 0) {
        score = 0;
      }
    }
  }
  console.log(score);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

特に書くことはないような気もするけど… let score = items[1]でもよかったかな？律儀に書くと一回Xに入れた方がいい気がしたので。あとはfor文はNまで回す必要はないのでi < Nにしてます。if文でox[i]が”o”ならscoreをインクリメントして、そうでなければデクリメント。elseの方には0以下になったらscore = 0にしてループの先頭に戻ってクイズ再開。

ABC183-B

問題「2次元平面上でビリヤード、x軸で球が入射角・反射角等しく跳ね返ります。(Sx, Sy)からx軸で反射させ(Gx, Gy )を通過させるにはx軸のどこを狙うか？」

問題文だけではイメージするのが難しいと思いますので、例１を見ましょう。

入力は「Sx Sy Gx Gy」であり「1 1 7 2」の場合は(1, 1)から横x軸で跳ね返り(7, 2)を狙います。答えは(3, 0)なんですが…図がないとわからないですよね。公式にはあるのでそちらを参考に。反射は1本の直線にして考えることもできるのですが、コードが浮かばず２つの三角形S, Gの相似で考えることにしました。

'use strict'
function main(input) {
  input = input.split(' ').map((a, b) => Number(a, b));
  
  let [sx, sy, gx, gy] = input;
  let ans = (gx - sx) * sy / (sy + gy) + sx; 
  
  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

gx-sxが2つの三角形を合わせた長さになっていて、それに相似比であるsy÷(sy+gy)を掛けると三角形Sのx軸に接している長さが出ますので、今のsxの位置を足せば三角形Sと三角形Gの接している位置になります。プログラミング要素の少ない数学的問題でした。 ABC182-Bは答えが複数あり、変な問題だったのでパスします…例2「8 9 18 90 72」の場合9で割り切れる数字は4つあり答えは９、他にも2や3で割り切れる数字も４つあるので２でも３でもいい