2021/12/11に開催されたパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)に参加しました。
直近のARCコンテストでは人生初の青パフォを達成し、レートは4桁の大台に乗りました。
しかし、レートが爆上がりしたことで今後はそれなりのパフォーマンスが出せないと冷えてしまうという状況にもなりました。
ということで、今回のコンテストでは何とか現状のレートぐらいの結果は欲しいという気持ちで臨むこととしました。
Rated参加します。前回のコンテストは、まぐれ勝ちでレートが大幅上昇したので、今回は現状維持以上を目標に頑張ります✊
— devgenjin77 (@devgenjin77) 2021年12月11日
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) - AtCoder https://t.co/0FpsPXndsu
今回の結果
今回、なんとか4完を確保することができたというところです。
肝心のパフォーマンスはというと、緑パフォが出たものの、4桁を切る結果となったので、今回は冷えということになってしまいました。。
4完緑パフォで冷えました。次頑張ります
— devgenjin77 (@devgenjin77) 2021年12月11日
devgenjin77さんのパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)での成績：2134位
パフォーマンス：915相当
レーティング：1005→996 (-9) :(#AtCoder #パナソニックプログラミングコンテスト2021(ABC231) https://t.co/cB1CPZ5FG3
振り返り
Dで少し手間取ってしまい、E以降は手が出ませんでした。
A問題
一読すると単純に入力をで割った結果を、小数点付きで出力するだけのように見える。
最近のA問題は難易度が上がってきているという印象があったので本当にこんな簡単で良いのかと疑心暗鬼になりましたが、あまり考えてもしょうがないので普通に実装して提出。問題なくACが取れましたとさ。
提出コード
https://atcoder.jp/contests/abc231/submissions/27816714
B問題
候補者の名前をキー、名前が出てきた回数を値としたHashMapを作り、最終的に値が最大となる候補者名を出力すれば良い。
こちらも問題なくAC。
提出コード
https://atcoder.jp/contests/abc231/submissions/27821630
C問題
まずは、入力のをソートし、各
が、
の中で何番目の大きさであるかを二分探索で求めれば良い。
ということで実装したものの、細かい条件分岐などで結構戸惑ってしまい、いろいろ試行錯誤した挙句になんとかACが取れたというところでした。
提出コード
https://atcoder.jp/contests/abc231/submissions/27835518
D問題
最初この問題を見た時、少し前に出てきたトポロジカルソートの類題かな？という考えが頭をよぎり、とりあえず類題と思われる問題のACコードをパクってきて貼ってみるということをやってみましたが、サンプルすら通らず。。
よくよくサンプルケース２をみると、同じ人が3回以上出てくる場合はどうやっても隣り合うように配置ができない。ということで、そもそもトポロジカルソート自体が相当な勘違いということに気づき、結構時間を無駄にしてしまいました。
では、次は入力を無向グラフとみなし、次数が3以上の頂点があればNoという感じで実装、提出をしてみましたが、こちらはWAという結果。よくよく考えると、グラフにサイクルが含まれるようなケースもダメなようだ。。
ということで、Union-Findを使って連結成分中にサイクルが発生するかを検知し、サイクルができればNoという条件を追加して提出。なんとかこれでACを取ることができましたとさ。
提出コード
https://atcoder.jp/contests/abc231/submissions/27844598
E問題
なんか昔、これに似たような問題をやったかなーとことで、過去問を漁ってみましたが、該当の問題が分からず。うーん、これまでやってきた過去問とかをちゃんと整理しないとなー。。
で、あまり考えててもラチがあかないのと、順位表をみると、F問題の方が解かれていそうだったので、この問題は諦めることに。
F問題
考察してみると、通りのパターンから、
番目のプレゼントをもらった場合に、それより嬉しさが大きいプレゼントが相手に渡るケースを引いていく問題のように思える。
あとは、番目のプレゼントが、何番目に嬉しさが大きいかを、
について求めて計算すれば良いかと考えましたが、気づけばもう終了時間間近。結局この問題を解くことはできませんでした。
G問題
問題すら見ておりません。
H問題
問題すら見ておりません。
これまでの実績
レートは微減。4桁の大台を割り込んでしまったのがなんとも悔しいところです。。
総括
今回の問題セットでは、4完早解きができれば現状維持ができたかというところでしたが、D問題で大きな勘違いをし、タイムロスをしてしまったのが痛かったですね。
他にも、C問題はもう少し実装が早くできたかというところなので、実装のスピードを上げていくことも今後の課題として取り組んでいこうかと思います。
ということで、また次回も頑張ります。
