AtCoderLogs

published: 2021/7/1 update: 2021/7/22

Table of Contents

AtCoder Logs

ABC097-C

小さい方から見ればよくなので、明らかに長さ5以下のsubstring(部分文字列)のみを見れば良い。

ABC097-D

swapできる対象をエッジとするグラフだと考えると、同じ連結成分に属していればそのindex同士は交換可能になる。union-findで正しい場所にある値同士が交換可能かどうか判定していけば答えは求まる。

memberに属しているかどうかを判定したくてmemberメソッドみたいなのを作成したが明らかに遅いのでデバッグ以外に使うことはなさそう。基本的にこれを使いそうになったらeqivを使うことを考えるべき。

これABC177-Dと対して難易度変わらない気がするんだけど水色...?

ABC204-C

なので、BFSを全点でやってもで十分間に合う。

ABC204-D

貪欲法を考えてだめだったやつ。DPに帰着できる。オーブンの分け方を全通り試すのは計算量的に無理。

それぞれのオーブンでかかる時間をA, Bとすると求めたいものはの最小値。オーブンは交換可能なので、としてよい。なので、を最小化することが目的になった。

のときに、なので、。このとき、を最小化したい。最小化するにはの範囲内でできるだけ大きければいい。

[0, S/2]の範囲で取りうる部分和はDPを用いて計算することができるので、答えが求まった。

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

ofuse

Other Articles

Site Map

Table of Contents

    AtCoder Logs


当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

ofuse
Privacy Policy

Copyright © illumination-k 2020-2021.