C - 最小カットと最大カット この問題は、 「N頂点N辺の連結なグラフが与えられるので、頂点を2色に塗分けて、両端の頂点の色が異なるような辺の数を(最小/最大)化せよ(但し、色は2色とも1度は使用しなければならない)」 という問題です。 まず、最小は簡単…
Tasks - 全国統一プログラミング王決定戦 エキシビジョン A:接頭辞たちは、文字列の先頭から何文字か切り出したものなので、辞書順ソートすると接頭辞の長さ順になります。よって、接頭辞配列は{先頭から1文字目まで,先頭から2文字目まで,...,先頭からN文字…
AtCoder Beginner Contest 117 - AtCoder A: Entrance Examination 飛んだ先の世界で時間が時間過ぎると、元の世界では時間は時間過ぎます。 https://atcoder.jp/contests/abc117/submissions/4157588 B: Polygon 多角形の成立条件に関する問題。問題文を読…
H - 包囲 この問題は、いくつか格子点が与えられるので、その格子点の中からいくつか選んで単純多角形を作り、その内部(線上はナシ)に原点を取り囲め、というものです。 まず、少し頭を使って考えると、下図のように、ある3点を結ぶ三角形の内部に原点が来る…
3:59 E<体感400>dp[価値]=その価値を達成する最小コスト。https://atcoder.jp/contests/dp/submissions/3936145 9:44 H<体感400>所謂11解法。dp[a][b]=(上+左)。https://atcoder.jp/contests/dp/submissions/3936760 20:03 C<体感300>dp[日付け][直近の操作A…
F - Lotus Leaves この問題は、カエルが移動する方法をなくす、という時点で最小カット問題を連想すると思います。 次に考えるのは、葉をグラフの頂点とみなして最小カットに似たことをする、という方針ですが、これをすると辺の張り方がわからなくなる上、…
B - Tree Burning この問題の解説の証明部分がよくわからなかったので、自分で証明を考えました。 まず、座標正の向きに移動する行為をFと、負の向きに移動する行為をBと定義します。 そして、操作の列をFFBFBF...のように表記することにします。 ここで、高…
D - No Need この問題は、まずサンプルケース、特にSample 3の 6 2010 4 3 10 25 2 を見て実験すると、どうやら要らなくなるのは2,3,4の3つだということがわかります。 ここで、直観的に「不要な数がk個存在するなら、それは小さい順からk個である」という仮…
はてブロを始めました。 主に競プロの面白いと思った問題をまとめる、みたいなことをすると思います。 宜しくお願いします。
