🫥

JavaScriptでABC414(A-C)

に公開
JavaScript
AtCoder
tech

https://atcoder.jp/contests/abc414

A - Streamer Takahashi

https://atcoder.jp/contests/abc414/tasks/abc414_a

X_i \le LかつR \le Y_iとなるiの数をカウントすればOK
やるだけといえばやるだけですけど、入力もらうのがちょっとだるくない……？

https://atcoder.jp/contests/abc414/submissions/67509347

1分49秒 AC!

B - String Too Long

https://atcoder.jp/contests/abc414/tasks/abc414_b

Bは愚直

連長圧縮（ランレングス圧縮）を復元してください。

→はい(従順)

適当な変数(let)に空文字列を入れておいて、そこにc[i]をl回繰り返したものを連結代入していきます。
「c[i]をl回繰り返したもの」はc[i].repeat(l)
100文字を超えた段階で処理を打ち切って"Too Long"を出力させて、打ち切られずに完走したら作った文字列を出力します。

https://atcoder.jp/contests/abc414/submissions/67515846

4分55秒 AC!

C - Palindromic in Both Bases

https://atcoder.jp/contests/abc414/tasks/abc414_c

競プロ力じゃないなにか(JavaScript力)を要求された……

  1. 十進法で書いたときに回文になるN以下の数を全て列挙する (以降、"候補列挙")
  2. それらがA進法で回文になるか判定して総和を求める (以降、"判定と計算")

の2段階に分かれると思います。

候補列挙は「D桁の数字で回文になるものの先頭\lceil\frac{D}{2}\rceil桁の候補は、\lceil\frac{D}{2}\rceil桁の自然数で必要十分」を使えばよさそうです。
判定と計算はやるだけだと思います。A進法にしたときの表記の文字列はNumber.prototype.toString()の引数にAを渡せばできます。

https://atcoder.jp/contests/abc414/submissions/67538540

なぜ……？？？(TLE×8) しかもサンプルでTLEが出ています。
JavaScriptなのをいいことにTampermonkeyで手元実行するスクリプトを書いているのですが、そこではサンプルは1000msくらいで終わったので大丈夫だと思ったらこれです。どうして……

終わってから解説を読んだんですけど、これ方針完璧にあってますね……
どうして〜〜！！

しょうがないので最適化を考えます。

  • 回文かどうかを判定するために「逆にした文字列」を作っていましたが、これをやめました。
    • JSで逆にした文字列を作る方法として主流なのはおそらくArray.from(str).reverse().join("")だと思います
    • これだとArray作ってindex全部逆に振り直して……ってやるのが遅そうな気がしたので変更
    • for文を使って先頭からi文字目と末尾からi文字目を比較していくことにします。 
      • const isPalindromic = (a) => {
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== a[a.length - 1 - i]) return false;
    }
    return true;
}
    • 候補列挙でもArray.from(str)→arr.reverse()→arr.join("")を使っていたので変更
      • for (let k = str.length - 2; k >= 0; k--) { ... }と、1ずつ下がっていくfor文を用意してletに連結代入していくことにしました。たぶんreverseよりはマシ。
        • 偶数桁ならもとの数の最終桁をもう一度繰り返す必要があるのでそこだけ注意

これで通ってほしいな〜〜(諦め気味)

https://atcoder.jp/contests/abc414/submissions/67545089

ですよね〜(TLE×3)

ということで最終手段を使います。

N = 10^{11} - 1, A \in \{2,3,4,5,6,7,8,9\}のときの答えを事前に計算し、N \ge 10^{11}のときにはあとからこれを足します。
これにより、1〜11桁の部分の計算をすっとばせます。N = 10^{12} - 1のときの実行時間がおよそ半分になります。

https://atcoder.jp/contests/abc414/submissions/67550576

74分47秒 AC!(2ペナ)

D-G

D,Eはなんの検討もつきませんでした

F,Gは見てないです

Perfomance

  • perf : 687
  • レート変化 : 822 → 809 (-13)

感想

Dに全く手がつかなかったのもあれですが、40分以内にCまで解けていれば810perf出たことを考えるとCがネックな気がします。
Cを一発で通せていれば……！！(1回目の提出が40分07秒だった)

次回やらかすと落茶するのでまずいです。頑張ります。

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

Discussion