【競プロ精進ログ】【2021/03/12】ABC131: C, D ABC130: C ABC129: C

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC131: C – Anti-Division
ABC131: D – Megalomania
ABC130: C – Rectangle Cutting
ABC129: C – Typical Stairs
まとめ

ABC131: C – Anti-Division

ABC131 より、ABC131: C – Anti-Divisionを解きました。
難易度は茶色。

解法も実装も簡単だったので特に書くことないです。
こういう集合計算はありがちですね。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・A <= x <= B の最大値は 10^18 なので、シンプルに1つずつ探索するのは無理そう 
・A から B までの範囲の、Cの倍数の個数＋Dの倍数の個数-CとDの最小公倍数の倍数の個数で求められそう
*************************************************************************************/
lint gcd(lint a, lint b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

lint lcm(lint a, lint b)
{
    return a * b / gcd(a, b);
}

lint how_many(lint A, lint B, lint N)
{
    lint end = B / N;
    lint start = (A - 1) / N;

    return end - start;
}

int main()
{
    lint A, B, C, D;
    cin >> A >> B >> C >> D;
    lint l = lcm(C, D);

    cout << B - A + 1 - (how_many(A, B, C) + how_many(A, B, D) - how_many(A, B, l)) << endl;
    return 0;
}

ABC131: D – Megalomania

ABC131 より、ABC131: D – Megalomaniaを解きました。
難易度は茶色。

この問題解くときに、C++ の pair 型のデータをソートするときの仕様が勉強になりました。
普通に sort() を使うと、「first の昇順 → second の昇順」でソートされるみたいです。

要素がpairの時のvectorのソート – Qiita

今回は期日の昇順でソートをしたかったので、 B を pair の first に入れました。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;

/*************************************************************************************
NOTE: 

・締め切りの存在さえなければ、sum(Ai) 時間後にすべての仕事が終わる
・どんな順番に仕事を進めていけばいいか(締め切りの早い順？)
*************************************************************************************/

int main()
{
    lint N, A, B;
    cin >> N;

    using P = pair<lint, lint>;
    vector<P> vec(N);
    rep(i, N)
    {
        cin >> A >> B;
        vec[i].first = B;
        vec[i].second = A;
    }
    sort(vec.begin(), vec.end());

    lint time = 0;
    rep(i, N)
    {
        time += vec[i].second;
        if (time > vec[i].first)
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

ABC130: C – Rectangle Cutting

ABC130 より、ABC130: C – Rectangle Cuttingを解きました。
難易度は茶色。

最初全然解法が思いつかなかったのですが、サンプルがかなりのヒントでした。

「長方形を直線で分割する場合、直線が長方形の対角線の交点を通る = 直線が長方形を二等分する」ってのは常識なんですね。
知らなかったです。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・長方形を直線で分割する場合、 直線が長方形の対角線の交点を通る = 直線が長方形を二等分する となるらしい
  https://drken1215.hatenablog.com/entry/2019/06/17/003300
・これを知らなくてもサンプルを見れば何となく気づける感じ
・C++ は、整数型同士で除算すると、小数点以下が切り捨てられる(知らなかった…)
*************************************************************************************/

int main()
{
    double W, H;
    lint x, y;
    cin >> W >> H >> x >> y;

    double ans = (W * H) / 2;
    cout << ans << " ";

    if ((W == 2 * x) && (H == 2 * y))
    {
        cout << 1 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    
    return 0;
}

ABC129: C – Typical Stairs

ABC129 より、ABC129: C – Typical Stairsを解きました。
難易度は茶色。

なんぞこれむずい。
と思ったのですが、初歩的な DP 問題でした。

このくらいはサクサクっと解きたいところですが、まだまだ時間がかかりますね。
要精進。。。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・壊れた段がない場合の階段の上り方は、DPで表すことができる
・同じように、壊れた段がある場合の上り方も、DPで表すことができる
*************************************************************************************/

int main()
{
    lint N, M;
    cin >> N >> M;
    vector<lint> crash(N+1, 0);
    rep(i, M)
    {
        lint a;
        cin >> a;
        crash[a] = 1;
    }

    vector<lint> dp(N+1, 0);
    dp[0] = 1;
    if (crash[1] != 1) dp[1] = 1;

    for (lint n = 2; n <= N; ++n)
    {
        if (crash[n-1] != 1) dp[n] += dp[n-1];
        if (crash[n-2] != 1) dp[n] += dp[n-2];
        dp[n] %= 1000000007;
    }
    cout << dp[N] << endl;
    return 0;
}