れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest (ABC) 191のメモ

結果

ABC191に参加しました。 A,B,Eの3問正解でパフォーマンスが1407でした。 C問題、D問題が解けなかったのが悔しい。
C問題は意味と方針がよくわからなかったけど、先に解けそうだったから問いたE問題が正解できたのは大きかった。 D問題は愚直に実装したら案のサンプルの時点で定時間制限を超えたので別の解き方をで問いてたらバグ取りが間に合わなくて時間切れ。

A問題

問題文通りに実装。 ボールが消え始める距離とボールが出現する距離を計算して、その区間内にDが含まれるかどうかで判定。

B問題

A問題同様に問題文通りに実装。 一旦配列に入れてから、前から順番に指定された値かどうかを確認して出力。

C問題

愚直に実装した場合

探索の範囲を円に外接する正方形の中に絞って2重ループで正方形内のすべての格子点を探索。 案の定サイズが大きくなるとTLE。

方針変更後

正方形の中を探索するのはそのままにX座標は全探索。 Y座標は正方形の上からと下から探索して円の内部か周上にある最小と最大の座標を求めて、その区間に点がいくつあるかを計算していく。 愚直にやるよりは早そうだけどなんかバグってた。

E問題

問題文を読んで最短経路を求める必要がありそうだったので自前のダイクストラ法のコードをコピペ。 辺の情報を受け取る時ついでに町i行きの辺を持つ町とそのコストを求めておきつつ、町iを始点としてダイクストラ法を実行して各町へのコストを計算。
計算した最短経路のコストと、事前に用意しておいた町iに行ける町とそのコスト情報をもとに町iからどっかの辺を通って町iに帰ってくるコストを算出して出力。

所感

C問題、D問題が解けないのはちょっときついなあ。代わりにE問題が解けたから順位的には致命傷にはならなくて済んだ。
大学のときにネットワークの研究室にいたからグラフが出てくる問題にはそれほど抵抗がないけど、他の人はグラフとか最短経路求める系の問題が苦手な人多いのかなあ。