ARC095 F - Permutation Tree -

問題

F - Permutation Tree

解法

まず、数列から木を作ってみる。
作ると木に頂点を追加するときは、脚を増やすか胴体を伸ばす選択肢しかないことが分かる。
(こういう木をcaterpillarというらしい。確かに毛虫っぽい。)

なぜ、caterpillarになるのかのイメージは公式の動画解説が分かりやすい。 f:id:shot_1107:20180419034933j:plain

数列から作られる木はcatapillarなので、 与えられる木がcatepillarだったらそれから作ることができる辞書順最小の数列を出力、そうではなかったら−1を出力すればいい。

数列の作り方として、
1はどこに置いても変わらないので最初に置いたほうがいい。
それ以外の数字もできるだけ小さいのからつかっていきたい。
caterpillarと数列の関係性を見ると、脚は順序が逆転してる頂点間に生えている。
上記の考察から胴体は小さい順につなげていき、脚が生えていたらその脚の数分の数字を、脚の生えている頂点より左に置くという感じで数列を構成していく。

胴体が木の直径であることは直感的に分かる。数列の構成の仕方として2パターン考えられるが(直径の端は2つあるので)、その2つのうち、辞書順で小さい方を最終的に出力すればいい。

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if ( a > b ) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if ( a < b ) a = b; }

using Pii = pair<int, int>;

const int INF = 1e18;

struct Edge {
  int t, w;
  Edge(){}
  Edge(int t, int w): t(t), w(w) {}  
};

vector<Edge> G[100001];
int n, d[100001];
int st, ds;

void bfs(int s) {
  for ( int i = 0; i < n; i++ ) d[i] = INF;
  queue<int> q;
  q.push(s);
  d[s] = 0;
  int u;
  while ( !q.empty() ) {
    u = q.front(); q.pop();
    for ( int i = 0; i < (int)G[u].size(); i++ ) {
      Edge e = G[u][i];
      if ( d[e.t] == INF ) {
    d[e.t] = d[u]+e.w;
    q.push(e.t);
      }
    }
  }
}

void calc_d() {  
  bfs(0);
  int maxv = 0;
  st = 0; ds = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INF ) continue;
    if ( maxv < d[i] ) {
      maxv = d[i];
      st = i;
    }
  }

  bfs(st);
  maxv = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INF ) continue;
    if ( maxv < d[i] ) {
      maxv = d[i];
      ds = i;
    }
  }
}

int pre[100001];
bool is_body[100001];
vector<int> path;
void calc_path(int v, int p) {
  pre[v] = p;
  for ( int i = 0; i < (int)G[v].size(); i++ ) {
    Edge e = G[v][i];
    if ( e.t == p ) continue;
    calc_path(e.t, v);
  }
}

bool is_caterpillar() {
  for ( int i = 0; i < (int)path.size(); i++ ) {
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;      
      if ( is_body[v] ) continue;
      if ( (int)G[v].size() > 1 ) return false;
    }
  }

  return true;
}

signed main() { 
  cin >> n;
  for ( int i = 0; i < n-1; i++ ) {
    int v, w;
    cin >> v >> w;
    v--; w--;
    G[v].push_back(Edge(w, 1));
    G[w].push_back(Edge(v, 1));
  }
  
  calc_d();

  calc_path(st, -1);
  {
    int v = ds;
    while ( v != -1 ) {      
      path.push_back(v);
      is_body[v] = true;
      v = pre[v];
    }
  }

  if ( !is_caterpillar() ) {
    cout << -1 << endl;
    exit(0);
  }

  vector<int> ans1, ans2;
  int idx = 1;
  for ( int i = 0; i < (int)path.size(); i++ ) {
    int tmp = idx;
    idx++;
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;     
      if ( is_body[v] ) continue;
      ans1.push_back(idx++);
    }
    ans1.push_back(tmp);
  }

  idx = 1;
  for ( int i = (int)path.size()-1; i >= 0; i-- ) {
    int tmp = idx;
    idx++;
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;     
      if ( is_body[v] ) continue;
      ans2.push_back(idx++);
    }
    ans2.push_back(tmp);
  }

  vector<int> ans = min(ans1, ans2);

  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  
  return 0;
}

感想

実は木の直径を使う問題は初めてだった。 キャタピラーと言われるとポケモンキャタピーを思い浮かべてしまう。

ARC094 F - Normalization -

問題

F - Normalization

解法

この問題の部分問題として、S->Tに変換できるか考える。
まず、Sから変換している以上、同じ文字が連続している箇所がないとおかしい。
さらに、a->0 b->1 c->2 とそれぞれの文字に数字を割り当てS,Tを数列とみなしたとき、
(∑S) mod 3 == (∑T) mod 3
を満たしていないといけない。(これ気づくの不可能では)
例として
abc と ccc を比べてみると
abc -> 0 + 1 + 2 = 3
ccc -> 2 + 2 + 2 = 6
となり、mod 3 した値は等しくなる。
S.size == 4 のときをすべて示して、
S.size >= 5 のときはそれを元に帰納法っぽく証明できるらしい。

上のことが分かればあとはDPするだけ。 dp[index][今までの総和mod 3][前につかったやつ][同じ文字が連続したか]

場合分けとして、
S に含まれる文字が1種類のときは1を出力する。
S.size <= 3 の時は全探索
S.size >= 4 の時はDP(Sに同じ文字が連続した箇所がなければ+1(DPで数えてないので))

ソースコード

#include <bits/stdc++.h>
using namespace std;h

const int MOD = 998244353;

string s;
vector<int> v;
int l;
int mod3_s;
map<vector<int>, bool> used;

int solve1(vector<int> now) {
  if ( used[now] ) return 0;
  used[now] = true;
  
  int ret = 1;
  for ( int i = 0; i < l-1; i++ ) {
    if ( now[i] != now[i+1] ) {
      vector<int> nxt = now;
      nxt[i] = nxt[i+1] = 3-now[i]-now[i+1];
      ret += solve1(nxt);
    }
  }
  
  return ret;
}

int dp[200001][3][4][2]; //dp[idx][mod 3][bool]
int solve2(int now, int mod3, int pre, int flag) {
  if ( now == l ) {
    if ( flag && mod3 == mod3_s ) return 1;
    else return 0;
  }
  if ( dp[now][mod3][pre][flag] >= 0 ) return dp[now][mod3][pre][flag];
  
  int ret = 0;
  for ( int i = 0; i < 3; i++) {
    ret += solve2(now+1, (mod3+i)%3, i, flag|(pre==i));
    ret %= MOD;
  }

  return dp[now][mod3][pre][flag] = ret%MOD;
}

int main() {
  cin >> s;
  l = s.size();
  for ( int i = 0; i < l; i++ ) v.push_back(s[i]-'a'), mod3_s += v[i];
  mod3_s %= 3;  

  if ( (((int)s.find("a") >= 0) + ((int)s.find("b") >= 0) + ((int)s.find("c") >= 0)) == 1 ) {
    cout << 1 << endl;
  } else if ( l <= 3 ) {
    cout << solve1(v) << endl;
  } else {
    fill_n(***dp, 200001*3*4*2, -1);
    int ans = solve2(0, 0, 3, 0);
    if ( !((int)s.find("aa") >= 0 || (int)s.find("bb") >= 0 || (int)s.find("cc") >= 0) ) ans++;
    cout << ans << endl;
  }
  
  return 0;
}

感想

文字列を数列にしてmod 3するみたいなのは考えもしなかった。
今後の解法の選択肢の一つとして覚えておきたい。

ARC094 D - Worst Case -

問題

D - Worst Case

解法1

公式解説通り

#include <bits/stdc++.h>
using namespace std;

using Int = long long;

int main() {
    Int Q;
    cin >> Q;
    while ( Q-- ) {
        Int A, B;
        cin >> A >> B;
        if ( A > B ) swap(A, B);
        
        if ( B - A <= 1 ) cout << 2*A-2 << endl;
        else {
            Int C = (Int)sqrt(A*B);
            if ( C*C == A*B ) C--;
            if ( C*(C+1) >= A*B ) cout << 2*C-2 << endl;
            else cout << 2*C-1 << endl;
        }
    }

    return 0;
}

解法2

dohatsuさん解
高橋君よりスコアの小さい参加者の人数を二分探索で求める。
そのために、N人を参加者の人数にできるかという、部分問題を考える。

例として、A = 5, B = 10, N = 12の場合を考える。
1回目の他の参加者の候補として、
1 2 3 4 6 7 8 9 10 11 12
2回目の他の参加者の候補として、
1 2 3 4 5 6 7 8 9 11 12
が考えられる。
参加者の人数をできるだけ多くするためには、
(1, 12) (2, 11) ... (12, 1)
のようにするのがいいことが分かる。(積をいい感じに少なくするため(証明はしてない))

凸関数になっていそうなので、真ん中あたりの値だけ確認すればいい。
(a, b) という組み合わせがあったとき、ab >= AB を1つでも満たしてしまったら、Nは答えとして採用できない。
真ん中を適当に100個ぐらい見れば多分十分。

以上のことが分かれば、二分探索で解くことができる。

感想

sqrt(A*B)付近になることは分かったんだけど、そこからWAが取れなかった。
こういう問題を論理的に考えて解けるようにしたい。

DDCC2016 本戦 C - 01文字列 - 

問題

C - 01文字列

解説

https://ddcc2016-final.contest.atcoder.jp/data/other/ddcc2016-final/editorial.pdf

考察

公式解説そのまま

NをTのサイズとすると、
操作1と操作2は合計で N 回行われることは明らか。
よって、操作1と操作2をそれぞれ何回行うか、そのとき操作3は何回する必要があるかが分かればよさそう。

まず、操作1と操作2をそれぞれ何回行うかというのは、文字列Tをどこで区切るかということである(前半部分と後半部分に分ける)

次に操作3は何回する必要があるかについて、
前半部分( l とする)、後半部分( r とする)それぞれについて考える必要がありそう。
r については以下のように求めることができる。 (公式解説より引用)
1. 次に末尾に追加したい文字が 1 である限り,操作 2 を行う
2. N 文字入力したならば終了.そうでなければ 3. へ
3. 操作 3 を行い,0 と 1 を置き換える
4. 次に末尾に追加したい文字が 0 である限り,操作 2 を行う
5. 操作 3 を行い,0 と 1 を置き換える
6. N 文字入力したならば終了.そうでなければ 1. へ

l についてもほぼ同じ方法で求めることができる。

操作 3 を行うタイミングを l の構成時と r の構成時で揃えると考えることでで操作 3 の回数を l と r の max に押さえることができる。

これだけだと O(N2) になってしまうので、もう少し工夫する必要がある。

上記の考察から操作3が行われるのは、隣り合う文字が異なる場合と先頭が1の場合と末尾が0の場合だけである。 よって、その数を累積和で求めておけばO(N)でこの問題を解くことができる。

ソースコード

signed main() {
    int A, B, C;
    cin >> A >> B >> C;

    string T;
    int N;
    cin >> T;
    N = T.size();

    int cum_sum[200001] = {};
    
    Rep(i, N-1) {
        cum_sum[i+1] = cum_sum[i];
        if ( T[i] != T[i+1] ) cum_sum[i+1]++;
    }

    int ans = INF;
    Rep(i, N+1) {
        int a = i, b = N-i;
        int x = 0, y = 0;
        if ( i ) x = cum_sum[i-1];
        if ( i < N ) y = cum_sum[N-1] - cum_sum[i];
        if ( i && T[0] == '1' ) x++;
        if ( i < N && T[N-1] == '0' ) y++;
        int c = max(x, y);
        ans = min(ans, A*a+B*b+C*c);
    }

    cout << ans << endl;
    
    return 0;
}

感想

操作3の操作回数を求める方法が分からなかったのがだめだった。
回数をO(1)で求められないかをまず考察するようにしたい。
累積和のインデックスとfor文内の操作のインデックスをうまいこと調整するのが少しめんどくさかった。

ARC066 E - Addition and Subtraction Hard -

問題

E - Addition and Subtraction Hard

解説

公式
https://atcoder.jp/img/arc066/editorial.pdf
kmjpさん
AtCoder ARC #066 : E - Addition and Subtraction Hard - kmjp's blog

考察

どうすれば式の値を最大化できるかを考える。

-の後に開き括弧を挿入して、引く値をできるだけ小さくできたら良さそう。
また、+の後に開き括弧を挿入しても意味はない。(式の値を増やすことはできない)

上記の考察から-の後に括弧を挿入することだけ考えればいい。 また全ての-の後に開き括弧を挿入してもいいことも分かる。(開き括弧を挿入する必要がなかった場合でもその後の数の直後で閉じればいいため)

すると
dp[i][j] = i 項目の直後で、j 個括弧が開いている時の、そこまでの式の値の最大値 というような DP を思いつく。

しかし、これは O(N2) なのでまずい。
iは減らせなそうなので、jをどうにか減らしたい。

考察をすると、開き括弧を挿入した後の式の値は符号が反転すると考えられることが分かる。
- A - B - C - Dで表される式があったとして、
- A -(B - C - D)  …(i)
- A -(B -(C -(D))) …(ii)
の2つの括弧挿入後の式を考える。
Dの部分に着目すると
(i)のDはB前の-(によって式の値の符号が反転している。
(ii)のDはD前の-(によって反転、C前の-(によって反転、B前の-(によって反転、計3回反転している。
符号が1回反転しているのと3回反転しているのは実質やっていることは変わらない(式の値は変わらない)ので同じものと考えていよいことが分かる。

上記の考察から括弧を開くのは高々2回でよいことが分かる。(偶奇だけ考えればよいため)

よって j の範囲は 0∼2 だけを考えればよくなり、この DP が O(N) でできることが分かった。

ソースコード

signed main() {
    int N;
    int A[100001];
    char op[100001];
    int dp[100001][3];   
 
    fill_n(*dp, 100001*3, -INF);
    
    cin >> N;
    cin >> A[0];
    dp[0][0] = A[0];
 
    for ( int i = 1; i < N; i++ ) cin >> op[i] >> A[i];
    
    for ( int i = 1; i < N; i++ ) {
        if ( op[i] == '+' ) {
            dp[i][0] = dp[i-1][0]+A[i];
            dp[i][1] = dp[i-1][1]-A[i];
            dp[i][2] = dp[i-1][2]+A[i];
        } else {
            //open
            dp[i][1] = max(dp[i-1][0], dp[i-1][2])-A[i];
            dp[i][0] = dp[i][2] = dp[i-1][1]+A[i];          
        }
 
        //close
        dp[i][1] = max(dp[i][1], dp[i][2]);
        dp[i][0] = max(dp[i][0], dp[i][1]);
    }
 
    cout << *max_element(dp[N-1], dp[N-1]+3) << endl;
 
    return 0;
}

感想

コードはとても短いけど、解法を理解するのに結構時間がかかった。

Codeforces Round #456 (Div. 2) D - Fishes -

問題文

n × m マスのグリッドにk匹の魚がいる。(それぞれのセルには魚は高々一匹しかいない)
r × r の正方形の網がある。その網をグリッド上に設置したとき、その領域に含まれる魚を得られる。
その網をグリッド上の考えられるすべての場所に設置するとき、得られる魚の平均の数を最大化せよ。

制約
(1 ≤ n, m ≤ 10^5, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 10^5)

http://codeforces.com/contest/912/problem/D

解法

まず愚直に考えると、全ての座標に魚を置いてみて、その座標を含む領域の数が大きいやつからとってくみたいなことを思いつく。
しかし n m の制約からそれは無理なことが分かる。

そこで含まれる領域の数が多い座標の特徴はなにか考える。少し考えると真ん中に行けばいくほど良いことが分かる。(直感的にも分かる)

考察から、グリッド上の真ん中あたりから座標を決めていくことにする。やり方はいろいろあると思う。
公式の解説では、y座標は m / 2 と m / 2 + 1 、x座標は 1 ~ n に決めて、その座標を含まれる領域の数(グリッドと網の領域のサイズと魚の座標から計算できる)と一緒に multiset に突っ込んで、いいやつから取っていってそれに近い座標もどんどん突っ込んでくみたいなやり方をしていた。(公式解説を見た方が正確)

公式解説
http://codeforces.com/blog/entry/56920

ソースコード

const int N = 100005, M = 350;
int n, m, r, k;

struct Cell {
    int x, y, d, val;
    Cell(int x, int y, int d) : x(x), y(y), d(d) {
        val = (min(m+1, y+r) - max(y, r)) * 1LL * (min(n+1, x+r) - max(x, r));
    }

    bool operator < (const Cell &other) const {
        return val > other.val;
    }
};

multiset<Cell> ms;

double get() {
    for ( int i = 1; i <= n; i++ ) {
        int j = m / 2;
        ms.insert({i, j, 0});
        ms.insert({i, j+1, 1});
    }

    int total = 0;
    Rep(i, k) {
        auto it = *ms.begin();
        total += it.val;

        ms.erase(ms.begin());

        if ( it.d == 1 && it.y < m ) {
            ms.insert({it.x, it.y+1, 1});
        } else if ( it.d == 0 && it.y > 1 ) {
            ms.insert({it.x, it.y-1, 0});
        }
    }

    return (double)total / ((n-r+1) * 1LL * (m-r+1));
}

signed main() {
    cin >> n >> m >> r >> k;
    if ( n > m ) swap(n, m);

    if ( n == 1 && m == 1 ) {
        printf("%.10f\n", 1.0);
    } else {
        printf("%.10f\n", get());
    }

    return 0;
}

反省とか

自分で解いたというより解説を理解しただけ。
コンテスト中はCを読むのがめんどくさすぎてほどんど考えず離脱してしまった。

AOJ 1065 - The House of Huge Family -

問題文

重み付き有向グラフが与えられる。
頂点を2つのグループに分け、お互いの頂点間を移動できないようにしたい。
そのために、辺を取り除いていくことができる。
取り除いた辺の重みの最小値は?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1065

解法

有向グラフの任意の2頂点間に共通して到達できる/到達されることができる頂点があることは、その有向グラフを無向グラフして考えた時グラフが連結であることの必要十分条件である(ほんとか?)。

つまり与えられた有向グラフを無向グラフとしたとき、そのグラフが非連結になるように辺をとったときの最小値を求めればいい。
また、頂点数Nの無向グラフが連結であるために必要な辺の最小はN-1であることと、この問題では辺は高々N本しか与えられないことから削除する辺は2本以下になることが分かる。
あと、負の重みを持つ辺は最初から削除しておいた方がお得なのは自明なので、その総和をとっておいて後から足すことにする。

削除する必要のある辺が0、1、2それぞれの場合について考える。
0 : 与えられたグラフが非連結な場合のみなので、最初にグラフの連結判定をして確かめる。
1 : 辺が橋(取り除くとグラフが非連結になる辺)の場合である。lowlinkを用いた橋の列挙を行う。
2 : どの2本の辺を取り除いてもグラフは非連結になる。

0の場合は例外として、 1と2のminをとった値に負の辺の重みを足したものが最終的な答えとなる。

ソースコード

vector<Pii> G[101];
int min_bridge = INF;
int ord[101], low[101];
bool vis[101];

void dfs(int v, int p, int &k) {
  vis[v] = true;

  ord[v] = k++;
  low[v] = ord[v];

  Rep(i, G[v].size()) {
    if ( !vis[G[v][i].fr] ) {
      dfs(G[v][i].fr, v, k);
      low[v] = min(low[v], low[G[v][i].fr]);      
      if ( ord[v] < low[G[v][i].fr] ) min_bridge = min(min_bridge, G[v][i].sc);
    } else if ( G[v][i].fr != p ) {
      low[v] = min(low[v], ord[G[v][i].fr]);
    }        
  }
  
}

void dfs2(int v) {
  if ( vis[v] ) return;
  vis[v] = true;
  Rep(i, G[v].size()) {
    dfs2(G[v][i].fr);
  }  
}

signed main() {
  int n, m;
  while ( cin >> n >> m, n | m ) {
    int minus_cost = 0;
    min_bridge = INF;
    int min_1 = INF, min_2 = INF;
    Rep(i, 101) {
      G[i].clear();
      vis[i] = false;
    }
    
    Rep(i, m) {
      int a, b, c;
      cin >> a >> b >> c;
      if ( c <= 0 ) minus_cost += c;
      else {
    if ( min_1 > c ) min_2 = min_1, min_1 = c;
    else if ( min_2 > c ) min_2 = c;
    G[a].pb(Pii(b, c));
    G[b].pb(Pii(a, c));
      }
    }

    dfs2(0);
    bool is_connected = true;
    Rep(i, n) {
      if ( !vis[i] ) {
    is_connected = false;
    break;
      }
    }

    if ( !is_connected ) {
      cout << minus_cost << endl;
      continue;
    }
    
    Rep(i, n) vis[i] = false;
    int k = 0;
    Rep(i, n) {
      if ( !vis[i] ) dfs(i, -1, k);
    }

    if ( min_bridge == INF ) cout << minus_cost << endl;
    else cout << min(min_bridge, min_1+min_2) + minus_cost << endl;
  }

  return 0;
}

参考
橋の列挙 http://kagamiz.hatenablog.com/entry/2013/10/05/005213

反省とか

最初なにも考えずに全点間の最小カットを求めて…みたいなことをしていたが明らかにTLE。