JavaScriptでABC433 (A-D)
A - Happy Birthday! 4
なんかわり算のあまりとかできれいにやる方法はあるんでしょうけど、だるいので適当にシミュレーションしちゃいましょう
1分59秒 AC!
B - Nearest Taller
forの初期値・条件式・変化式をうまく書こうってだけですね
以下のように書くと人iのすぐ左の人から順番に左に向かって見ることができます
for (let i = 1; i <= N; i++) {
for (let j = i - 1; j >= 0; j--) {
// 省略
}
}
4分39秒 AC!
C - 1122 Substring 2
1122の悪夢、再来……！
ランレングス圧縮をして「数字が個数個」というデータの配列を作ると、その先頭要素以外について順に
「前のやつと今のやつで並んでる数字が+1になっていれば、(前のやつと今のやつの個数のうち小さい方)個をそこで作れる」
ということができ、あとはやるだけ
11分34秒 AC!
D - 183183
-
j A_i \times 10^{A_j\text{の桁数}} \equiv -A_j (\mod M) A_i - 事前にすべてのAについて、
A \times 10^{x} \mod M 1 \le x \le 9 0 M
めんどいから各値になる個数は配列で持っておけばいいかな……
……？(TLE)
とりあえずバカでかい数になってBigIntを持ち出している箇所があるのでそこをどうにかしましょうか
// 避けれるならこれは避けたいですよね
const y_onAi = Number((BigInt(Ai) * 10n ** BigInt(x)) % BigInt(M));
で、modの性質を考えると、n * 10 % M === (n % M) * 10 % Mだな〜となり、順番に計算すれば大きな数を扱わなくても同じものが作れますね！これでいけたら嬉しいなぁたぶんだめだろうけど
うん(TLE)
ここで制約を見直して気づきました、
Mapに変えて該当個数が0のところは飛ばすことにします。
配るDPっぽい書き方をすると漏れなく楽に必要なところを全部埋めれると思います。
54分47秒 AC!
E-G
- E: 「
i = 1, 2, ..., N \max_{1\le j\le M}A_{i,j}=Xi = \le - F: なにをどうやったら重複せずにカウントできるというのですか
- G: 何も思いつかん
Perfomance
- perf : 1129
- レート変化 : 868 → 897 (+29)
感想
2ペナしたものの久々に4完できて嬉しい！
レートも伸びたのでいい感じ。Highest更新も十分射程圏内。
とはいえDでサボってTLEしちゃったのはかなりもったいない。それがなければ15分くらい早く解けていた可能性があるので……。
過去の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 | 428 | 429 | 430 |
| 43x | 431 | 432 |
Discussion