みろくの精進日記

競プロに関することを主につづります

AtCoder Beginner Contest 326参加記

前置き

2023/10/28に開催されたパナソニックグループ プログラミングコンテスト2023（AtCoder Beginner Contest 326）に参加しました。

atcoder.jp

今回はD問題、E問題ともに450点問題ということで、425点問題を先日のABC324で初めてコンテスト中ACしたばかりの私は、C問題をそれなりに早く解き緑パフォをとることを目標として、あわよくばDまたはE問題を解くことを目標としていました。

コンテスト結果

今回の結果は、約22分での3完で、パフォーマンスは848でした。 正確な値は記憶にありませんが、C問題を提出した時点で緑パフォギリギリで、4完しないと800に届かないのではないかと思いましたが、無事緑パフォをとることが出来ました。

各問題の解法、感想

A - 2UP3DOWN

atcoder.jp

まずxとyのどちらが大きいか判定し、 x \gt yなら x - y \le 3のとき、x \lt yならy - x \le 2のときに階段を利用する、
という方針でACをとりましたが、 x \gt yかx \lt yかを判定せずともy - xをすれば符号で判定できるので、-3 \le y - x \le 2を判定すればよかったですね...

B - 326-like Numbers

atcoder.jp

まず、その数が326-like numberかの判定部分は、各桁の抽出さえできれば、326-like numberである判定は、問題通り百の位の数と十の位の数の席が一の位の数と等しいかを判定すればよいと考えました。
制約から、入力が3桁なので、各桁の抽出はそれぞれ、
(百の位の数) = N / 100
(十の位の数) = N % 100 / 10
(一の位の数) = N % 10
で求められます。
あとは、Nが326-like numberであればNを出力、違えば1を足した数が326-like numberであるかを判定していくことでACを取れました。
　　

C - Peak

atcoder.jp

まず、区間について考えました。プレゼントが置かれている座標は0以上の整数なので、xを整数にしてもxを実数にしても、x以上の最小の整数から、x+M未満の最大の整数までのM個の整数にあるプレゼントを獲得することが出来ます。
続いて区間の左端(x の値)についてですが、任意のA_{i}のみとしてよいと考えました。これはxがA_{i-1}より大きくA_{i}未満にある場合ならxをA_{i}まで進めても獲得できなくなるプレゼントはないと考えられるからです。
このように区間の左端を決定するとA_{i}からA_{i}+M-1までの数字にあるプレゼントを獲得できることになります。
区間の位置の候補を決められたので、あとはその区間にいくつのプレゼントがあるかを調べますが、二重ループを用いてA_{i}からA_{i}+Mまで調べるとTLEすると考えられます。
座標0からA_{i}までのプレゼントの数をあらかじめ求めておく、累積和の解法も少し考えましたが、同じ座標にプレゼントがあったときにバグの原因になりそうだなと考えたため、二分探索を考えました。
前もってAをソートしておくことで二分探索を用いることが出来るので、 各A_{i}について、A_{i}+M以上の最小の座標にあるプレゼントを二分探索で求めます。これがj番目のプレゼントとすると、獲得できるプレゼントはj - i個となります。これをすべてのA_{i}に対して求め、最大値が答えとなります。
この解法の計算量はO(NlogN)なので、これでACをとることが出来ました。

提出したコード atcoder.jp

D - ABC Puzzle

atcoder.jp

この問題をC問題ACした後コンテスト中考えていましたが、通せませんでした...

まずNが5以下なので適切な全探索をすればよいのではないかと考え、DFSを用いた全探索をしました。各行と列において既に現れた文字をbit列で管理し、ABCを書くことが出来るなら「.」と書ける文字を書くパターンを試すというのを再帰的に繰り返していき、最後の文字までたどり着いたらR,Cの条件を満たすかどうかを確認するという方法をとりましたが、実行結果は4419msで、TLEでした。各行や各列で最後の文字で書くべき文字が二つ以上ある場合やR,Cを探索中に調べることで通るのではないかと考えましたが時間内に実装できませんでした。

TLEしてしまった提出 atcoder.jp

E - Revenge of "The Salary of AtCoder Inc."

Dを解く前に少しだけ見ましたが、期待値mod 998244353という表記を見たことがなく、定義を見てもすぐ理解できなかったため、諦めてD問を解きました。

F,G

問題を見ていません...

まとめ

それなりのスピードでC問題を解くことができ、緑パフォも出せて満足のコンテストでしたがD問題の枝刈り全探索という問題に慣れておらず、あと少しの実行時間が縮められなかったため、くやしさが残るコンテストとなりました。E問題の期待値modも含めて、しっかり復習をして行きたいと思います。
また、今回解法をここまで書いてきたわけですが、かなり文字数の多い記事となってしまったため、次回からは解法というより感想を書いていくほうが良いのか迷っています。よろしければコメントまたはtwitterの方にてご意見くださるとありがたいです！