AtCoder Beginner Contest 266 参加記

2022/8/27に開催されたAtCoder Beginner Contest 266に参加しました。

前回のABCでは、青パフォが出るという上々の結果でレートを大幅に上げることに成功しました。

今回のABCでは、前回の勢いを落とさない様に、まずはレート以上のパフォーマンスを出そうという気持ちで臨むこととしました。

Rated参加します。
前回、青パフォという出来過ぎの内容でした。
今回はレートが上がるぐらいの結果が出れば良いという感じで頑張ります。

AtCoder Beginner Contest 266 - AtCoder https://t.co/qG7AsoGoKk
— devgenjin77 (@devgenjin77) 2022年8月27日

今回の結果

前回に続いて、5完を達成しました！

水パフォを叩き出すことに成功し、前回に続いてレートはHighestを更新！さらに水色コーダーに近づくことが出来ました！！

5完水パフォで上げ😂
この勢いで入水できるように頑張ります✊

devgenjin77さんのAtCoder Beginner Contest 266での成績：1388位
パフォーマンス：1319相当
レーティング：1129→1149 (+20) :)
Highestを更新しました！#AtCoder #ABC266 https://t.co/Nf3Ad56CyC
— devgenjin77 (@devgenjin77) 2022年8月27日

振り返り

C問題で大きく手こずったことが反省点です。

A問題

A - Middle Letter

文字列 $S$ の長さを $T$ とした時、0-indexedで、 $\lfloor \frac{T}{2} \rfloor$ 文字目を出せば良い。

ということで、実装して1回の提出で問題なくACが取れました。

1分47秒で1完。

提出コード

https://atcoder.jp/contests/abc266/submissions/34369403

B問題

B - Modulo Number

普通に、 $N mod 998244353$ を計算すれば良いというのであれば簡単だが、そうはいかないと思われる。

とりあえず、上記の要領で計算してみると、やはり $N$ がマイナスの時に計算が合わない。

ということで、マイナスの場合は、 $998244353$ を足してみることで帳尻を合わせる実装をすることに。

これでなんか嫌なケースがあったら困るなあという気持ちで提出しましたが、なんとか無事ACを取ることができました。

9分2秒で2完。

提出コード

https://atcoder.jp/contests/abc266/submissions/34376842

C問題

C - Convex Quadrilateral

苦手意識のある、二次元上の角度を求めるような問題。

解法を検討してみるものの、角度計算の方法をさっぱり忘れており、時間を溶かしてしまう。。

とりあえず10分ほど経ったところで、いったんこの問題からは撤退。D問題以降に着手することにしました。

ーーー

で、D、Eと解いたところで戻ってきたC問題。とりあえず、平面上の３点間の角度を計算する方法をググればなんとかなるかというところで、調査を開始。

すると、外積を計算すればよいとかなんとか説明している、いい感じの計算できるコードを見つけたので、とりあえずコピペで自分のコードに実装。

あとは、A→B→C、B→C→D、C→D→A、D→A→Bのそれぞれ４パターンで３点間の角度を計算し、判定することでなんとかACを取り切ることが出来ました。

88分58秒で5完。自身の知識不足のせいで、やたらと時間がかかったのですが、なんとか5完を確保することができました！

提出コード

https://atcoder.jp/contests/abc266/submissions/34401948

D問題

D - Snuke Panic (1D)

多分、DPすればいい的な問題。ということで、以下のDPを構築してみる。

$dp\lbrack i \rbrack \lbrack j \rbrack :=$ 時刻 $i$ の時点で、地点 $j$ にいる時に得ることができる最大の得点。
遷移は、 $dp\lbrack i \rbrack \lbrack j \rbrack = max(dp\lbrack i - 1 \rbrack \lbrack j - 1 \rbrack, dp\lbrack i - 1 \rbrack \lbrack j \rbrack, dp\lbrack i - 1\rbrack \lbrack j + 1 \rbrack)$ と計算し、その時点で、すぬけ君を捕まえることができるならば、得点をプラスする。