ABC208の感想
AtCoder Beginner Contest208に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABC (15:18+0WA)
順位 2286 / 8444
パフォーマンス 1018
なんか難しくなかったですか？A問題から結構悩みました。B問題もかなり悩みました。でも、ABCの序盤はこのくらいがちょうどいいなと思いました。やるだけではなくちょっと考えさせる感じといいますか。序盤から楽しめました。
ただ、D以降が解けなかったのは悔しいですね。といいますか、このD問題が1600人に解かれていることに驚きです。みなさん賢すぎます、、
ちょっと煮え切らない感じですが、感想書いていきます。
A問題
これ結構難しいんじゃないかな。さいころ（1~6）をA回振って、Bとなることがあるかを判定します。この問題を見たときにオレンジを取っていく問題を思い浮かべたのはおそらく私だけではないと思います。
あの問題を解いていなかったら解けなかったかもしれません。
解法としては、A回振ったときの下限が1*Aで上限は6*Aですので、この間にBが入っていたら実現可能です。
うーん、A問題にしては結構悩みました。
オレンジを貼っておきます。
B問題
こちらも悩みました。
以前に何かの問題で10!は十分計算可能な値に収まる、ということを知っていたので、大きいほうから順に計算していこう、という発想になりました。
やることとしては、階乗を計算して、大きいほうからpを超えない範囲で減らしていくだけなのですが、これもなかなかに考えさせられました。
ここまで、WAが出なくて結構ホッとしていました。
C問題
お菓子を配ります。まず、制約を見て、シミュレーションを回すのは間に合わなさそうだから計算するんだな、というお気持ちになりました。
まず、平等に配れるのは k /n 個で余りの k%n個を数字の小さい順に配っていきます。これは、pair<数字、index>をソートすれば簡単ですね。ソート結果の順にそのindex番号のお菓子の数を+1してあげれば答えです。
ABCのなかで一番簡単だったかもしれません。
ここまで解けて確か1400位ぐらいだったかな。やっぱり皆さん解くの速すぎです。
D問題
経路問題です。パッと見てダイクストラ＋αで解けるのかな、と考えました。この時点でもう違ってますね。
方針としては、K=1,2,3,4,..とするにつれて、K以下の頂点を結ぶ辺をグラフに追加していく、というものです。このときに、直接辺で結ばれた頂点はKの値に関わらずに移動が可能なので、その頂点組は別で処理しました。
これを、K=1において、頂点1からダイクストラ,頂点2からダイクストラ,...とやりました。そもそも、N^2回ダイクストラを回すのって間に合うんですかね。知りません。
これを実装して、サンプル１を試すと出力は20となりました。本来の答えは25なので違っています。ここで、この解法の間違いに気付きます。例えば、K=2のとき、1->2には行けますが、1->2->3には行けません。直接でないし、K=2なので、2->3の辺は追加していません。ただ、問題の条件を見るとどうやらこれもいけるようにしないといけないらしいです。
これは困りましたね。対応策として3と繋がっている（3に移動可能な）頂点までの距離を求めてその頂点から3までのコストの足してあげる、という方法を考えましたが、これを全部の頂点でやると大変なことになります。
この辺りで、残り時間は25分ぐらいだったかな、半ば諦めモードで色々と考えていましたが、結局何も浮かばず、、
E問題
見てないです
F問題
見てないです
あとがき
今回は3完という結果でした。コンテスト後に解答を見たらD問題はワーシャルフロイド法により解けるみたいですね。一応、ふんわりと原理を知ってはいるのですが、実装したことは1度もありません。解けるはずがなかったですね。
今回は「ワーシャルフロイド法」という非常に具体的な収穫がありました。しっかりと復習をしまして、使いこなせるようになっておきます。前向きに考えれば、また強くなってしまった。ということですね。
今回もとっても楽しく勉強になる問題をありがとうございました。次回も楽しく参加できればなと思います。
この記事が気に入ったらサポートをしてみませんか？