ABC195の感想
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）に参加しましたのでその感想を書いていきます。
問題はこちらから。
結果はこんな感じでした。
ABC3完（4WA）
順位：3780 / 7679
パフォーマンス：620
今回も良くなかったです。なんといいますか、B問題でとっても焦りました。問題を見ていまいち理解できず、がちゃがちゃやれば解けるかな、と色々と試しました。その結果、4WAを出して解くことはできました。が、かなり時間を使ってしまいそのまま時間切れ。いままであまり見たことのないタイプの問題でした。まだまだ精進が足りません。こればかりはアルゴリズムの勉強以前にやるしかないですね。やりましょう。
では感想行きます。
A問題
モンスターにダメージが与えられるか判定する問題です。
モンスターのHPがMの倍数なら攻撃が効くそうなので、
H % M == 0
でおしまいです。HPが攻撃力の倍数の時にのみダメージが通るゲームって面白いですね。FFのレベル3フレアみたいなもんかな。
B問題
みかんが沢山あって指定された重さにピッタリと合わせる問題です。
この問題でとても苦戦しました。まず、気になったのが
みかんの重さは整数とは限りません。
という一文です。これが何のためにあるのかがいまいちわかりませんでした。
色々と考えまして。まずはピッタリと作れない場合を考えようとしました。
W*1000 / a == W*1000 / b
が判定式だ！として次に進む。
すでにピッタシ作れることは確定したので、最大値と最小値を求めます。これは入力例と照らし合わせながら切り捨て切り上げを考えました。その結果最小値であれば切り捨て、最大値であれば切り上げれば良さそうとなりまして、提出。そしてWA。困りました。
ここで一旦C問題に行きました。
CののちにBに戻ってきまして、判定式が違うことに気付きました。
ここで何故かDPで考え始めます。制約が小さいので範囲内の全部のみかんを入れればいけそう。
となりましたが、上の、みかんの重さは整数とは限らない、で諦めました。
その後、みかんの組み合わせで作れる数を考えました。
1個使えば当然a≦x≦bは作れます。2個使えば、2a≦x≦2bです。これを増やしていき、wがこの範囲に入るかどうかで判定をしました。
これでようやくAC。長かったです。
C問題
数字の3桁ごとに「,」を打つときにある数までを全部書き出したときに合計で「,」はいくつですか？という問題です。
B問題でとっても動揺してました。考える余裕はなかったです。
とりあえず数を書き出してみて
[0,999]:0個
[1000,999999]:1個
...
となることがわかりました。そうなるようにコンマを打ってるので当然と言えば当然です。
あとは入力に対応して全部場合分けを書きました。果たしてこれで良いのかと思いましたがACできたので良しとしましょう。B問題に戻ります。
D問題
重量W, 価値Vのものを箱に詰める問題です。
この問題をみて真っ先にナップザック問題のDPが思いつきました。ということでそれをベースに考えてました。構成は
dp[i][j]:i箱目j荷物目まで見たときの価値の最大値
です。でも遷移情報を上手く落とし込めませんでした。そもそもDPで解けるのか疑問ではあります。
あとがき
今回は悔しい結果でした。最近、あまり結果が良くないです。というよりは私の実力はこんなもんで、今まで過去問の類題で上振れていただけのような気がしています。恐らくそうです。
謙虚な気持ちで向き合っていきたいな。
それでも楽しくやることは忘れずに！今回みたいに上手くいかなくて悔しいコンテストでも、他の方の解答を見て、ほえー賢いなあ、ってなったり、次は負けないようにしよって意気込んだり、なんだかんだ楽しんでいます。楽しい限りは続けて、つまんなくなったらやめます。そんな感じで頑張ります。
この記事が気に入ったらサポートをしてみませんか？