ABC198 感想

AtCoder Beginner Contest 198に参加しましたのでその感想を書いていきます。

問題はこちらから。

Tasks - AtCoder Beginner Contest 198

結果はこんな感じでした。

3完（48:54 + 1wa）
順位：3155 / 8172
パフォーマンス：808

先週はコンテストがお休みだったため、１週間開けてのコンテストでした。１週間なかっただけですごく久しぶりな感じがしました。今回は「なんでEが間に合わないかな」この一言に尽きます。解けたと思ったのにな。残念です。

感想いきます。

A問題

お菓子を分ける問題です。

まず、AとBに一つずつ渡しましょう。これで、N' = N - 2 です。このときの n 個を分配する通り数が答えになります。

ですので、(0,N')(1,N'-1), ... , (N',0)のN'+1通りです。

これって結局、N-2ですね。これでACです。

B問題

回文の問題です。私は回文にあんまり良いイメージがないのです。それがB問題にきてしまったもんだから、さあ大変です。

でも、頭のどこかにB問題だから、簡単でしょうという考えがありました。

制約をみると n ≤ 10^9 で安心しました。0がつく可能性のがあるのは高々9個ですね。ということで、全部試しました。このとき、先頭に0をつける必要があったので、はじめに n を反転させておきました。回文ですので、反転をさせても変わりませんね。無事解けました。

C問題

R だけ移動できる人が(X,Y)まで移動するためには何回の移動が必要ですか？

という問題です。これは難しかったです。なんといっても、距離は小数が出現しますので、そこの対処に困りました。

まあだいたい、

√(X^2+Y^2) / R

でしょ。という見立ての元、式を詰めていきました。ルートがあると大変なので、まずは2乗をして、移動回数の2乗を考えることで、答えを求めました。このとき、1回移動の時には要注意です。通り越してしまうかもしれません。

これでACなのですが、２乗の移動回数を1乗に戻すときにミスがあって1WA。痛いミスです。

D問題

順位表を見てEの方が解かれていたのでとばしました。

E問題

グラフの問題です。

これをパッとみてすぐに解法が浮かびました。setを持ったBFSで解けそうです。

計算量も

O((M+N) log N)

でしたので、行けるという確信のもと、ぱぱっと実装して提出。２TLEでした。解けるという確信のもと提出したので、これはもうびっくりしました。setを何回か受け渡しているのがネックなのかなと思い、setのvectorなども用意しましたが、結局解けず。

悔しいですね。計算量が違うのでしょう。

F問題

見てないです。正解者数を見るにとっても難しそう。

あとがき

久しぶりのABCでした。結果はあんまり良くなかったですが、なによりも楽しかったので今回は良しとしましょう。早く解かなきゃと焦る感じ、提出の際に本当に出していいのか葛藤する感じ、少しひりつくようなこの感覚が大好きです。

最近3完が続いています。悔しくないかと言われれば、ものすごく悔しいと答えますし、成績が伸び悩んでいますので、数字だけを見ていると結構楽しくないです。

そんな中でも、毎日少しずつ問題を解いています。まあ、そのうち「ぽんっ」と良い成績が取れるでしょ。と思いつつ、コツコツと精進を続けたいと思います。

また、解答記事も頑張って書きたいと思ってます。予定ではコンテスト中に全完して早速執筆しようと計画してましたが、そんなに上手くはいきませんでした。

私ごとですが今年度から新社会人になってしまいました。そのため、時間はかかるかと思いますが、少しずつ書いていきますので、楽しみにしていただけると嬉しいです。まずはFまで解かなくちゃ！