Codeforces Round #349 (Div. 2)

1763 -> 1691(-72).
A, B, C, D を出して C, Dは落ちた.
なんか Reading Hard.

A. Pouring Rain

問題概要

円の直径 cm の円柱状のカップがある.
カップの中には, 底から cm 水が入っている.
水を毎秒 ml 飲む.
雨が降っているので毎秒 cm の水がカップに入る.
カップを空にできれば, YES とともにその時間を, できなければ -1 を出力せよ.

解法

[ml] 単位に合わせて問題を整理すると良さそう.

• 最初, ml ある.
• 毎秒, ml 減少する.
• 毎秒, ml 増加する.

増加量が減少量以上のときは, 自明に空にできない.
空にできるときも自明で, 最初の量を毎秒の減少量で割ってあげればよい.
よって, 秒となる.

ソース

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const double EPS = 1e-8;
int main()
{
  double D; 
  double H; // H * π * D^2 / 4 ml
  double V; // - V ml / s
  double E; // + E * π * D^2 / 4 ml / s
  
  cin >> D >> H >> V >> E;

  double Dec = V - E * PI * D * D / 4;
  
  if(Dec <= EPS) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
    cout << fixed << setprecision(10) << H * PI * D * D / 4 / Dec << endl;
  }
}

B. Coat of Anticubism

問題概要

棒が 本あり, それぞれの長さは である.
ただし, それらをつなげて凸多角形を作ることはできない.
1 本棒を加えるとき, 凸多角形を作るための必要な最短の長さを求めよ.

解法

頂点を増やすと作りにくくなるので, 作るものは三角形と仮定する.
1 辺を の最大値としたとき, 三角形を作るためには他の 2 辺は, 合わせて (最大値 + 1) の長さが必要(例えば 最大値未満の長さだとつなげようとしても届かない).
よって, 足りない長さを求めればよくて, が答えとなる.

ソース

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, l[100000];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) scanf("%d", &l[i]);
  cout << 2 * *max_element(l, l + N) - accumulate(l, l + N, 0) + 1 << endl;
}

C. Reberland Linguistics

問題概要

5 文字以上の文字列に, 2 文字か 3 文字からなる文字列をいくつか繋げて(ただし, 同じ文字列を2回連続で繋げることは出来ない) 文字列 にしたい.
繋げる文字列として考えられるものを辞書順で出力せよ.

解法

DP. 1個前に加えた文字列を保存しておいて, 次に加える文字列が追加できるかどうか見ればよい.

ソース

本番は dpの更新が '=' だったけど, 自明に '|=' じゃないとダメだった.

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

int main()
{
  string S;
  cin >> S;
  
  S = S.substr(5);
  reverse(S.begin(), S.end());
  bool dp[10002][4] = {{}};
  
  for(int i = 0; i < S.size(); i++) {
    if(dp[i][2]) {
      int s = i + 2;
      dp[s][2] |= s + 1 < S.size() && (S[i] != S[s] || S[i + 1] != S[s + 1]);
      dp[s][3] |= s + 2 < S.size();
    }
    if(dp[i][3]) {
      int s = i + 3;
      dp[s][2] |= s + 1 < S.size();
      dp[s][3] |= s + 2 < S.size() && (S[i] != S[s] || S[i + 1] != S[s + 1] || S[i + 2] != S[s + 2]);
    }
  }

  set< string > ss;
  for(int i = 0; i < S.size(); i++) {
    if(dp[i][2]) {
      string s = "";
      s += S[i + 1];
      s += S[i];
      ss.insert(s);
    }
    if(dp[i][3]) {
      string s = "";
      s += S[i + 2];
      s += S[i + 1];
      s += S[i];
      ss.insert(s);
    }
  }
  cout << ss.size() << endl;
  for(const string& s : ss) cout << s << endl;
}

D. World Tour

問題概要

頂点数 , 辺の数 の有向グラフがある. 各辺の重みはすべて 1 である.
4 個の異なる頂点を選び, 順に最短経路を移動する(同じ道を何度通っても良い). このときの和を とする.
が最大となるような頂点の選び方を求めよ.

解法

まず, 全点対間最短路が欲しそうで, これは BFS で .

選ぶ頂点の番号を順に, とおく.
の組を全通り試すとする.
すると, は, から最も遠い頂点となるが, 異なる頂点を選ぶという制約より最も遠い頂点が ではいけないことが分かる. だから, 最も遠い頂点の候補を遠い順に 3 個用意するとよい.
また, は, への経路のうち最も遠い頂点となり, これは逆辺を張れば, と同じ.

の全通りの組で の候補がそれぞれ高々 3 通りなので, 計算量は となって間に合う.

ソース

冷静になれば当たり前だよね....

#include <bits/stdc++.h>
using namespace std;
typedef pair< int, int > Pi;

vector< int > graph[3000], rgraph[3000];
int g[3000][3000];
set< Pi > qq[2][3000];
int main()
{
  int N, M;
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    graph[u].push_back(v);
    rgraph[v].push_back(u);
  }

  for(int l = 0; l < 2; l++, swap(graph, rgraph)) {
    memset(g, -1, sizeof(g));
    for(int i = 0; i < N; i++) {
      queue< int > que;
      que.push(i);
      g[i][i] = 0;
      while(!que.empty()) {
        int p = que.front(); que.pop();
        for(int to : graph[p]) {
          if(g[i][to] == -1) {
            que.push(to);
            g[i][to] = g[i][p] + 1;
            qq[l][i].insert({g[i][to], to});
            while(qq[l][i].size() > 3) qq[l][i].erase(qq[l][i].begin());
          }
        }
      }
    }
  }

  int ret = -114;
  int aa, bb, cc, dd;
  
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(i == j || g[j][i] == -1) continue;
      for(const Pi& a : qq[1][i]) {
        if(i == a.second || j == a.second) continue;
        for(const Pi& b : qq[0][j]) {
          if(i == b.second || j == b.second || a.second == b.second) continue;
          if(ret < g[j][i] + a.first + b.first) {
            ret = g[j][i] + a.first + b.first;
            aa = a.second, bb = i, cc = j, dd = b.second;
          }
        }
      }
    }
  }
  cout << aa + 1 << " " << bb + 1 << " " << cc + 1 << " " << dd + 1 << endl;
}