JavaScriptでABC426(A-D)
A - OS Versions
全パターン比較書いても9パターンしかないし、if...elseを9回書いても別にいいと思う
楽するならこっちで勝手にバージョン番号をつけてしまうのがいいかなぁ
1分29秒 AC!
B - The Odd One Out
Bは愚直……愚直……？
出現した文字の種類(Array)と各文字の出現回数(Object<string, number>)を前から走査する形で作って、各文字種について出現回数が1回なら出力する感じ
出現した文字の種類はわざわざArrayで記録しなくてもfor...inを使えばいい気はするな……
3分35秒 AC!
C - Upgrade Required
「もうアップグレードしたからこのバージョン以下のPCはないよ」を持っておけばfor文の範囲を縮めることができて、それだけやってしまえばあとは愚直
forの範囲が被らないから線形時間になるんですね……
理屈はわかってるんだけどACもらうまで超不安だった
30分51秒 AC!
D - Pop and Insert
基準となる文字を(i文字目と)1つ決めると、i文字目を含む同じ文字が連続する部分の端っこにくっつけるムーブをするのが最速に見えます
……ので、基準となる文字を先頭から末尾までループしながらそうなるときの最短手数を計算して最小更新したら代入を繰り返せばいいです
前または後ろに同じ文字が続いているパターンの除外方法は色々ありそうですが、私は「次の文字が同じ文字ならCO += 1、そうでなければCO = 0」として、同じ文字が連続する部分文字列の末尾のときだけ計算するようにしました COはcarry_overのつもり
66分44秒 AC!
E-G
- E: ガチ数学っぽそう……三分探索ってどこかで聞いたこともある気がするけど残り時間で書ける気がしないので断念
- F: なんかこれを解くのに使えるデータ構造がありそうな気配を感じるけど知らないのでパス！
- G: 見てない
Perfomance
- perf : 1073
- レート変化 : 856 → 880 (+24)
感想
おしゃーーかなり盛れた、嬉しい
なんか久々にD問題が解けたような気がします これを安定させたい
強いて言うならC問題はもうちょっと早く解けても良かったかもしれない。気づくのに時間かかったので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 |
Discussion