最近競プロを始めました & ABC 118(2/16)の感想

どうもーーーーー

最近は日中はpythonとjsをカタカタしながら、一方で自分のプロダクトをリリースすべく、家でカタカタして引きこもりまくっていたのですが、
最近競プロをはじめました。（引きこもり促進）

atcoder.jp

まあ今さらこんなCとかもやったことないクソ雑魚文系出のエンジニアがアルゴリズムとかなんとかをやるのもナーと思ったのですが、
少しでも強くなるために、勉強中でございます。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

これが有名な蟻本

さて、１月に始めて６回コンテストに参加し、茶色コーダーになることができました。

今年中に緑かその上の水色までは行く所存！

まあ自分の実力を上げるという意味もあるし、測るという意味もあるし、趣味という意味もある。

工学部系の学生さんも多く、さすがだなーと思います。

最近本当に自分の老けを感じる。
関わったり見たりする人の年齢層が低いというのもあるかもしれない。
そして体重が半年前52付近->60まで上がったのもあるかもしれない。
25歳にして老害の雰囲気を醸し出し始めている。

新元号は老で良いよもう。
超絶高齢化社会だしちょうどいいでしょう。

てか体重急に増え過ぎだろ。
今までクソ雑魚ガリヒョロ非力エンジニアだったのが
クソ雑魚ガリ非力エンジニアになったわ。

とりあえず、昨日のコンテストの感想でも書くか。
（競プロerがtwitterでA:-, B:-みたいなのをやってるのに憧れた）
とりあえずABCの3完でした。
Dは勉強中のdpということで、全然歯が立たず1時間を費やしました。

atcoder.jp

A: 実直に実装
B: カツサンドくんはオムライスが好きです（混乱）

result = 0
for i in KA[0][1:]:
 if all([i in j[1:] for j in KA]):
   result += 1

全員が好きと言っている食べ物をカウントしたいとのことなので、一人目が好きだと言った食べ物の中で、他の人全員が好きだと言っているものをカウントしました。

好きな食べ物が一番少ない人の食べ物についてループとかにしたほうがいいのか？
まあ、N, M<= 30だし、これも実直に実装すればできますね。

C: 最大公約数？考えてもなかった。。
まず、モンスターの体力を降順にソートしました。
最初は単純に体力最大のモンスターからその次に体力が大きいモンスターの体力を引き、
引けなくなるまで繰り返し、それを最後の要素まで繰り返そうかと思ったのですが、10000体のモンスターで、しかも体力が10億まであるとのことで、
到底時間制限におさまらないということで、引くのではなく余りを求めようと思いました。
まず、同じ体力のモンスターは2体いても変わらないということで、set()をしました。
例えば
10 10 10 3 3 2
という体力の組み合わせがあった場合、10の体力の3匹のモンスターを戦わせると最終的に1匹だけ残ります。
ですから、setで余計なモンスターを抹殺します。

そうするとモンスターは
10 3 2
というようになります。
ここから最大から最小を引いてを繰り返すと
10 3 2
7 3 2
4 3 2
1 3 2
というふうに遷移します。
これは引き算をせずとも、余りを利用すれば一度で計算できそうだと思いました。

ですので、各要素を一つ次の要素で割った余りにしていこうと考えました。
すると
1 1 2（最後の要素はそのままにした）
となり
さらにset()してsortすると
2 1
になり、同じく余りを求めると
1 1になり
set() & sort()で
1になります。
（リスト内に1が出た瞬間解答は1になるか）

リスト内のモンスターが1匹になったら、そのモンスターの体力を出力して終了としました。
あと、ループするたびに0の要素は取り除かないと、0除算のエラーが出てしまいます。
set() & sort()しているので、リストの一番最後のモンスターが0かどうかを調べ、取り除くことにしました。

python3でやりましたが、set()しないと計算が間に合いませんでした。（これで1ペナ）

まあこんなような感じで実直に解いたので、解説やtwitterで最大公約数がどうたらというのを見て得も言われぬ気持ちになりました。
正攻法ではないので、計算時間とかは悪いのでしょう。

atcoder.jp
今回の解答は、whileループを使い、毎回全要素を次の要素で割った余りを求めてかつset()しているので、いまいち計算時間がわかりません。
てか、蟻本難しすぎだろｗ（唐突）
計算時間の出し方、いつも困ります。

まあまだまだアルゴリズムに関して勉強が足りていないので、どうしても実直な解答ばかりになってしまい競プロ感が出ないのですが、
そのうちデータ構造などもしっかり勉強して、ヒープがどうの木構造がどうの云々言いながら競プロをしていきたいと思います。

atcoderなどは情報系や少なくとも理系の方が多いと思いますが、（今更文理の分別など意味もないのですが）
私のようなアルゴリズムとかをあんまりやってきていない系エンジニアなら、大体実直に解けるCまで解ければいいのではと個人的に思いました。
（実直に解けるとかいいつつ解説を無視した解答を提出しまくっているのは置いておいて）
Dとかは、DPなど解法を知らぬと解けない問題が多い感じがするためです。
ABCのCまではプログラムを書く力を、Dはアルゴリズムの力を測られていることが多いような気がします。

もっと勉強して、いつかABC全完してみたいものです。