ABC209の感想
AtCoder Beginner Contest 209に参加しましたので感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABCD（49:41+1WA）
順位： 2348 / 8758
パフォーマンス：1016
今回もレートが少し下がってしまいました。最近、ずっと下がってるな、と思って、確認してみましたら6連続で下がっているみたいです。そろそろ上がってほしいなとは思いますが、今回もなかなかに楽しめたのでまあよしとします。でもやっぱりレートは上がったほうが嬉しいので、次回はよろしくお願いします。
感想いきます。
A問題
A以上、B以下の数の個数を出力します。まず、B-A+1というのはすぐにわかりました。いちおう植木算になるのでその点には注意です。
このまま提出しようとしましたが、今回の私は落ち着いていました。制約チェックです。制約を見るとA,Bの関係はどこにもありません。問題文にもありません。ということで、A>Bのときを考慮しなければいけませんね。
結局
max(0,A-B+1)
を出力しました。これでAC。いい感じですね。
B問題
全ての商品を購入できるかを判定します。
これはやるだけですね。やりました。制約を見てもオーバーフローの心配はなし、コーナーケースもなさそう。
これでAC。次です。
C問題
世界一難しい問題です。30分+1WAのなかなかの痛手を負いました。
まず、先頭から考えて出現した数字をsetで管理することを考えました。setのlower_boundで使った数字の個数をカウントして各Cの値から引く。それを掛けていけば答えが求まります。
はい、嘘ですね。
1 3 3 3
というケースを考えて、誤ってることに気が付きました。
次にsetをmultisetに変更しました。これで同じ数字の出現に耐えられます。耐えられはするんですけど
5 3
で大変なことになりました。5のときに1,2,3を入れたときと4,5を入れたときで場合分けが発生します。
ここらへんで、これはdpか？とかいろいろと迷走を始めます。このように、Ci > Cj (i<j)のときに場合分けが発生して大変なことになります。困りました。
20分ぐらい色々試していましたが、ここでようやく気づきます。
Ci > Cj (i<j)でやばいなら、ソートしちゃお。ソートしても結果変わらないじゃん。
ということで、ソートしました。ソート＋multisetのlower_boudで計算しました。が合わない。upper_boundでした。
サンプルが合ったので提出。TLEでした。
30秒ほどソースを強く睨んだらわかりました。upper_boundの２分探索をN回したら間に合わなそうです。ソートしたのでC-iで十分でした。
これで何とかACです。ぼろぼろになりました。
D問題
グラフです。まず、N頂点、N-1辺、連結の３要素から木であることがわかりました。ですので、各頂点の深さを求めてあげればその差の偶奇で判断すればおしまいです。
ぱぱっと実装して、ACと行きたかったんですが、BFSをバグらせました。結局15分ぐらいかかってしまいました。うーん、この問題で時間をかけてしまったことが今回の一番の反省点です。
E問題
しりとりします。
問題を見た瞬間にグラフを作ることを決意しました。しりとりのルールに従って辺を貼れば、しりとり要素はおしまいなので、あとはグラフだけで完上げていきます。
まずは、グラフである前にゲーム問題ですので、「後ろから考える」。これにつきます。グラフの後ろってどこだろうとは思いましたが、この場合は有効グラフですのでどこにも遷移できない頂点です。ここで、典型で習った「Grundy数」の登場です。終点の頂点のGrundy数を0と設定して、辺を逆向きに貼れば後ろから考えることが可能です。
ただ、本問題は閉路を含みますので、その扱いに困りました。
閉路はループしてしまいますので、Grundy数の設定がうまくできませんでした。ループ長の偶奇、ループから抜け出す頂点の変更、ループに入る頂点、などなど色々な例をずっと試していましたが、残念ながら時間切れです。
解けませんでした。
F問題
ちょっとだけみました。それだけです。
あとがき
今回は4完でしたが、レートが下がってしまい少し悲しいです。ただ、E問題を考えているときが非常に楽しくて、それだけで大満足のコンテストでした。典型で習ったアルゴリズムをあれでもない、これでもない、と時間が許す限りずっと試していました。今まではそもそも知識がない、アルゴリズムの一覧がない、ということで、分かる問題はわかるけど、分からない問題には手が出ない、という状態になってました。でも、今回は「今日の典型」を駆使して足掻くことができました。この時間が一番好きかもしれないです。
でも、やっぱり解けた方が嬉しいのは間違いないです。いつか解けることを信じてコツコツと精進していきます。
この記事が気に入ったらサポートをしてみませんか？