B - Robot Armsが難しかった
AtCoderのコンテストに初参加した。
キーエンス プログラミング コンテスト 2020
問題
問題文
ある工場では、 数直線上にN 個のロボットが設置されています。 ロボットi は座標 Xi に設置されており、
数直線の正負の方向にそれぞれ長さLi の腕を伸ばすことができます。
これらのロボットのうちいくつか (0 個以上) を取り除き、 残ったどの 2 つのロボットについても、
腕が動く範囲が共通部分を持たないようにしたいと思います。 ただし、各 i (1≤i≤N) に対して、
ロボットi の腕が動く範囲とは 数直線上の座標が Xi−Li より大きく Xi+Li 未満の部分を指します。
取り除かずに残せるロボットの個数の最大値を求めてください。
考え方
Xi+Li
でソートし、Xi+Li
が最も左に存在するものを基準にしてXi-Li
とXi+Li
の範囲が被るか否かを判断する。
私の回答
"use strict" function Main(s) { s = s.split('\n'); let n = Number(s[0]); const robos = s.slice(1, s.length); const sort = robos.sort((a, b)=> Number(a.split(' ')[0]) < Number(b.split(' ')[0]) ? -1:1); let range = []; for(let i=0; i <robos.length; ++i){ const x = Number(sort[i].split(' ')[0]); const l = Number(sort[i].split(' ')[1]); const min = x-l; const max = x+l; if(Math.max.apply(null, range) > min) { range.push(min, max); n=n-1; } } console.log(n); } Main(require("fs").readFileSync("/dev/stdin", "utf8"));
上記の回答はX
(数直線上のロボットの位置)でソートを行っている。
そのため、不正解だった。
(その他にもrange
に基準となる初期値が入ってないとか色々問題がある)
回答(修正)
"use strict" function Main(s) { s = s.trim().split('\n'); // trim()重要 const robos = s.slice(1, s.length); const l = robos.map(robo => { let t = robo.split(' ').map(Number); return [t[0]-t[1], t[0]+t[1]]; }) l.sort((a, b) => a[1] - b[1]); let range =-1e10; let cnt = 0; for(let i=0; i <l.length; ++i){ const min = l[i][0]; const max = l[i][1]; if(range <= min) { range = max; cnt++; } } console.log(cnt); } Main(require("fs").readFileSync("./input.txt", "utf8"));
回答に関係ないがハマった点
- 入力された値を
trim()
しないと、結果がACにならない。 - 頭に
"use strict"
を記述しないと、ES6が使えない。
両方ともめっちゃハマった。
参考:
【Atcoder】JavaScriptで550問以上過去問を解いて、気付いた罠・注意点 - Qiita