【AtCoder】ABC022 - 競技プログラミング初挑戦！

AtCoder ABC022に挑戦！

人生で初めて競技プログラミングのコンテスト(オンライン)に出場してみました！
使用言語はC++にしようかと思ったのですが、どっちかというとD言語のほうがすきだし、Dlangも十分競技プログラミングに向いているっぽかったのでD言語で出場しました。

結果

2完で121位でした
いやー惨敗でしたねｗｗ
A問題がなんか変に時間食っちゃって、焦りました。そしてB問題がするっと出来て、「おっ！」と思ったら案の定C以降にても足も出ませんでした...
C問題に関してはそもそも問題文を勘違いしていました（勘違いに気がついても結局できなかったｗｗ）

復習

解説放送も聞いてきましたー

A問題

普通にたしていった。一回全部入力受けてから計算始めてたけど無駄だったなー受け取りながら計算すればもっと早くなってたはず。
今回は簡単な問題だったのでよかったけど、こういうのでTLEになる場合もあるんだろうな

B問題

N - (花の種類)というおしゃれ解法もある様子(ただしやることは結局同じで、今まで訪れた花の種類を覚えながら舐める)

ここまでは完答

C問題

頂点1に隣接する頂点はちょうど2つなので、その2つをつなぐ最短経路を求めればいい！！
発想はなんとなくあってたなー
僕が考えていたのは、頂点1から道が伸びてる頂点Xについて、 1 - X間の道を除いたグラフを考えて、X - 1の最短経路をダイクストラで求めるやり方でした
結局実装力不足で死にましたが...(´・ω・`)

ダイクストラだとO(N²) * O(N²) = O(N⁴)になっちゃうけど、ワーシャルフロイドを使えばO(N³)ですむとのこと。たしかに。
ワーシャルフロイトは実装らくちんだもんなー
なるほどだなー悔しいなこれ。あとちょっとだった。

D問題

C問題でつまづきまくってしまい心が折れてたので全然まともに挑んでいないです...
解説きいたあとだから言いたい放題なんだけど、これ部分点までならとれた気がするｗｗ
いろいろ解法がある様子。とにかく、回転移動や平行移動に惑わされない値に注目してあげれば、相似比は簡単に求まるよねーというお話。
ぱっと思いついたのは最遠点だったけど、それだとO(NlogN)で部分点らしい。
最も初心者向けなのは重心からの最遠点までの距離っぽいです。

感想などなど

初めて競技プログラミングのコンテストに出場しましたがめちゃくちゃ楽しいですねこれ！
AtCoderさんの解説放送のおかげでわからなかった問題の理解もできたし、はまりそう.
もともとコンテスト外の問題は練習で少しだけ解いたことがあったのですが、全然別物の面白さでしたー
とりあえずダイクストラとかの基本アルゴリズムに関してはすらすら実装できるようになりたいなー

明日はyukicoderさんのコンテストがある？のかな？
出場してみたいと思います！

では模範解答を写経して寝ます！