主に、なんか面白そー、っていう理由でAtCoderを始めることにしました。あと、トレーニングっていうかリハビリっていうか、とにかくコードを考えて書くための動機がなんか欲しかったということもあります。
で、自分が何を考えて回答のコードを書くに至ったのか参照できるようにしておくと後で役立つかもと思って、ブログに思考を落としておくことにします。いわば積極的に恥を晒していくスタイル。
あと、Javaでやります。(当面の間は) Javaで競プロは正直面倒ですし、時間をいくらでもかけていいならよりエレガントにかける言語は他にもありますが、現状ではトータルで考えてJavaが圧倒的に早く書けるので仕方がない・・・。
各問題
A - B +/- A
https://atcoder.jp/contests/abc118/submissions/4279713
条件をただコードに書き下しただけ。
B - Foods Loved by Everyone
https://atcoder.jp/contests/abc118/submissions/4282069
食べ物ごとに好きと答えた人の数をカウントし、そのカウントが回答人数と一致したものを数えたら、それが答え。
C - Monsters Battle Royale
https://atcoder.jp/contests/abc118/submissions/4290804
最終的にACに至った回答は
- 一番小さい数で他の数すべてをオーバーキルにならないように攻撃する
- このときの最終結果は、他の数に対して一番小さい数で剰余を計算すると求まる
- これを生存者が一人になるまで繰り返す
というロジック。
なんでこんなロジックになっちゃったかというと、最初に思いついたロジックが
- 一番小さい数で二番目に小さい数を「一回」攻撃する
- ひたすらそれを繰り返す
というもので、それを TLE にならないように修正した(だけ)だからです。
最初の回答 : https://atcoder.jp/contests/abc118/submissions/4283717
あと、確実にループでなめられるようにするためにソートかけてるんですけど、多分ちょっと考えたらソートいらなくなりそう。 ていうかソートに頼っている時点でだめやん?
D - Match Matching
未提出
C問題のTLEがなかなか振りほどけず、考える時間がほとんどありませんでした。
ちなみに問題を見て思いついたロジックは。
- 1があるとき
- 本数が偶数のとき
- 1を並べる(完)
- 本数が奇数のとき
- 7があるとき
- 7のあと1を並べる(完)
- (7がなくて)5があるとき
- (次は4本の4だが、これは偶数だから考えなくていい)
- 5のあと1を並べる(完)
- 7があるとき
- 本数が偶数のとき
(以下省略)
のように、使用本数が少ないものから考慮していくというものでしたが、これだと必要本数の多い数だけが用意されているケースで分岐が大変なことになりそうなので、いずれにせよ色んな意味でだめでした。
感想
競プロで必要な考え方に慣れていかないと、話になりませんね。 とりあえずDPをちゃんと勉強せねば。
まずは色がつくところを目標にがんばります。