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 つのナッツが含まれる複数の断片に分割するとき, 分割の仕方の方法の数を で割ったあまりで求めよ。
解法
考えるのが面倒だったので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) の円内に水をまくことができる。
それぞれの花が, 少なくとも一方のスプリンクラーの範囲に入るようにするとき, の最小値を求めよ。
解法
落ちたつらい。
噴水 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; } }
