TakefumiYamamura commented 8 years ago

C - おいしいたこ焼きの売り方

時間制限 : 2sec / メモリ制限 : 64MB

問題文

高橋君は、たこ焼きをどの順番で売るか悩んでいました。というのも、作り置きされたたこ焼きは美味しくないとわかっているので、高橋君はそのようなたこ焼きを売りたくないのですが、できたてばかり売ってしまうと売れるたこ焼きの数が減ってしまいます。

また、お客さんを待たせてばかりだと、次第にお客さんが離れてしまうだろうと高橋君は考えています。そこで、彼は T 秒以内に作成されたたこ焼きを売り続けることで、お客さんを捌ききれるかどうかを調べることにしました。たこ焼きは A1、A2、…、AN 秒後に焼きあがります。お客さんは B1、B2、…、BM 秒後にやってきます。 1 人のお客さんに対して、たこ焼きを 1 つ売るとします。すべてのお客さんにたこ焼きを売れるならyes、売れないならnoを出力して下さい。

Note

This problem is a typical kind of an area scheduling. and input is already sorted so just compared front of two array. Therefore order is O(n).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define MAX_N 51
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    int t, n, m;
    queue<int> a;
    queue<int> b;

    cin >> t;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int tmp;
        cin >> tmp;
        a.push(tmp);
    }
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        int tmp;
        cin >> tmp;
        b.push(tmp);
    }

    while(!a.empty() && !b.empty()){
        if(a.front() <= b.front() && b.front() <= a.front() + t){
            a.pop();
            b.pop();
        }else{
            a.pop();
        }
    }

    if(b.empty()){
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }

}

TakefumiYamamura commented 8 years ago

D - おいしいたこ焼きの焼き方

時間制限 : 5sec / メモリ制限 : 256MB

問題文

高橋君のたこ焼き屋で使っているたこ焼き器は焼く場所によって美味しさの変わるクセの強いたこ焼き器です。また、店員の力量によって一度に焼けるたこ焼きの数が違います。高橋君はそれぞれの店員ができるだけ美味しくたこ焼きを焼けるようにしようと思いました。

たこ焼き器はN×Nの正方形をしています。それぞれの場所ごとにたこ焼きの美味しさDijが決まっています。それぞれの店員は一度に焼けるたこ焼きの上限Pkが決まっています。また、一度に焼くたこ焼きは必ずたこ焼き器の長方形の部分になっていて、その中の全てを使わなければなりません。それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を求めて下さい。ただし、店員が焼き始める時はたこ焼き器が完全に空いていてどの場所でも使えるとします。

note

二次元の累積和を求める

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define MAX_N 51
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int q;
int P[52*52];
int dp[52][52];

int cal(int x, int y, int lx, int ly){
    // cout << " "<<dp[lx][ly] << " "<<dp[lx][y] << " "<<dp[x][ly] << " "<<dp[x][y] << " ";
    return dp[lx][ly] - dp[lx][y] - dp[x][ly] + dp[x][y];
}

int solve(int size){
    int ans = 0;
    for (int x = 1; x <= size; ++x)
    {
        if(size % x != 0) continue;
        int y = size / x;
        for (int s = 0; s+x <= n; ++s)
        {
            for (int t = 0; t+y <= n; ++t)
            {
                ans = max( ans, cal(s, t, s+x, t+y) );
                // cout << s << t << "st " << cal(s, t, s+x, t+y) << " xy"<<x<<y<<endl;
            }
        }
    }
    return ans;
}

int main(){
    cin >> n;
    Fill(dp, 0);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> dp[i][j];
        }
    }

    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        cin >> P[i]; 
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            dp[i][j] += dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
        }
    }

    int ans[52*52];
    ans[0] = 0;
    for (int i = 1; i <= n*n; ++i)
    {
        ans[i] = max(solve(i), ans[i-1]);
    }
    for (int i = 0; i < q; ++i)
    {
        cout << ans[P[i]] << endl;
    }
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 005 #23

C - おいしいたこ焼きの売り方

問題文

Note

D - おいしいたこ焼きの焼き方

問題文

note