ARC#008

今回のAtCoderのwriterやってました。

A
まず10個ずつ纏めて全部パックで買う。そして、残りのたこ焼きを1パックで買った場合とバラで買った場合でかかる費用の小さい方を選ぶ。たこ焼きn個のときの最小費用は、100[n/10]+min{15(n%10),100}円となる。

#include <stdio.h>

int main(void)
{
    int price[10]={0, 15, 30, 45, 60, 75, 90, 100, 100, 100};
    int n, pack, sole;
    
    scanf ("%d", &n);
    
    pack = n / 10;
    sole = n % 10;
    
    printf("%d\n", pack * 100 + price[sole]);
    
    return 0;
}

C++

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int n, pack, sole, price;
    
    cin >> n;
    
    pack = n / 10;
    sole = n % 10;
    price = pack * 100 + min(sole * 15, 100);
    
    cout << price << endl;
    
    return 0;
}

B
各文字について、その文字を揃えるのに何袋必要になるかを考え、その最大値を答えとする。零除算に注意。
もとは英字ビスケットでケーキの飾り付けをする問題。chokduaiさんは誕生日ケーキにたこ焼き乗せてソースで「24歳」とか書いたりしてそうだなあ。

C言語

#include <stdio.h>

int main(void)
{
    int i;
    int n, m;
    int ans = 0, pack;
    int nameNum[32], cookieNum[32];
    char name[64], cookie[64];
    
    scanf ("%d%d", &n, &m);
    scanf ("%s", name);
    scanf ("%s", cookie);
    
    for (i = 0; i < 32; i++) {
        nameNum[i] = 0;
        cookieNum[i] = 0;
    }
    for (i = 0; i < n; i++) {
        nameNum[name[i] - 'A']++;
    }
    for (i = 0; i < m; i++) {
        cookieNum[cookie[i] - 'A']++;
    }
    
    for (i = 0; i < 26; i++) {
        if (cookieNum[i] == 0) {
            if (nameNum[i] > 0) {
                ans = 999;
            }
        }
        else {
            pack = (nameNum[i] + cookieNum[i] - 1) / cookieNum[i];
            if (ans < pack) {
                ans = pack;
            }
        }
    }
    
    if (ans == 999) ans = -1;
    printf("%d\n", ans);
    
    return 0;
}

C++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
    int n, m;
    int ans = 0;
    int nameNum[32], cookieNum[32];
    string name, cookie;
    
    cin >> n >> m;
    cin >> name;
    cin >> cookie;
    
    for (int i = 0; i < 32; i++) nameNum[i] = cookieNum[i] = 0;
    for (int i = 0; i < n; i++) nameNum[name[i] - 'A']++;
    for (int i = 0; i < m; i++) cookieNum[cookie[i] - 'A']++;
    
    for (int i = 0; i < 26; i++) {
        if (cookieNum[i] == 0) {
            if (nameNum[i] > 0)
                ans = 999;
        }
        else {
            ans = max (ans, (nameNum[i] + cookieNum[i] - 1) / cookieNum[i]);
        }
    }
    
    if (ans == 999) ans = -1;
    cout << ans << endl;
    
    return 0;
}

ダイクストラで1番の人から各人に何秒でたこ焼きを届けられるかを計算して、時間のかかる人から順にたこ焼きを届ける。O(V^2)のダイクストラなので、慣れてなくても比較的簡単に組める。自分にたこ焼きを投げないように注意。たこ焼き投げたい。

#include <iostream>
#include <cmath>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;

double x[1024], y[1024], p[1024], r[1024];
double mat[1024][1024], t[1024];
bool flag[1024];

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main(void)
{
    int n;
    double ans = 0;
    
    cin >> n;
    
    REP(i,n) cin >> x[i] >> y[i] >> p[i] >> r[i];
    REP(i,n) REP(j,n) mat[i][j] = dist(x[i], y[i], x[j], y[j]) / min(p[i], r[j]);
    REP(i,n) t[i] = 99999999, flag[i] = true;
    
    t[0] = 0;
    
    REP(i,n) {
        double minTime = 99999999;
        int num;
        REP(j,n) if (flag[j] && t[j] < minTime) {
            minTime = t[j];
            num = j;
        }
        REP(j,n) t[j] = min (t[j], t[num] + mat[num][j]);
        flag[num] = false;
    }
    
    sort (t, t + n);
    FOR(i,1,n) ans = max (ans, t[i] + n - i - 1);
    
    cout.precision(20);
    cout << ans << endl;
    
    return 0;
}

D
SegmentTreeを使うシンプルな問題。セグ木周りには何のひねりも無いので割と簡単。平方分割を使っても解ける。タコヤキオイシクナールなんて~~胡散臭いｷﾁｶﾞｲﾏｼーﾝ~~を一兆個も買うなんて、高橋社長はどうかしてるZE☆

SegmentTree

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;

typedef pair<long long,int> P;

long long p[128000];
double a[128000], b[128000];
P v[128000];

const int STsize = 1 << 18;

class SegTree {
public:
    int n;
    double datA[STsize], datB[STsize];
    SegTree(void) { n = STsize / 2; REP(i, STsize) datA[i]=1,datB[i]=0; }
    void update(int pos, double a, double b) {
        datA[pos] = a; datB[pos] = b;
        while (pos < 2*n-1) {
            int lpos = pos/2*2, rpos = pos/2*2+1;
            datA[pos/2+n] = datA[lpos] * datA[rpos];
            datB[pos/2+n] = datA[rpos] * datB[lpos] + datB[rpos];
            pos = pos/2 + n;
        }
    }
    double query(void) { return datA[2*n-2] + datB[2*n-2]; }
};

int main(void)
{
    long long n;
    int m;
    double ansMin = 1, ansMax = 1;
    
    scanf ("%lld%d", &n, &m);
    REP(i,m) {
        scanf("%lld%lf%lf", &p[i], &a[i], &b[i]);
        v[i] = make_pair(p[i], i);
    }
    sort(v, v + m);
    
    REP(i,m) {
        if (i == 0) p[v[0].second] = 0;
        else if (v[i-1].first == v[i].first) p[v[i].second] = p[v[i-1].second];
        else p[v[i].second] = p[v[i-1].second] + 1;
    }
    
    SegTree seg;
    REP(i,m){
        seg.update(p[i], a[i], b[i]);
        double ret = seg.query();
        ansMin = min (ansMin, ret);
        ansMax = max (ansMax, ret);
    }
    
    printf("%.14lf\n%.14lf\n", ansMin, ansMax);
    
    return 0;
}

平方分割

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;

typedef pair<long long,int> P;

long long p[128000];
double a[128000], b[128000];
P v[128000];

class SQRT {
public:
    int n;
    double datA[102400], datB[102400];
    double datC[320], datD[320];
    SQRT(int m) {
        n = m;
        REP(i,n*n) datA[i]=1,datB[i]=0;
        REP(i,n) datC[i]=1,datD[i]=0;
    }
    void update(int pos, double a, double b) {
        datA[pos] = a; datB[pos] = b;
        datC[pos/n] = 1; datD[pos/n] = 0;
        REP(i,n) {
            datC[pos/n] *= datA[pos/n*n+i];
            datD[pos/n] = datD[pos/n] * datA[pos/n*n+i] + datB[pos/n*n+i];
        }
    }
    double query(void) { 
        double ans = 1;
        REP(i,n) ans = ans * datC[i] + datD[i];
        return ans;
    }
};

int main(void)
{
    long long n;
    int m;
    double ansMin = 1, ansMax = 1;
    
    scanf ("%lld%d", &n, &m);
    REP(i,m) {
        scanf("%lld%lf%lf", &p[i], &a[i], &b[i]);
        v[i] = make_pair(p[i], i);
    }
    sort(v, v + m);
    
    REP(i,m) {
        if (i == 0) p[v[0].second] = 0;
        else if (v[i-1].first == v[i].first) p[v[i].second] = p[v[i-1].second];
        else p[v[i].second] = p[v[i-1].second] + 1;
    }
    
    SQRT sq(320);
    REP(i,m){
        sq.update(p[i], a[i], b[i]);
        double ret = sq.query();
        ansMin = min (ansMin, ret);
        ansMax = max (ansMax, ret);
    }
    
    printf("%.14lf\n%.14lf\n", ansMin, ansMax);
    
    return 0;
}

50点解法

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;

double a[1024], b[1024];

int main(void)
{
    int n, m;
    double ansMin = 1, ansMax = 1;
    cin >> n >> m;
    REP(i,1024) a[i] = 1, b[i] = 0;
    REP(i,m) {
        int pos;
        double ans = 1;
        cin >> pos;
        cin >> a[pos] >> b[pos];
        REP(j,1024) ans = ans * a[j] + b[j];
        ansMin = min (ansMin, ans);
        ansMax = max (ansMax, ans);
    }
    
    cout << ansMin << endl << ansMax << endl;
    
    return 0;
}

(o_o)

ブログ。