ABC155
ABC155に参加しました。
A,B,Cの三完でした。Dが全く分からず、Eに手を付けたのですが、サンプルケースの3つ目が通らず時間になってしまいました。ずっと考えていて、他の方の解説を参考にしながら今日やっと解決したので、記録しておこうと思います。
一番シンプルなやり方は、if文でAとB、BとC、CとAが等しい時に、残る一つが等しければNo、異なればYesを出力する方法かと思います。しかし、これは三回も同じコードを書く必要があって面倒です。私はvectorで受け取ってsortをかけて、一番目と二番目、二番目と三番目が等しい時に、一番目と三番目が等しいかどうかを判定することにしました。結局これでは手間は変わってないな…と思いながらコードを書きました。
for文でsetに受け取り、.size() == 2 になるかどうかを判定するのが一番きれいかなと思います。
コンテスト中にACした回答です。
Submission #10141857 - AtCoder Beginner Contest 155
vectorで受け取り、bool型のtrueフラグを用意しました。各要素に対して、偶数か、3で割り切れるか、5で割り切れるかをチェックし、偶数で、3でも5でも割り切れない要素があった場合はフラグをfalseに書き換えるようにしました。
コンテスト中にACした回答です。
Submission #10145208 - AtCoder Beginner Contest 155
この問題を見て、今回は大変そうだな…と思いました。
連想配列の形で受け取り、名前の受け取りと同時に出てきた回数をカウントしました。出力する名前を入れておく配列と、得票数の最大値を記録する変数を用意し、得票数の最大値が更新されるたびに配列を初期化して名前を記録し直すようにしました。mapをしっかり使ったのは初めてだと思うので、かなり時間がかかりましたが、それなりに奇麗にかけたような気がします。
コンテスト中にACした回答です。
Submission #10152333 - AtCoder Beginner Contest 155
全く分かりませんでした。素直にやると時間が足りないので、どうしようもないなと思って次に行きました。
解説を見て、二分探索やしゃくとり法というテクニックを知り、調べて勉強しました。テクニックについては分かったような気がするのですが、具体的なコードのイメージがつかめないままなので、これからほかの方の回答を参考にもう少し勉強してみようと思います。
解けそうで解けませんでした。6以上の場合はお釣りをもらったほうがよく、一つ上の位の紙幣を一枚多く払うようにします。5以下の場合はそのまま払ったほうがいいと考えました。このようにして考えた場合、例えば98のような数字の時は一の位が8なので、十のくらいに1足すのですが、こうすると十の位が10になってしまうので、この場合はお釣り無しでさらに一つ上の位に1を足すようにしました。
この考え方で書いたコードが以下のものです。
Submission #10162052 - AtCoder Beginner Contest 155
しかし、これではサンプルの三つ目が通りませんでした。理由が分からず二日間かなり悩んだのですが、これは555のようなケースを考えていないということに気が付きました。上記の方法であれば、15枚の紙幣が必要になります。しかし、1000で支払い、お釣りをもらうことにすると、1+4+4+5=14枚の紙幣で事足ります。655でも同様です。上記では15枚になりますが、1000で支払うと、1+3+4+5=13枚になります。つまり、ひとつ下の位が5以上であれば5の時も繰り上げて計算する必要があるということです。また、155の場合、1+5+5=11と、2+4+5=11になります。5,6が場合分けの分岐点になっているので、もう少し注意深く考察出来ていれば解けていたのではないかと思うととても悔しいです。また、こういう考え方は貪欲法と呼ばれているようです。
いくつかの解説を見た限り、この問題はDPで解こうとするのが一般的なようでした。前回もいわゆる桁DPの問題が出ており、復習はしたつもりだったのですが、自分でできそうだと思った解き方にこだわってしまったのは反省点です。
DPで解く場合は、上からのほうが簡単そうだったので、上から解くことにしました。次の桁でお釣りを使う場合があるので、ちょうど払うときと、1多く払う時を考えます。
復習で、DPを用いて解いた回答です。
Submission #10171570 - AtCoder Beginner Contest 155
Fは解答を見ても全く分かりません。
今回は以上です。Eが解ければなあという気持ちが二日たっても消えません。悔しさをばねにしたいと思います。
