ゆるふわ競プロ

Javaでゆるゆる競プロしています.忘れっぽいのでメモ用,復習用

yukicoder 209

yukicoder 209 参加記

No.807 umg tours - yukicoder

yukicoder2回目の参加となりました. 前回は星2つでリタイアしてしまったので今回は星2つを通そうと意気込んでいました.


#A No.804 野菜が苦手

この問題は,条件が100以下と小さいので1から少しずつカウントして行けば十分間に合います. 終了条件に注意が必要でした. ボクは終了条件一つ書き間違えてWAしてしまいました.A問題のWAは心に悪い.

cnt : 食べた野菜の数
  • 終了条件
    • cnt が与えられた野菜の数になる
    • cnt * 野菜に必要な肉 > 肉の数
    • cnt + cnt * 野菜に必要な肉の数 > 食べられる量

この3つの条件を考えてcntを徐々に増やしていきました

#B No.805 UMG

最初誤読していました.

UUMGG

の場合UMGの部分列が何個取り出せるかという問題かと思いました.(TESTケース)で気づくことができた.j - i = k - jという条件を完全に見逃していました.
言い換えるとMを中心にUGが等距離離れていればいいという問題です.
ひたすら全探索することで答えが得られました.配列外へのアクセスが内容にするのがポイントです.

#C No.806 木を道に

グラフ理論の本のPDF(ネットに上がってる軽いもの)を少し読んだことがあったので木構造を少し理解することができました. node数与えられているのにpathの数が与えられていないじゃんと最初思いましたが木構造なので,node数引く1がpathの本数になります. これは瞬時に気づきたかった. この数字を用いて入力作業を行います. 最終的には1ほんの道にしたいです.つまり各nodeの字数を2いかにしなければなりません.(これ全然自然な発想ではない)各edgeごとにnode数を数えて2より大きい分だけ削って行けば答えが出せました.
グラフ理論の知識が役たって嬉しかった問題です.

#D umg tree

本番中にはACすることができませんでした.

考察

ある点に行って帰ってを行うのに最小のコストが知りたい. 一度だけコスト0の変更することができるので行きと帰りでは確実に使用するコストが異なります.どちらでVIPを使っても一般できに答えは変わりません.
今回はVIPを使って点までいく最小コストとVIPを使わずに点までいく最小コストを求めます.ここまでは考察できたのですが実装ができませんでした.最小コスト(最小経路問題)で負のコストを含むためダイクストラ法かなと考えていました. わーシャルフロイド法かベルまフォード法もあるしどれかやろwとってわからんから離脱しました. ##### 解説見て 解説見たら考察の仕方があってました!!これは嬉しい.あとダイクストラ法を用いるまであっていました.ここまできたらただの練習不足感が否めませんね..