少ない学びをせめて記録する

技術記録、競プロメモ、その他調べたことを書く @京都, twitter : @nehan_der_thal

Codeforces Round #620 (Div1 + Div2) 参加記録

codeforces

A, B, Dの３つ解けました。遅かったのでレートは下がりました。(1752 -> 1716) f:id:whitman:20200218154122p:plain

A Cow and Haybales

苦手系です。割算を頑張りましょう。 こういう割算の算数系はそれほど難しくない割に時間がかかって本当に苦手です。

B Cow and Friend

ちょうどのものがあれば1です。目的地より遠くに飛べれば2です。 目的地より近くにしか跳べないなら、跳べる最長の距離で切り上げ除算です。

C Cow and Message

今見ると簡単ですが頭が混乱していて解けませんでした。 長さ2以下の文字が答えになるので長さ2以下の部分列をそれぞれ数えます。

D Cow and Fields

難しかったです。各special field Pi について始点からの距離と終点からの距離を計算しておきます。これはbfsでできます。 すると、Pi とPjを繋いだときの1-Nの最短パスはd(1, Pi) + d(Pj, N) + 1, d(1, Pj) + d(Pi, N) +1, d(1, N)のいずれかになります。（d(x, y)はつなぐ前のx-yの距離） あとはMin(d(1, Pi)+d(Pj, N), d(1, Pj) + d(Pi, N))が最大となるように(i, j)を見つければいいです。 全探索だとN**2かかるので工夫が必要です。私は以下のようにやりました。

d(1, Pi) をai, d(Pi, N) をbiとする。 ai<aj, bi<bjがあればai, biはいらないので消す。あとは(ai, bi) についてai < aj となるjを調べると最小のajの(aj, bj)を選べばいいことがわかる。aiでソートしてから隣り合うものについてMinを計算してMaxをとる。

以下はtwitterで見つけた賢い解法です。（こういうのって転載いいのかな）