読者です 読者をやめる 読者になる 読者になる

おかゆの競プロ(その他)日記

主に自分の解いた問題を載せていきます。競プロ以外にもなにか載せるかもしれません。

ABC051 - B,C,D

久しぶりの投稿です。
AtCoder Beginner Contest 051のB,C,Dを書きたいと思います。

・B問題(B - Sum of Three Integers)
入力K,S(2 <= K <= 2500, 0 <= S <= 3K)が与えられ、3つの変数x,y,z(0 <= x,y,z <= K)がx+y+z=Sを満たすようなx,y,zの組み合わせがいくつあるか、という問題。

想定解法としては、x,yの値を決めれば、x+y+z = Sを満たすようなzは勝手に決まるので、x,yの値を全探索すればO(K^2)くらいで求められるみたいな感じでしたが、この時の僕はあろうことかx,y,zを全探索で求めようとしてTLE(まあこれは分かっててやってしまった感じ)、そこから方針を変えて、Sが偶数か奇数で場合分けをし、それぞれの場合で和がSとなるようなx,y,zの値の組み合わせを、それぞれが奇数か偶数で場合分けし…というような、目も当てられないような酷いコードを書きました。それでも最大ケース(K = 2500, S = 7500)はTLEしていたので、そのケースだけif文で書いて提出したらACしてしまいました…。ちなみに計算量は、O(K * (2 * (K/2)^2)) = O(K^3)です(定数倍で少し速くなってるかもしれない)。

 

 別解では、O(K)解法やO(1)解法がありました(すごい)。

ちゃんと考えて実装するように気をつけます。

 

・C問題(C - Back and Forth)

xy平面上の点(sx, sy)と(tx, ty)が与えられる(-1000 <= sx, sy, tx, ty <= 1000)。(sx, sy)を始点、(tx, ty)を終点として2往復するのだが、その際に一度通った点は通らずに移動しなければならない。そのときの最短経路を1つ求めて、L,R,U,D(L:左,R:右,U:上,D:下)でその経路を表した文字列を出力する(日本語が怪しいかもしれない)。

これは一見、最短経路とか書いてあるしワーシャルフロイドとかダイクストラ、それとも優先探索?などと思いがちかもしれませんが、その必要はなかったです。

2往復しなければならず、かつ一度通った点には行けない -> 2回目は遠回りしないといけない

ということに気づければ特に難しいことはありません。

(例)

(sx, sy) = (0, 0), (tx, ty) = (2, 2)とした時、

(0, 0) -> (1, 0)(右へ) -> (2, 0) -> (2, 1) -> (2, 2)

 ... ここで(tx, ty)に到着

(2, 2) -> (1, 2) -> (0, 2) -> (0, 1)(上から戻る) -> (0, 0)

 ... ここで一往復した

ここで、最短経路なので(0, 0) -> (1, 0)または(0, 1)に行きたい…でも一度通った所は行けない、じゃあどうする? -> 右方向と上方向は行き帰りで使ってしまったので残りの左と下を使って行くしかない、となります。

(0, 0) -> (0, -1)(下へ) -> (1, -1) -> (2, -1) -> (3, -1) -> (3, 0) -> (3, 1) -> (3, 2) -> (2, 2)

 ... やっと(tx, ty)に到着

(2, 2) -> (2, 3) -> (1, 3) -> (0, 3) -> (-1, 3) -> (-1, 2) -> (-1, 1) -> (-1, 0)(左から戻る) -> (0, 0)

 ... 到着!

つまり何が言いたいかというと、

2回目は1回目のときより上下左右に余分に1回ずつ動かなければならない(言い換えれば、余分に1回ずつ動けば良い)ということです。

このような感じでやるとACできました。

 

 ・D問題(D - Candidates of No Shortest Paths)

自己ループと二重辺を持たない頂点数N、辺数Mの重み付き無向グラフが与えられるので、どの2頂点間のどの最短経路にも含まれない辺の数を求めるという問題。

要は、

全点間の最短経路を求めてから使われていない辺を数え上げれば良い

のですが、僕はあろうことか最小全域木を求めていました…。最小全域木とは、最小の総和コストで構成される全域木のこと(全域木 - Wikipediaより)。

最小全域木を求めてから使われていない辺を数える、みたいなことをしていたんですが、そもそも最小全域木を求めることと、全点間の最短経路を求めることは違います(そりゃそうです)。kruskal法を投げても通らないわけです。

コンテスト後、ワーシャルフロイドで書いてみたら通りました。計算量はO(N^3 + M)くらいですかね?

 

もっと問題をこなして経験値を蓄えていくぞ〜