2023/9/23に開催された、サントリープログラミングコンテスト2023(AtCoder Beginner Contest 321)に参加しました。
先週のABC、ARCでは緑パフォまでしか出せずで連敗。レートの方も、なんとか水色を維持できましたが、微減という結果でした。
今回は、なんとか連敗を止めて行こうという感じで挑みます。
Rated参加します。先週土日は連敗という結果だったので、今回とりあえず連敗を止めに行きます。
— devgenjin77 (@devgenjin77) 2023年9月23日
サントリープログラミングコンテスト2023(AtCoder Beginner Contest 321) - AtCoder https://t.co/KpM4GnMKSv
今回の結果
4完を確保。E、Fは難し目の問題で解けずという結果になりました。
パフォーマンスは一応水色に到達。なんとか連敗を阻止する事が出来ました。
4完😃
— devgenjin77 (@devgenjin77) 2023年9月23日
devgenjin77さんのサントリープログラミングコンテスト2023(AtCoder Beginner Contest 321)での成績:1724位
パフォーマンス:1294相当
レーティング:1216→1224 (+8) :)
Highestを更新しました!#AtCoder #サントリープログラミングコンテスト2023(ABC321) https://t.co/vGxGC1YZ74
振り返り
大分時間が残った状態でE、F問題に取り組みましたが、残念ながら解き切ることはできませんでした。
A問題
を文字列として受け取り、隣接する文字の右側が辞書順で小さいことを確認するだけ。
やるだけの実装をして、問題なくACが取れましたとさ。1分39秒で1完。
提出コード
https://atcoder.jp/contests/abc321/submissions/45817255
B問題
なんか二分探索とか使って実装出来なくもない気がする問題だが、制約がそんなに大きくないので、安全策をとって行こうという方針に。
最終ラウンドで取る点数をからまで順番に試して、最終結果が初めて以上になる点数を求める。もし、そのような点数がなければ-1
を出力するという実装にしました。
これも問題なくAC。6分39秒で2完です。
提出コード
https://atcoder.jp/contests/abc321/submissions/45824099
C問題
一瞬難しそうに見えたが、よく考えると、321-like Numberは、0
から9
までをそれぞれ使うか使わないかに対応するので、総数はせいぜい程度。
だとすると、321-like Numberを全部列挙してからソートして、番目を出力すれば良い。
あとは、bit全探索を使って実装。なんとかACを取る事が出来ました。13分28秒で3完です。
提出コード
https://atcoder.jp/contests/abc321/submissions/45830386
D問題
まず、をソートして累積和を作成する。
次に、の各要素に対して、を二分探索し、価格未満で作れる定食が何通りあるかを求める。
この数をとした場合、価格未満の定食の合計は、と累積和の個目の要素を足すことで計算出来る。
また、価格の定食の合計は、で計算する事ができる。
あとは、実装して提出。の場合の考慮が足りておらず、1回REを出してしまいましたが、修正してACを取る事が出来ましたとさ。
36分56秒1ペナで4完。
提出コード
https://atcoder.jp/contests/abc321/submissions/45849598
E問題
順位表を見ると、少し手強そうな感じがする問題だが、時間があるのでなんとか解き切りたい問題。
考察したところ、ある頂点から葉の方向に対して、特定の距離に存在する頂点の数を適切に求める事ができれば、なんとか数え上げる事が出来そうである。
ということで、実装してみましたが、なんとサンプル1すら全く合わずで、どこにバグがあるかさっぱりわからずという体たらく。。
色々こねくり回してみましたが、最後までサンプルが合わずで時間切れになってしまいましたとさ。
F問題
F - #(subset sum = K) with Add and Erase
時間があるので一応目を通してみました。
ボールの削除が無い場合、普通にDPで解けそうな感じがする問題ですが、削除の場合どうすれば良いのかわからない。
結局、この問題は何もわからずで諦めです。
G問題
問題すら見ておりません。
これまでの実績
なんとか連敗を止めて、一応Highestを更新という結果になりました。
総括
今回、E問題が解けていれば大きくレートも伸びたというところでしたが、実装力が足りずでした。
ここのところ、緑と水色の狭間ぐらいの結果しか取れていませんが、このままでは、また緑落ちするのも時間の問題というもの。青パフォ以上狙える実力をつけるため、日々精進を重ねて行こうと思います。
ということで、また次回も頑張ります。