🔥
JavaScriptでABC428 (A-C)
A - Grandma's Footsteps
最終回は除いて一回計算して、最後の一回に残っている秒数を出して足します
頭バグってめっちゃ時間かかった なにしてるんですか
4分33秒 AC!
B - Most Frequent Substrings
Bは愚直
全部列挙して数えます やるだけですね！！
出力2行目のソートをお忘れなく
11分07秒 AC!
C - Most Frequent Substrings
まあ「あと何個)が必要か」を更新しつつ、それが一回でも負になっちゃうならその位置を覚えといてそこを消すまでNoって言い続ければ良さそう
実装めんどくせ〜〜！！
29分23秒 AC!
D-G
- D
-
C+x - テストケース1番目なら、「44〜49、410〜484」のように
- それぞれの範囲n〜mについて「
\sqrt{n} \sqrt{m} \lfloor{\sqrt{m}}\rfloor - \lceil{\sqrt{n}}\rceil + 1 - これがそのまま「n以上m以下の平方数の数」になります
- 各テストケースごとに
D O(T\cdot\log_{10}{D}) - ……と思ったんですが、制約を考えると
BigIntでの保持が必須だと気づきました-
f(C, C+x) 2 \times 10^{18} + 5 \times 10^{9} + 2 \times 10^{8} Number.MAX_SAFE_INTEGER(9 \times 10^{15}
-
- JavaScriptの
Math.sqrt()はBigInt非対応で、自力実装もO(\log N)
-
- E
- 調べたら「全方位木DP」っていうまんまそれっぽいものが出てきました
- 私は全方位木DPどころか木DP、なんならDPも知らないのでパス
- F, G
- チラ見してなんもわかりませんでした
Perfomance
- perf : 985
- レート変化 : 858 → 871 (+13)
感想
まあ温まったので許しましょう
D解けなかったの悔しい〜〜〜
過去のABCも似たような記事を書いています。よければそちらもどうぞ。
| xx1 | xx2 | xx3 | xx4 | xx5 | xx6 | xx7 | xx8 | xx9 | xx0 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 40x | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | |
| 41x | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 |
| 42x | 421 | 422 | 423 | 424 | 425 | 426 | 427 |
Discussion