yukicoder209

うわっ…私の更新頻度、低すぎ…?

初めてyukicoderで全完できたので久しぶりに更新します

A問題 野菜が苦手

解法

とっさに算数ができないので肉も野菜も枚数全探索します

B問題 UMG

解法

中心を固定して両端を広げます。

C問題 木を道に

解法

次数が3以上の頂点全てについて2になるようにしたいです。実はこれは次数が1の頂点にくっつけまくればいいです。

D問題 umg tours

解法

制約的にDijkstra一回とかで済ませたいです。1を始点にすれば良さそう。
コストを0にできるのは一回だけなので、持つべき状態を(距離, 場所, 0にした回数)にすればいいです。JOIによくあるやつ

E問題 Kaiten Sushi?

問題

No.808 Kaiten Sushi? - yukicoder
自分の席が回るんですね。めちゃくちゃ酔いそう

解法

だいたい貪欲っぽくいけば良さそうだけど、サンプル1の通り先に奥から取ったほうがよい事があるっぽい。
次の次に取るものが変わらないようにしながら、次に取るものを一番奥にすればよさそうである。
例えば

4  7 9
 56 8

で今4にいるとき、次に取るべきお茶は6になる。
もし8を取ると、7のためにもう一周する必要があるので、7より前のお茶を取りたい。
5を取るよりは6を取ったほうが最終周とかで得になることがある。

これは

  • now : 今いるところ
  • a : nowから取れる一番近いところ(反対サイド)
  • b : aから取れる一番近いところ(今いるサイド)
  • c : (now,b)のb寄りのところ(反対サイド)

を調べ、cを取る。
ということをN回繰り返せば良い。setと二分探索を使えばO(NlogN)で解ける。
二分探索でバグらないようにsetには一周後と二周後を入れておくと楽