Quiz
AC Code
https://atcoder.jp/contests/arc085/submissions/8316327
解法
アルメリアさんの解説の通り
その他
- 割る・残すは右左のどちらでもいい(今回たまたまアルメリアさんとは逆になった)
- 罰金を最小化する問題に置き換えてフロー
- 倍数の石は同時に割らなければ行けない条件を辺としてはる(4→2へinf、など)
- 最初、2→4の方向で張ってしまって解答が合わず
- ちゃんと考えるのもよし、逆向きで試してみるもよし
最大流ライブラリ
// 最大流用の辺 struct Edge{ ll to; ll capacity; ll rev; // index Edge(ll t, ll c, ll r){ to = t; capacity = c; rev = r; } Edge(){} }; // 最大流 // ford fulkerson ver struct MaxFlow{ vector<vector<Edge> > G; vector<bool> used; MaxFlow(ll node_num){ G.resize(node_num); used.resize(node_num); } void add_edge(ll from, ll to, ll capacity){ G[from].push_back(Edge(to, capacity, G[to].size())); G[to].push_back(Edge(from, 0, G[from].size()-1)); } ll dfs(ll v, ll t, ll flow){ if(v==t) return flow; used[v] = true; for(Edge &edge : G[v]){ if(!used[edge.to] && edge.capacity > 0){ ll d = dfs(edge.to, t, min(flow, edge.capacity)); if(d>0){ edge.capacity -= d; G[edge.to][edge.rev].capacity += d; return d; } } } return 0; } ll calc(ll start, ll end){ ll flow_sum = 0; while(true){ fill(ALL(used), false); ll f = dfs(start, end, inf); if(f==0){ break; } flow_sum += f; } return flow_sum; } };
最大流を実際に使っているコード
- 始点を0
- 石を1~N
- 終点をN+1とした
ll N; cin >> N; VI A(N); rep(i, N){ cin >> A.at(i); } MaxFlow flow(N+2); // 0 start // 1-N node // N+1 sink ll sum = 0; rep(i, N){ ll id = i+1; ll a = A[i]; if(a>=0){ sum += a; // 無条件で貰えるお金 flow.add_edge(0, id, a); // waru flow.add_edge(id, N+1, 0); }else{ flow.add_edge(0, id, 0); flow.add_edge(id, N+1, -a); } } FOR(i, 1, N){ // iの倍数へのエッジ FOR(m, 2, 101){ if(i*m>N)break; flow.add_edge(m*i, i, inf); } } ll penalty = flow.calc(0, N+1); ll ans = sum - penalty; p(ans);
他の最大流を使う問題(not 燃やす埋める)
- D - 浮気予防
- C - おいしいたこ焼きの売り方
2021年、E-MUL解き直し。雰囲気で解いていたのでハマった
- AC
- 説明
- コードにもコメントしたが、注意ポイントが2つある
- 注意ポイント11にあるように、Aiが正のものだけ先に報酬を与える必要がある。Aiが負のものは「先に報酬」の工夫なしにグラフ上のペナルティとして表現できるので「先に報酬」は不要
- N=2
- 考えがあっているか確認するには、N=2の単純な場合を考えるといい
- N=2, A=[5,-10]の場合
- 1番目を残し、2番めを破壊すればいいのは自明。これをフローで表現できているか図示すると、下記のようになる
- 赤い線を左から右に横切る辺のコストがペナルティとなることが分かる(なので中央の∞ペナルティはかからない)
#include <atcoder/maxflow> using namespace atcoder; // 忘れがち int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; VI A(N); rep(i, N) cin >> A[i]; ll start=N; ll end=N+1; ll base=0; for(ll a : A){ if(a>0) base+=abs(a); // 注意ポイント1:「正のものだけ」先に報酬を与える } mf_graph<ll> graph(N+2); rep(i,N){ ll a = A[i]; if(a>=0){ graph.add_edge(start,i,a); graph.add_edge(i,end,0); } else{ graph.add_edge(start,i,0); graph.add_edge(i,end,-a); } } rep(i,N){ FOR(j,i+1,N){ if(i==j)continue; ll a = i+1; ll b = j+1; if(b%a==0){ graph.add_edge(j,i,inf); // 注意ポイント2:方向 (i->j or j->i) } } } ll fl = graph.flow(start,end); ll ans = base-fl; p(ans); return 0; }