読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

Codeforces Round #340 (Div. 2)

Hack回。A, B, D を解いて3完。Cはコーナーケースに負けて落ちたつらい。 直前のドワンゴのコンテストと同じ A, B, Dだし暗示されていたのでは・・・

1587 -> 1657。

A. Elephant

問題概要

数直線上の点 x(x > 0) に位置する象が, 点 0 に位置する友達の家を訪れる。
象は1ステップに 1, 2, 3, 4, 5 のどれかの距離を選んで移動できる。
象が友達の家に訪れるための最短ステップ数を求めよ。

解法

なるべくたくさん動いて, 友達の家に近づけばよい。
なので, なるべくたくさん引いた。(これは頭が悪くて、(N / 5 + (N % 5 != 0)) がシンプル。)

ソース

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int X, ret = 0;
  cin >> X;
  while(X - 5 >= 0) X -= 5, ++ret;
  while(X - 4 >= 0) X -= 4, ++ret;
  while(X - 3 >= 0) X -= 3, ++ret;
  while(X - 2 >= 0) X -= 2, ++ret;
  while(X - 1 >= 0) X -= 1, ++ret;
  cout << ret << endl;
}

B. Chocolate

問題概要

N(1 ≤ N ≤ 100) 個のピースで構成されるチョコレートバーがある。
このバーをちょうど 1 つのナッツが含まれる複数の断片に分割するとき, 分割の仕方の方法の数を  {10^9 + 7} で割ったあまりで求めよ。

解法

考えるのが面倒だったのでDPした。

  • dp[i]: i番目までのチョコの組み合わせの個数

dp は、区間にちょうど ナッツ が 1 つのみのところに今のコストを加えれば良い。 O(N^3)。

ソース

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

int main()
{
  int N, x[100];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> x[i];
  }

  int64 dp[101] = {};
  dp[0] = 1;
  for(int i = 0; i < N; i++) {
    for(int j = i; j < N; j++) {
      int isOne = 0;
      for(int k = i; k <= j; ++k) isOne += x[k];
      if(isOne == 1) dp[j + 1] += dp[i];
    }
  }
  cout << dp[N] << endl;
}

C. Watering Flowers

問題概要

2次元座標上に 2 つのスプリンクラーと N(1 ≤ N ≤ 2000) 個の花がある。 両スプリンクラーは, それぞれを中心とした半径 r1, r2(0 ≤ r1,r2) の円内に水をまくことができる。
それぞれの花が, 少なくとも一方のスプリンクラーの範囲に入るようにするとき,  {r1^2+r2^2} の最小値を求めよ。

解法

落ちたつらい。
噴水 1 の範囲に入れる、一番外側となる花を決めてそれを半径として総当たり。噴水 1 の範囲外の花を噴水 2 に入れるとして、最大値を求めれば良い。
噴水 1 の半径が 0 になることを考慮してなかったので頭悪い。

ソース

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

int64 get(Pi& a, Pi& b)
{
  return((a.first - b.first) * (a.first - b.first) +
         (a.second - b.second) * (a.second - b.second));
}

int main()
{
  int64 n;
  Pi a, b;
  Pi p[2000];

  cin >> n >> a.first >> a.second >> b.first >> b.second;
  for(int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
  }

  int64 ret = 1LL << 60;
  for(int k = 0; k < 2; k++) {
    for(int i = 0; i < n; i++) {
      int64 dist = get(a, p[i]), res = 0;
      for(int j = 0; j < n; j++) {
        if(get(a, p[j]) > dist) res = max(res, get(b, p[j]));
      }
      ret = min(ret, dist + res);
    }
    swap(a, b);
  }
  cout << ret << endl;
}

D. Polyline

問題概要

二次元座標上で異なる 3 点が与えられる。 x軸かy軸に平行な線分を連結してできる連続直線を作成し, 3 点を通るようにしたい。 必要な線分の数の最小値を求めよ。

解法

怪しい問題。無駄にコードが長くなってしまった。

3点がY軸あるいはX軸に平行ならば直線なので答えは1。
2点がY軸あるいはX軸に平行ならば、これは面倒なので後述。
平行なものがないなら、答えは3。

2点の場合。縦線の時を考える(横線も同じことがいえる)。縦線の端点の上下にもう一点があれば(x座標は縦線と異なってもよい)、伸ばして直角に線を引けるので答えは2。
それ以外は3。

ソース

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

struct Point {
  int64 x, y;
};

int main()
{
  Point p[3];
  vector< int64 > xx, yy;
  for(int i = 0; i < 3; i++) {
    cin >> p[i].x >> p[i].y;
    xx.push_back(p[i].x);
    yy.push_back(p[i].y);
  }
  sort(xx.begin(), xx.end());
  xx.erase(unique(xx.begin(), xx.end()), xx.end());
  sort(yy.begin(), yy.end());
  yy.erase(unique(yy.begin(), yy.end()), yy.end());
  
  if(xx.size() == 1 || yy.size() == 1) {
    cout << 1 << endl;
  } else if(xx.size() == 2) {
    for(int i = 0; i < 3; i++) {
      for(int j = i + 1; j < 3; j++) {
        if(p[i].x == p[j].x) {
          if(p[i].y > p[j].y) swap(p[i].y, p[j].y);
          int none;
          if(i == 0 && j == 1) none = 2;
          else if(i == 0 && j == 2) none = 1;
          else if(i == 1 && j == 2) none = 0;

          if(p[i].y < p[none].y && p[none].y < p[j].y) {
            cout << 3 << endl; 
          } else {
            cout << 2 << endl;
          }
          exit(0);
        } 
      }
    }
  } else if(yy.size() == 2) {
    for(int i = 0; i < 3; i++) {
      for(int j = i + 1; j < 3; j++) {
        if(p[i].y == p[j].y) {
          if(p[i].x > p[j].x) swap(p[i].x, p[j].x);
          int none;
          if(i == 0 && j == 1) none = 2;
          else if(i == 0 && j == 2) none = 1;
          else if(i == 1 && j == 2) none = 0;

          if(p[i].x < p[none].x && p[none].x < p[j].x) {
            cout << 3 << endl; 
          } else {
            cout << 2 << endl;
          }
          exit(0);
        } 
      }
    }
  } else {
    cout << 3 << endl;
  }
}