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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#022

ABC

なぜかタイトルイニシャルが全てBBのABC
ライブラリの用意不足により実装時間が足らず3完部分点で撃沈しました.

- A問題「Best Body」

(http://abc022.contest.atcoder.jp/tasks/abc022_a)

問題概要:
体重の変化記録が与えられるので,S以上T以下であった日数を答える問題です。

解法:
初期状態を0として1日目を+Wとすると実装が楽になります。

ソースコード:
https://abc022.contest.atcoder.jp/submissions/391644


- B問題「Bumble Bee」

(http://abc022.contest.atcoder.jp/tasks/abc022_b)

問題概要:
A_jが与えられ,[tex:A_i = A_jかつi解法:
今までに発見した花をbool型の配列で管理します。
A_iが与えられたとき,flag(A_i)がtrueなら1を加算し、falseならtrueにするだけです。

ソースコード:
https://abc022.contest.atcoder.jp/submissions/391829


- C問題「Blue Bird」

(http://abc022.contest.atcoder.jp/tasks/abc022_c)

問題概要:
グラフが与えられ、指定された点を含む閉路のうち、コストの和が最小になるものを答えよという問題です。

解法:
ダイクストラいじってなんとかしようとしましたがダメそうでした。
始点を含む閉路について考えます。
その閉路から始点を抜くと、一本の直線パスになります。そのパスのコストの総和+パスから始点へのパスのコストを足し合わせると閉路のコストの総和となります。
始点以外の全頂点間最短距離を求めておき、始点につながっている2辺を引っ張ってきて辺をつなげるという算段です。
ワーシャルフロイドをぶっ放せば計算量はO(N^3)となります。

ソースコード:
https://abc022.contest.atcoder.jp/submissions/392625


- D問題「Big Bang」

(http://abc022.contest.atcoder.jp/tasks/abc022_d)

問題概要:
N点の星の変化前と変化後の座標が与えられます。変化前の座標に対して並進、回転、拡大縮小を順に行ったときの座標が変化後の座標です。拡大縮小のスケールを答えよという問題です。
解法を思いついてから実装に1時間半かかっているので非常に悔しい。

解法:
並進、回転、拡大縮小の3単語でアフィン変換の行列うんぬんとか考えてました。
が、変化前の座標と変化後の座標のインデックスが一致していないためうまく特定できません。
悩み続けた結果、スケールがP倍のとき2点間の距離もP倍になります。つまり変化前と変化後の最近点対を求めてその比を計算すれば良いのです。
最近点対を発見するためのアルゴリズムとして、分割統治法を使ったものが挙げられます。
分割統治法を使うことで計算量がO(N \log N)になるので無事ACです。
アルゴリズムの詳しい解説は後日。

ソースコード:
https://abc022.contest.atcoder.jp/submissions/393730