キーエンスプログラミングコンテスト 2020 【Cまで】

Cまでしか解けなかったんですけど、何というかAtCoderでは珍しい雰囲気の問題だった・・・

A: Aにしては結構珍しい、読解力で実装を軽くしていく様な問題。

二つの操作は独立している ので最もマスが多く塗れる様な操作をひたすら繰り返せば良い。

A - Painting

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
    int H,W,N;
    cin >> H;
    cin >> W;
    cin >> N;

    cout << int(ceil((float)N/max(H,W))) << endl;

    return 0;
}

B: 数直線が10^9以上の長さがあるので、数直線の座標ごとに何かするのは無理。

ロボットの稼働範囲を数直線に引くと、これは区間スケジューリング問題の超典型に落ちる。

区間スケジューリング問題の存在をギリギリ思い出したので解けましたが知らないと無理・・・ (確か銀髪本にも載ってたような。碧黴さんありがとう。)

Spaghetti Source - 区間スケジューリング

B - Robot Arms

いくら典型に落ちるとはいえそれを知るきっかけがないと中々解けないと思った。(KONAMI)

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
    ll N;
    cin >> N;

    // pair<end,start>
    vector<pair<int,int>> v(N);

    REP(i,N) {
        int x,l;
        cin >> x >> l;
        v[i] = make_pair(x+l,x-l);
    }

    // sort from end
    sort(ALL(v));

    int ans = 0;
    ll lastWork = -1 * 1e10;
    REP(i,N) {
        // 最後に働いた時間より作業の開始時間の方が遅いなら使う
        if (lastWork <= v[i].second) {
            // cout << "use " << v[i].first << endl;
            ans++;
            lastWork = v[i].first;
            continue;
        }
    }

    cout << ans << endl;

    return 0;
}

C:

よ〜〜〜く考えると、 l = rが許されるので変に足し算しなくてもよくね?って気付きます。

言ってしまえば、

N = 5 K = 3の時、

(ゴミ) (ゴミ) S S Sってやるだけです。

で、ゴミを何も考えずにINF(1e9)にします。

しかし、S=1e9の場合WA吐かれるので、S=1e9の場合は、任意の整数kを使って、 (ゴミ)*k ≠ S を満たす満たすゴミを使用します。例えば ゴミ=1e9-10

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
    int N,K,S;
    cin >> N >> K >> S;
    ll dead = INF;
    if (INF == S) dead = INF-10;
    REP(i,N-K) {
        cout << dead << " ";
    }

    REP(i,K) {
        cout << S << " ";
    }

    cout << endl;

    return 0;
}
Licensed under CC BY-NC-ND 4.0
Built with Hugo
テーマ StackJimmy によって設計されています。