🤩

JavaScriptでABC419(A-D)

に公開
JavaScript
AtCoder
tech

https://atcoder.jp/contests/abc419

A - AtCoder Language

https://atcoder.jp/contests/abc419/tasks/abc419_a

if文を、書きまーす！！

https://atcoder.jp/contests/abc419/submissions/68512679

1分24秒 AC!

switch文のほうが楽だったかもしれない(AC)

B - Get Min

https://atcoder.jp/contests/abc419/tasks/abc419_b

Bは愚直

適当にbagを用意して問題文の通りやればOK
取り出すことを考えるとタイプ2のクエリでは「降順ソート → console.log(Array#pop())」が楽だと思います

https://atcoder.jp/contests/abc419/submissions/68521570

5分11秒 AC!

C - King's Summit

https://atcoder.jp/contests/abc419/tasks/abc419_c

一旦2次元のことは忘れて1次元で考えましょう

1次元の場合、一番左の人と一番右の人に向かい合うような方向に動いてもらって、それ以外の人は最初に動きはじめた2人が来てから行動すれば良さそうです

 11    1 1
  2    11
   2   2
    2 2
     2

(※数はそのマスにいる人数を表します)

言い換えると、「一番左の人のすぐ左と一番右の人のすぐ右に壁を用意し、範囲を狭める方向に押していく」とも言えます

|11    1 1|
 |2    11|
  |2   2|
   |2 2|
    |2|

(※数はそのマスにいる人数を表します)

かかるステップ数は一番左の人と一番右の人の距離の半分を整数に切り上げたものですね

で2次元に戻ると、左右の壁の代わりに「全員を囲う最小の長方形の囲い」を用意し、高さと幅が1マスになるまで毎ステップごとに囲いの外周1マスを削っていけば同じ事ができそう
このときのステップ数は上下軸と左右軸でそれぞれ最も遠い2人組の距離の半分の切り上げを求めて、大きい方を採用すればいいです

https://atcoder.jp/contests/abc419/submissions/68531607

12分13秒 AC!

D - Substr Swap

https://atcoder.jp/contests/abc419/tasks/abc419_d

「操作後のSのn文字目」は、「n文字目がスワップされた回数の偶奇」で判定できます。
なので、「n文字目がスワップされた回数は何回か？」が分かれば各文字考えていくだけ。

「n文字目がスワップされた回数」は、「L_i \le n \le R_iであるiの個数」です。
……で、L_i \le n \land n \le R_iは\lnot(n < L_i \lor R_i < n)なので、「L_i \le n \le R_iであるiの個数」は
全体の個数M - (n < L_iであるiの個数 + R_i < nであるiの個数)
となります。

L_i \le R_iなのにn < L_iとR_i < nが同時に起こることはありえないので、LとRをそれぞれソートして二分探索すればOK。
うおーーたまたま昨日lower_bound()とupper_bound()準備してたんですよ、最高だな！！

https://atcoder.jp/contests/abc419/submissions/68545373

27分47秒 AC!

E-G

チラ見したけど何もわからなかったよ〜〜

Perfomance

  • perf : 1038
  • レート変化 : 816 → 840 (+24)

感想

28分4完……？！
ノーペナ4完で30分切ったのはたぶん初めてです。やったね
とはいえ問題セットがたまたまハマっただけな感じもあります どこで沼っててもおかしくない
lower_bound()とupper_bound()用意してなかったら+30分くらいかかってただろうし……
より確実な力にしていきたいですね

過去のABCも似たような記事を書いています。よければそちらもどうぞ。

Discussion