devgenjin77’s blog

デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)参加記

AtCoder 競プロ ABC 企業主催コンテスト

2022/2/19に開催された、デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)に参加しました。

本来は先週行われるはずだったこのコンテストが本日に延期になったので、今週は土日連続でABCコンテストが行われることに。

ということで、今週は土日での連勝が目標。まずは土曜のこのコンテストでレート上げを目指ざそうという気持ちで臨むことにしました。

Rated参加します。今週土日がABCなので、連勝できるように、まずは今日頑張ります。
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239） - AtCoder https://t.co/lGmfG7obKe
— devgenjin77 (@devgenjin77) 2022年2月19日

今回の結果

しかしながら、今回はあえなく4完止まりとなってしまいました。。

ABC239結果

パフォーマンスは、緑の下位ぐらいしか出ておらず、結局今回は大きな下げを喰らうことになってしまいました。。

明日頑張ります😭😭
devgenjin77さんのデンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）での成績：2594位
パフォーマンス：921相当
レーティング：1057→1044 (-13) :(#AtCoder #デンソークリエイトプログラミングコンテスト2022（ABC239） https://t.co/Xw9KCVZDRC
— devgenjin77 (@devgenjin77) 2022年2月19日

振り返り

E問題のTLEを取ることが出来ませんでした。

ABC239提出結果

A問題

問題文に書かれている通りの式を実装するだけのA問題。問題なくACを取ることが出来ました。

2分40秒という、まあまあ普通のタイムで1完。

提出コード

https://atcoder.jp/contests/abc239/submissions/29428568

B問題

B - Integer Division

$X \ge 0$ の場合は、普通に10で割った結果を出せば良さそうだが、 $X \lt 0$ の場合は調整が必要くさい問題。

よって、 $X \lt 0$ の場合、 $X = X - 9$ と調整して、10で割れば良いかと実装して出したらACが取れましたとさ。

なお、Pythonで実装する場合はこんな調整は必要ない模様。このような言語による仕様の違いについての知識を得ることができました。

5分28秒という、これもまあまあ普通のタイムで2完。

提出コード

https://atcoder.jp/contests/abc239/submissions/29433081

C問題

C - Knight Fork

問題文中にある図より、平面上の格子点からの距離が $\sqrt{5}$ であるということは、 $x$ 方向に $\pm2$ かつ $y$ 方向に $\pm1$ 移動した点、または $x$ 方向に $\pm1$ かつ $y$ 方向に $\pm2$ 移動した点である。

よって $(x_1,y_1), (x_2,y_2)$ それぞれについて、距離が $\sqrt{5}$ の格子点を全て求め、座標が一致する点があればYesとなる。

あとは、実装と提出をして、無事ACを獲得。

14分28秒での3完。ここまではまあまあ普通かなと。

提出コード

https://atcoder.jp/contests/abc239/submissions/29441593

D問題

D - Prime Sum Game

Paizaの問題でありがちなぐらい、制約が緩かったので全探索でなんとかなりそうな問題かと。

前計算として、エラトステネスの篩の要領で、200までの整数が素数か否かを判定するための配列を用意する。

あとは、先手が選ぶことができる全ての数値に対して、後手が素数を作れるのであれば後手必勝。そうでなければ、先手が必勝となる。

前計算部分で少し手間取ってしまいましたが、なんとか実装に漕ぎ着け、ACを取ることが出来ました。

32分32秒で4完。ここまで大分順調にきました。

提出コード

https://atcoder.jp/contests/abc239/submissions/29451738

E問題

E - Subtree K-th Max

グラフ問題は苦手なんだが、時間は1時間以上あるのでなんとかなるかという思いで臨んでみることに。

まずは、根付き木をDFSで探索し、各ノード配下にある数値 $X$ の集合を配列で管理する。その後、それぞれ降順ソートして、各クエリに答えれば良いかということでまずは実装。

一応サンプルは通ったが、ソートの回数が多めということに懸念が残る。まあとりあえず出してみるかという感じで提出したら、案の定TLEを食らってしまいましたとさ。。

とりあえず、WAはなかったので、性能改善すればいけるかということで色々工夫してみる。クエリの $K$ の最大値が $20$ ということで、サイズが20を超えてきた場合、配列のサイズを減らせばなんとかなるかということであれこれ頑張ってみるが、どんなに悪あがきしてもTLEは取れずでした。

結局、この問題が解けずで時間切れ。なんでこの問題が2000AC超えしてるのかよくわかりません。典型なのか？

F問題

https://atcoder.jp/contests/abc238/tasks/abc239_f

問題すら見ておりません。

G問題

G - Builder Takahashi

問題すら見ておりません。

H問題

Ex - Dice Product 2

問題すら見ておりません。

これまでの実績

まだまだ水色への道は遠いです。。

コンテスト実績

総括

今回は苦手のグラフ問題でつまづいてしまい、レート下げという結果となりました。

まだまだ水色付近のパフォーマンスが出せる実力がないということを痛感させられる結果でしたが、これにめげずに地道に精進を続けていきます。

ということで、また次回も頑張ります。