A一完でした。
C - 01 Balanced
解説AC。
「牛ゲー」というキーワードを聞いても解法が分からず、解説を読んで図を描いてようやく理解できた。
コンテスト中は連立方程式を解くことを中心に考えていたが、それでは計算量が落ちなそう。だったらグラフの問題なのでは？ とはちょっとだけ思った。
しかし、そう気付いても実際にグラフに落とすのはなかなか難しい……。
ただ、グラフにしようと思えば、頂点はN個（か、01列の最初・間・最後を考えてN+1個）だろうし、辺として考えられるのは、
・隣同士の頂点を結ぶ
・問題文の条件にある0と1の個数が同じ範囲の始点と終点を結ぶ
くらい。あとは、辺の重みをどうにかしようという気持ちになれば、解法にたどりつくのは不可能じゃなかったかな、とは思う。
牛ゲーに関連してこの問題を見てみたけど、大分雰囲気が違いますね。
こちらは、「$x-y\leq w$という形の不等式（がたくさん）で表せたら牛ゲーを考えよう」という感じの問題でした。
0 件のコメント:
コメントを投稿