roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest 019 A: Best Body, B: Bumble Bee, C: Blue Bard, D: Big Bang

ABC022に参加。久しぶりに全完できたのでうれしい。

問題はこちら

A: Best Body

高橋君は体重がS以上T以下のときをベストボディだと考えている。高橋君のはじめの体重Wと1日ごとの体重の変化の記録Aを与えられるので、高橋君がベストボディだった日が何日あるかを答えよ。

解法

体重を日ごとに更新していき、ベストボディの条件を満たしているか確認する。初日についてもベストボディかどうかの判定をするのを忘れない。

N, S, T = map(int,raw_input().split())
A = [input() for i in xrange(N)]
W = 0
ans = 0
for a in A:
    W += a
    if S <= W <= T:
        ans += 1
print ans

B: Bumble Bee

ハチの高橋君は蜜を集めるためにいくつかの花を訪れた。1度訪れた花と同じ種類の花を訪れると、その花を受粉させられるとする。訪れた花の種類を訪れた順に与えられる。訪れた花はすべて異なる花としたとき、ハチの高橋君が受粉させた花が何本あるかを答えよ。

解法

ある花の種類を訪れた回数 - 1 を足し合わせていけば答えとなる。

from collections import defaultdict
N = int(raw_input())
hist = defaultdict(int)
for loop in xrange(N):
    a = int(raw_input())
    hist[a] += 1
ans = 0
for v in hist.values():
    ans += v - 1
print ans

C: Blue Bard

N(≦ 300)個の家があり、家の間を結ぶ道がM本ある。i番目の道は家uiと家viを結んでおり、その長さはliとする。

家1から出発して、同じ道を2度通らないで再び家1に戻ってくることを考える。そのような道の通り方があるかどうかを求めよ。あるなら、そのとき通る距離の総和の最小値を答えよ 。

解法

まず家1が存在しないとして、全家間の距離をワーシャルフロイド法で求める。

そこから家1とつながっている異なる2つの家a、bについて、 (家1と家aまでの距離) + (家aと家bの距離) + (家bと家1までの距離) について最小値を取っていけば、答えを得ることができる。

計算量はO(N3)。pythonだとおそらく間に合わないのでC++で解答した。

#include <iostream>
#include <vector>
#include <utility>
#define REP(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) REP(i, 0, a)
using namespace std;
const long long inf = 1000000000L;
 
int N, M;
long long G[301][301];
vector<pair<int, int>> start;
 
int main(void){
    rep(i, 301) rep(j, 301) G[i][j] = inf;
    cin >> N >> M;
    rep(loop, M) {
        int u, v, l;
        cin >> u >> v >> l;
        u--; v--;
        if (min(u, v) == 0) {
            start.push_back(make_pair(max(u, v), l));
            continue;
        }
        G[u][v] = G[v][u] = l;
    }
    rep(k, N) rep(i, N) rep(j, N) G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
    long long ans = inf;
    rep(i, start.size()) {
        int v1 = start[i].first, l1 = start[i].second;
        REP(j, i + 1, start.size()) {
            int v2 = start[j].first, l2 = start[j].second;
            ans = min(ans, l1 + G[v1][v2] + l2);
        }
    }
    cout << (ans < inf ? ans : -1) << endl;
    return 0;
}

D: Big Bang

xy平面上にあるN(≦105)個の点を2組(AとB)与えられる(座標値は整数)。Aの座標の組に以下の操作を行うとBの座標の組と一致する。

  1. 同じ向きに同じ距離だけ平行移動する。
  2. 原点を中心に同じ角度だけ回転する。
  3. 原点を中心に P 倍 (1≦P) に相似拡大する。つまり点 (x,y) を点 (xP,yP) に移すという操作をすべての点に実行する。

Pの値がいくらであるかを答えよ。なお2つの必ず座標の組は必ず一致させられる。

解法

上の操作を行っても重心からの距離の大きさの順番は変わらないことに注目する。

つまり、Aの中で重心からもっとも遠い点は、Bの中で重心からもっとも遠い点である。したがってAの重心から最も遠い点までの距離 maxDistA と、Bの重心から最も遠い点までの距離 maxDistB を求めれば、答えは maxDistB / maxDistA となる。

下のコードでは誤差がどうなるかわからなかったので平方根を取るのは最後にしている。

import math
def dist(x, y):
    return (x - gx) ** 2 + (y - gy) ** 2
    
N = int(raw_input())

A = [map(float, raw_input().split()) for i in xrange(N)]
gx = sum(x for x, y in A) / N
gy = sum(y for x, y in A) / N
maxDistA = max(dist(x, y) for x, y in A)

B = [map(float, raw_input().split()) for i in xrange(N)]
gx = sum(x for x, y in B) / N
gy = sum(y for x, y in B) / N
maxDistB = max(dist(x, y) for x, y in B)

print "%.10f" % (math.sqrt(maxDistB / maxDistA))

まとめ

いつものABCよりも難易度が高かった気がする。Dは簡単な解法があって助かった。

広告を非表示にする