2023/1/7に開催されたAtCoder Beginner Contest 284に参加しました。
2023年一発目のRatedコンテストということで、幸先良いスタートを切るために、今回はなんとか勝ちで終わりたいところ。なんとかプラスの結果になれるようにという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年1月7日
2023年最初のコンテスト。まずはプラスの結果になるように頑張ります✊
AtCoder Beginner Contest 284 - AtCoder https://t.co/ZnRX6Zamq5
今回の結果
4完で終了。E、F問題に使える時間はだいぶありましたが、結局解けずという残念な結果となりました。
順位表から見て、だいぶ下げるかと思いましたが、なんとか4桁パフォには届いていた模様。とりあえず、かすり傷程度で済んだという印象です。
4完緑パフォで負け😭
— devgenjin77 (@devgenjin77) 2023年1月7日
残念な結果ですが、致し方なし。
次に向けて精進を継続していきます。
devgenjin77さんのAtCoder Beginner Contest 284での成績:2589位
パフォーマンス:1004相当
レーティング:1140→1128 (-12) :(#AtCoder #ABC284 https://t.co/7iBqW059LU
振り返り
E問題を難しく考えすぎていました、
A問題
もらった文字列を逆から出力する問題。
色々実装方法はあると思いますが、とりあえず配列に格納後、for文で逆から出力する方針で実装。問題なくACが取れましたとさ。
1分38秒で1完。
提出コード
https://atcoder.jp/contests/abc284/submissions/37793052
B問題
ちょっと前のABCでクエリ問題のテンプレートがB問題として出ていたような気がするが、今度は複数テストケース問題のテンプレートかという印象。
最近こういうのが流行っているのか、たんなるネタ切れなのかよくわかりませんが、問題としては配列の要素中に奇数が何個あるかを数える程度なので、実装はやるだけ。
こちらも、提出1回で問題なくACが取れました。
4分39秒で2完。
提出コード
https://atcoder.jp/contests/abc284/submissions/37800633
C問題
C - Count Connected Components
連結成分の個数を求めるということで、Union-Find一発で解ける問題のように見える。
C問題でこれを使うのは少しやりすぎという印象があったが、方針が見えてしまえば、さっさと実装した方がよい。
ということで、上記の解法で提出。問題なくACが取れましたとさ。
7分44秒で3完。
提出コード
https://atcoder.jp/contests/abc284/submissions/37804954
D問題
素因数分解の問題に見えるが、今回の最大値がという、ちょっと見慣れない制約だったので少し戸惑いました。
ただ、よくよく検討してみると、問題文の条件より、かのいずれかはの三乗根以下の数値になるということが導かれるので、まずの三乗根以下の範囲で割り切れる素数を見つけておき、あとはその素数で1回割れるか、2回割れるかで場合分けすれば良いということに気づきました。
あとは実装して。問題なくAC。とりあえず素数判定用に、エラトステネスの篩を使っては見たものの、とくに要らなかったのかもしれません。
29分31秒で4完。
ちなみに、コンテスト後の解説では、高速に素因数分解するアルゴリズムを使っても解けるとのこと。今後のためにライブラリ化しておこうと思います。
提出コード
https://atcoder.jp/contests/abc284/submissions/37804954
E問題
単純パスの数え上げという、あまり個人的に経験のない問題。
とりあえず、解法の糸口を見つけるべく、いろいろググってみるが、ヒントになりそうな物はなし。
ということで、あれこれ試行錯誤しながら、気がつけば30分もたってしまったので、一旦この問題は諦めることにしました。
で、コンテスト後に解説を見てみると、なんとDFSで解けば良いとのこと。答えの最大がだったのも次数に制約があったのも、これの伏線と考えるべきだったのかと、思い知る結果に。
次数に変な制約がある問題は、単純に探索していくことを検討した方がよいという知見を得ました。
F問題
一見したところ、文字列の比較を回繰り返せば答えが見つかる問題だが、一回の比較にかける時間を高速化できないとTLEになりそうな感じ。
高速化する方法などわからないため、とりあえず愚直に実装を行って通るかどうかを試してみることに。
が、、結局愚直実装すらまともに組めないまま、時間切れを迎えましたとさ。
解説をみると、SuffixArrayやらZ Algorithmやらの文字列比較用のアルゴリズムの準備が必要だった模様。
このアルゴリズムについては、ac-libraryにあるのは知っていましたが、使う機会がなかったので、これまで放置してました。今回の問題を機に、Java用に移植しておきたいと思います。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
2023年初Ratedコンテストは負けという結果になりました。
総括
E問題については、難しく考えすぎでした。どうせなら、E問題を愚直解で解こうという発想が働けばよかったというところ。今後は、順位表を見てAC数が多そうな感じだったら、愚直を考えてみるという方針で行ってみようかと思います。
F問題については、ライブラリの準備がないとダメな問題だったので、今回解けないのも仕方なし。次に向けて準備していきます。
2023年最初のコンテストは残念な結果でした。しかしながら、諦めずに努力を重ねていけば、いつか上の色に到達できると信じて、この1年頑張り通していきたいと思います。
ということで、また次回も頑張ります。