2024/1/27に開催された、AtCoder Beginner Contest 338に参加しました。
先週、久々の５完を達成し、レートの方は、再入水寸前というところまで上げることができました。
この勢いで、まずは再入水を早く達成したいところ。今回も５完了目標で臨むことにします。
Rated参加します。
— devgenjin77 (@devgenjin77) 2024年1月27日
今回も５完達成して、再入水を決められるように頑張ります✊
AtCoder Beginner Contest 338 - AtCoder https://t.co/FJXzJSNgFg
今回の結果
蓋を開けてみると、４完達成がやっとという結果でした。。
パフォーマンスは、水色にも届かずという感じで、結局今回は負け。再入水はお預けになりましたとさ。
４完緑パフォで負け😢
— devgenjin77 (@devgenjin77) 2024年1月27日
再入水はお預けになりました
devgenjin77さんのAtCoder Beginner Contest 338での成績：2105位
パフォーマンス：1136相当
レーティング：1193→1188 (-5) :(#AtCoder #ABC338 https://t.co/Igvj5QYf6t
振り返り
変な勘違いで、問題を余計に難しく考えてしまったところがあり、時間を浪費してしまった回でした。
A問題
isUpperCaseやisLowerCaseを使って、大文字小文字の判定をしていくだけの問題。
やるだけの実装をして提出。問題なくACが取れましたとさ。2分53秒で1完です。
もうちょっと簡単に実装するなら、正規表現を使ってみるとかですかね。
提出コード
https://atcoder.jp/contests/abc338/submissions/49694189
B問題
サイズ26の配列を作成して、各文字の個数をカウントする。あとは、最大値を計算するだけ。
これも、ほとんどやるだけの実装。問題なくACが取れて、5分35秒で2完です。
提出コード
https://atcoder.jp/contests/abc338/submissions/49699070
C問題
当初、の最大を
ぐらいかと誤解していたので、やたらと難しく考えてしまいましたが、よくよく確認してみると、
の最大が
程度ということで、結局、料理Aを作る個数を固定した全探索で解決できそうというオチでした。
方針だけ決まれば、あとは普通に実装してAC。25分28秒で3完です。
初手で難しく考えすぎていたところで、10分以上ロスしてしまいました。。
提出コード
https://atcoder.jp/contests/abc338/submissions/49713229
D問題
橋を壊した場合に通る橋の数と、橋
を壊さない場合に通る橋の数は、ツアー中のぞれぞれの移動について独立に考えることができそうです。
橋
を壊した場合、すべての橋が残っている状態から比較して、ツアーの旅程で通る橋の数がどれだけプラスされるか。
上記の値が計算できれば、あとは最小値を取って、すべての橋が残っている場合のツアー中に通る橋の数と足すことで答えになる。
例えば、島の数が個で、島
から島
に移動する場合、橋
から
のいずれかが破壊される場合は、破壊されない場合に比べて
つ余計に橋を通る必要が出てくる。よって、橋
から
それぞれに
を足すという要領です。
しかし、これを普通に計算するとTLEになるので、区間加算かつ最小値取得を効率的にできれば良いという感じだが、やり方がなかなか思いつかない。。
で、結局、D問題で使うのは場違いかと思ったが遅延セグ木を使って、区間加算と最小取得を行うぐらいしか思いつきませんでした。
使い慣れないライブラリなので、実装に悪戦苦闘しながらも、なんとかサンプルが通る実装を作って提出。なんとかACを取り切ることができましたとさ。87分36秒で4完です。
あとで解説を確認すると、imos法で解けた問題だったとのこと。履修済みのアルゴリズムが咄嗟に出て来なかったのは反省材料ですが、なんとか通し切ることができたのは良かったかと。
提出コード
https://atcoder.jp/contests/abc338/submissions/49735426
E問題
C、Dで大分時間を消費したので、ほぼ絶望的な状態で臨んだE問題。
一応、問題に目を通したのものの、何にも解法が浮かばずで時間切れ終了になりましたとさ。
F問題
問題文すら読んでいません。
G問題
問題文すら読んでいません。
これまでの実績
今回、再入水はお預け。が、致命的な負けでは無いので、次回取り戻せればと。
総括
今回は、問題文を難しく考えたがために、余計な時間を喰ってしまうというミスがあった回でした。
結局、まだまだ緑Diffレベルの基礎も曖昧な状態になっているということでしょう。当面は、基礎の振り返りに全力を入れていきたいと思います。
ということで、また次回も頑張ります。
