ei1333の日記

ぺこい

AtCoder Regular Contest 078

意思に反してレートが上がる….

CDF を解いて 3 完.

2421 -> 2495(+74) highest.

C - Splitting Pile

arc078.contest.atcoder.jp

解法

 {N - 2} 通りの全てのパターンを試したい気持ちになる.

で, これはできるため.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int64 INF = 1LL << 59;
 
int main()
{
  int64 N, A[200000];
  cin >> N;
  int64 all = 0;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    all += A[i];
  }
 
  int64 ret = INF;
  int64 sum = 0LL;
  for(int i = 0; i < N - 1; i++) {
    sum += A[i];
    all -= A[i];
    ret = min(ret, llabs(all - sum));
  }
  cout << ret << endl;
}

D - Fennec VS. Snuke

arc078.contest.atcoder.jp

解法

400 点問題で出る可能性のある解法を考えるとはいになる.

400 点問題ということを忘れずにぐっと睨むと, 任意の頂点について距離が相手より近ければ自分の色で塗れることがわかる.(両者は相手が塗れる頂点を最小化したい気持ちになって, これは相手に近づく方の頂点を優先して塗ったほうがいいことがわかって, これは最短距離っぽい)

このような個数は, 適当にDFSすればもとまる.

でこの頂点数が多い方が勝てる.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
vector< int > g[100000];
int dist[2][100000], id;
 
void dfs(int idx, int par = -1)
{
  if(~par) dist[id][idx] = dist[id][par] + 1;
  for(auto &to : g[idx]) if(to != par) dfs(to, idx);
}
 
int main()
{
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
 
  id = 0;
  dfs(0);
  id = 1;
  dfs(N - 1);
 
  int ret = 0;
  for(int i = 0; i < N; i++) {
    if(dist[0][i] <= dist[1][i]) ++ret;
  }
  if(ret >= (N + 2) / 2) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
}

F - Mole and Abandoned Mine

arc078.contest.atcoder.jp

解法

「頂点  {1} から頂点  {N} への経路が  {1} 通り」をもうちょっと一般的な形で言い換えてみたい気持ちになる.

すると「頂点  {1} から頂点  {N} の経路間にある辺が橋のみ」ということがわかる(それはそうなので).

経路間にある頂点の気持ちを考えると, その頂点からある頂点につながっていてもいいが, その頂点から他の経路間の頂点に到達できてはいけないという気持ちがわかる.

お絵かきしてみると以下の図が生まれる. 丸みたいなのが連結成分みたいになっている.

f:id:ei1333:20170716005644p:plain

なんかこれはDPで求まらなきゃ無理という気持ちになるのでDPを考える.

必要っぽい情報としては「どの頂点が未使用か( {2^N} 通り)」と「直前の経路間にある頂点 ( {O(N)} 通り)」.(直前の経路上にある頂点の情報は, 次に使う経路上の頂点間に辺がないと険しい気持ちになるので必要)

遷移としては未使用の頂点の任意の部分集合のうちのどれかをえい(連結成分をぐいってする感じになるので) するみたいな感じになる. 部分集合を求めるのが険しいが, 以下のブログを読むとわかるので解けそうだということがわかる.

topcoder.g.hatena.ne.jp

必要そうな情報を前計算をしておくと  {O(3^N N^2)} みたいな感じになって, 祈ると間に合う.

ソース

考察っぽい漠然とした何かは時間はかからなかったけど, 漠然としていたので実装時間などがアになった.

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
 
int N, M;
int g[17][17];
int lookup[1 << 17];
int dp[1 << 17][16];
vector< int > add[1 << 17];
 
int rec(int mask, int pre)
{
  if(mask == 0) return (0);
  if(~dp[mask][pre]) return (dp[mask][pre]);
  int ret = -INF;
  for(int i = mask; i > 0; i = (i - 1) & mask) {
    for(auto &j : add[i]) {
      if(pre != 15 && g[pre][j] == 0) continue;
      ret = max(ret, rec(mask ^ i, j) + lookup[i] + g[pre][j]);
    }
  }
  return (dp[mask][pre] = ret);
}
 
signed main()
{
  memset(dp, -1, sizeof(dp));
 
  cin >> N >> M;
  int all = 0;
 
  for(int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a][b] = c;
    g[b][a] = c;
    all += c;
  }
 
  for(int i = 0; i < 1 << N; i++) {
    if(i & 1 && (i >> (N - 1)) & 1) continue;
    for(int j = 0; j < N; j++) {
      if((i >> j) & 1) {
        if(i & 1) {
          if(j == 0) add[i].push_back(j);
        } else if((i >> (N - 1)) & 1) {
          if(j == N - 1) add[i].push_back(j);
        } else {
          add[i].push_back(j);
        }
        for(int k = j + 1; k < N; k++) {
          if((i >> k) & 1) lookup[i] += g[j][k];
        }
      }
    }
  }
  cout << all - rec((1 << N) - 1, 15) << endl;
}