ABC338の所感

今日はAtCoderのABCに参加しました。
私自身はここ1年位緑色で停滞しているソフトウェアエンジニアです。

yuforest - AtCoder

各問題の所感などを書いて行きます。
自分が見たのがE問題までなのでそこまでとなります。

AtCoder Beginner Contest 338 - AtCoder

A問題

特筆するべきことはないと思います。
最初が大文字で後の文字が小文字であればYes、それ以外ならNoです。

B問題

これはmapを知っていれば難なく解けると思います。
全て格納した上で最大のカウントを求めます。
その後で前から見ていって最初にそのカウントである文字を答えとします。

C問題

意外と手強かったです。
まず何皿作るかをAとBで全探索をすることを考えますが、それだと実行制限時間をオーバーしてしまうことがわかります。
そこで片方を固定して、もう片方をどれだけ作れるかを考えると見通しが良くなります。
Aの料理を作れる数は必要な各材料でQ[i]/A[i]を計算したときに最も少ないものです。(A[i]が0のものは除く)
それを求めて、まずAをx皿作った時の全探索を0からその数字まで行います。
それぞれで必要な材料を引いておき、残った材料でどれだけBを作れるかを計算し、その最大値を更新していきます。
これは私の実装方針ですがより良い方法があるかもしれません。

D問題

この問題は難しかったです。
かなりハマった結果解けませんでした。
解説を見るとツアーにおける移動には2種類あり、その移動の寄与分をimos法を使って足していき最小値を計算すると言うものでした。
解説を見てもまだ完全には理解できていないです。

E問題

この問題はD問題を同じくらいの水diffでしたが、D問題よりは簡単な印象です。
StackとSetをゴニョゴニョしてなんとかACしました。
問題文で見落としていた部分があり、一つの点が2つ以上の弦の始まりや終わりになることなないと言う点です。
これがなければよりシンプルに実装できたと思いました。
解説を見るとpairのvectorとstackだけで解けており、綺麗なコードだと思いました。

総合的な振り返り

最近はずっと緑のパフォーマンスでしたが、E問題がとけたおかげでなんとか水色のパフォーマンスを出すことができました。
今年は一日一問を目標に精進していきたいです。