競プロ月記 - 2023/01
競プロについての活動記録を毎月とってみようと思います。
これをやる理由は
- 競プロのモチベーションアップにする
- 記録しておいたらもしかしたら後で何かの役に立つかもしれない
- 何か記事を書く癖をつけたい
という感じです。
もしかしたら今回しかやらないかもしれません。
この記事を書きながら数回前のコンテストについてけっこう覚えてないなと思ったので、当時思っていた感想とは異なるものもあるかもしれません。
AtCoder のレート変化
1658 → 1607 (-51)
レートが上がることの多い ARC にだけ Rated 参加したが、すべてレートが下がってしまった。
もう水色に落ちたくないなと思っていたけどさすがにそろそろ落ちそう。
AtCoder の各コンテストの振り返り
2023-01-07(土) AtCoder Beginner Contest 284
Unrated で参加。パフォーマンスは 1533。
E 問題までは早解きできたがその後の問題が解けず。
D - Happy New Year 2023 が面白かった。
E - Count Simple Paths は慣れない DFS を書いたけどなんとかあまり時間をかけずに解けた。
F - ABCBAC はパッと見で全く解法がわからなかったので自分の得意な ad hoc な問題だろうと思いがんばろうとしたが自分の知らない典型だったっぽい。
解説を読んで Z algorithm と rolling hash というアルゴリズムを自分が知らないことを知る。
Z algorithm は 【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く - Qiita という記事で理解し、実装した。
おそらく正しいアルゴリズムで書けているがけっこう重く、過去の Z algorithm を求められている問題も TLE となり通すことができなかった。
rolling hash についてはすごく薄くどんなものかだけ理解した。
今のところ「ずるいもの」というような印象を持っているけど便利そうなので使えるようになりたい。
あと、Z algorithm や rolling hash がわかったところで今回の F 問題を解く方法はまだわかっていないのであとで考察したい。
G - Only Once は F 問題を諦めた後見に行って少し考察したが解けるまでには至らず。
2023-01-14(土) AtCoder Regular Contest 153
Rated で参加。パフォーマンスは 1286。レート変化は -32。
A 問題は解けたがその後の問題が解けず。
B 問題と C 問題どちらを解くか迷ったがどちらかと言うと解けそうで配点も高い C 問題を選んだら時間が間に合わなかった。
B - Grid Rotations は少し考えてみたがぜんぜんわからず、一旦保留することにした。
全体解説のヒント集を見てみたら、2 つのヒントがどちらも思いもしなかったような内容で、天才的な解法だと思った。
気づけば簡単な問題なので、半年後ぐらいにこの問題を忘れた頃に解きたい。
おそらくサンプルをもっと注意深く眺めていれば法則に気づけたと思うので保留する前にもっと考えれば良かった。
でも解けそうだと思った C 問題に移ったことは戦略的に間違ってなかったと思うので B 問題をもっと考えれば良かったという反省はあまりしていなくて、むしろ C 問題は残り時間では解ききれないということに気づけなかったことに反省している。
C - ± Increasing Sequence はほぼ解けると思ったのだが、実装が時間内に間に合わなかったり、通ると思ったケースで落ちたりした。
考察はできたと思っていたが何か足りなかったのかもしれない。
できたら解き直したいが、実装がしんどかったのであまり解き直したくない。
2023-01-15(日) AtCoder Beginner Contest 285
いつか書けたら書く。
2023-01-21(土) ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)
いつか書けたら書く。
2023-01-22(日) AtCoder Regular Contest 154
いつか書けたら書く。
2023-01-28(土) ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)
いつか書けたら書く。
2023-01-29(日) AtCoder Regular Contest 155
いつか書けたら書く。
