ABC338の振り返り

成績はいつも通りだったものの、茶色になったので良かった。
問題を解くのが早い方ではないので、そろそろD問題を解けるようにならないとなぁという感じ。

ようするに、DPと向き合わないと…

A問題 Capitarized?

Pythonで解いた。そのままの命令ありそうだけどと思ったら解説に書いてあった。
正規表現で解いたものの、 match と fullmatch の違いを考えてなくて、WAをやってしまった。
この問題の場合、文字列全体と正規表現がマッチしていなければならなかったので、 fullmatch しなければいけなかった。 ちょっと実装上の考慮漏れ。

B問題 Frequency

Pythonで解いた。
連想配列に アルファベット → カウント をもたせた。で、valuesの中からmaxを取得して、keysをソートして（タイブレーク対策）maxの登場回数のものを探した。

すごい力技感がある。（実際メモリ使用量 76800KBなので結構でかい）

C問題 Leftover Recipes

Javaで解いた。

さすがにC問題ともなると実装が複雑になるだろうということでJavaに切り替え。仕事でこういう言語を触らなくなっちゃったので（触らないといけないはずなんだけど…）

この問題は本当に悩んだ。 当初、レシピが3個以上もありうると勝手に思い込んでいてドハマリしていた。動的計画法問題がCで出る？そんな馬鹿な！？ とか思っていた。

レシピが2つしかないのだから、ワーストケース（10万人分作れる）でも普通に計算可能なのでぐるぐる計算すればよい。わけわからなくてヤケクソで書いたロジックだがACしたので良かった。

結局のところ、Aのレシピがいくつ作れるか、1個ずつ作ってみてとりあえず保存。残った材料でBを作って保存。あとは、Aの量を一個ずつ減らしながら、Bがいくつ作れるようになるかをループして、最大値を答えればオッケー！

提出した回答では、Aを一個ずつ作っているが、普通に割り算すれば一発だった。にしても、ループをかなり回しているのに思った以上の速度で実行できていたので、やっぱりJavaって早いなぁという感じ。

感想

いろんな人の成績を見ていると、15分でC問題を解けるとパフォーマンスが1000を超える。なので、アルゴリズム力は今のままでも判断と実装が早くなると水色まで行けるということに…

とはいえ、今だとC問題の回答で時間ギリギリなのでもう少し慣れていかないと…という感じがする。