【競プロ精進ログ】【2021/03/06】ABC165: D ABC162: D

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

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

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

精進ツリー

ABC165: D – Floor Function
ABC162: D – RGB Triplets
ABC194 参加
まとめ

ABC165: D – Floor Function

ABC165 より、D – Floor Function を解きました。
難易度は茶色。

提出コードはこちら。

#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: 

・x は 1 <= x <= N
・x と f(x)の値に相関性があれば、2分探索で求められそう
  → 相関じゃなくて周期性がありそう
  → 0 に到達した地点を最大値と判断させたものの 4/ 10 が TLE になった
  
・周期のマックスに到達するまでは、最初の正の数の値から 1 ずつ増えていくので、
  → 2分探索的に最大値がどの範囲にあるのか絞っていけそう
  → 周期性の特性を確認したら2分探索は不要だった。最大値は常に 1 <= x <= B の範囲に存在する
・B までの範囲で f(x) は単調増加なので、手前からやると最大O(10^12)になる
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. 1 から B までの範囲の解の最大値を求める
   → これだと TLE になる
2. B もしくは N の小さい方から、逆順にいくつか計算して大きい方をとる
*************************************************************************************/

lint func(lint A, lint B, lint x)
{
    lint ret;
    ret = floor((A*x) / B) - A * floor(x / B);
    return ret;
}

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

    lint ans = -1;

    lint counter = 0;
    for (lint i = min(N, B); i > 0; i--)
    {
        ans = max(ans, func(A, B, i));
        counter++;
        if (counter > 5) break;
    }

    cout << ans << endl;
    return 0;
}

ABC162: D – RGB Triplets

ABC162 より、 ABC162: D – RGB Tripletsを解きました。
難易度は茶色。

提出コードはこちら。

#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 4000
#define NIL -1

using lint = long long int;

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

・2*j != K + i かつ、 1<=i<j<k<=N を満たす
・文字列をstringとして扱えば、O(1) で Si にアクセスできる
・先に文字が全部異なる場合に取りうる組み合わせを洗い出して、それが条件を満たすか判断すればいいのでは
  → 計算量は 10^9 ~ 10^10 程度になりそう
・RGB それぞれの文字の配列を作れば、平均1300程度で探索が可能
  → RGB それぞれが異なる組み合わせは、 R*G*B の計算量で求めることができる
・O(N) で 10^10 程度ならギリギリいけるかな？
  → ダメでした。3/25 が TLE。

↓
・RGB の計算が 3乗にならないようにすればOK
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. Sの中から、RGBのそれぞれの要素番号を持つ配列を作成
2. R * B * G で、それぞれが違う文字になるような全パターン数を求める
3. N^2 の計算量で、2j = k + i かつ RGB が異なる場合の数を取得
*************************************************************************************/

string S;
vector<lint> R, G, B;
lint i, j, k;

void init(lint x, lint y, lint z)
{
    i = x < y ? (x < z ? x : z) : (y < z ? y : z);
    k = x < y ? (y < z ? z : y) : (x < z ? z : x);
    if((x != i) && (x != k)) j = x;
    if((y != i) && (y != k)) j = y;
    if((z != i) && (z != k)) j = z;
    return;
}

int main()
{
    lint N;
    cin >> N;
    cin >> S;

    for(lint i = 1; i <= S.length(); i++)
    {
        switch (S[i-1])
        {
        case 'R':
            R.push_back(i);
            break;
        case 'G':
            G.push_back(i);
            break;
        case 'B':
            B.push_back(i);
            break;
        default:
            break;
        }
    }

    lint pile = R.size() * B.size() * G.size();
    lint count = 0;
    for (lint i = 1; i < N - 1; i++)
    {
        for (lint j = i + 1; (2*j - i) <= N; j++)
        {
            lint k = 2 * j - i;
            if ((S[i-1] != S[j-1]) && (S[j-1] != S[k-1]) && (S[i-1] != S[k-1]))
            {
                count++;
            }
        }
    }

    cout << (pile - count) << endl;
    return 0;
}

ABC194 参加

今日はAtCoder Beginner Contest 194 – AtCoderに参加しました。

結果は、A,B,C の 3完で 3272位・・・。
少なくとも2000番台には乗っていきたい。

E 問題がかなり解けそうだったので、解けてればもっと順位が上がってたのになぁというところです。
引き続き精進しましょう。

E 問題の Mex Min、あと少しでいけそうでいけなくて 3 完フィニッシュ
くやC😭😭😭😭 pic.twitter.com/XUhqWtByfp
— かしわば (@yuki_kashiwaba) March 6, 2021

提出コードは、A,B はやるだけだったので割愛します。
C の提出コードはこちら。

普通にやると O(N^2) で無理そうだったので、式を展開＆変形して O(N) の形に落とし込みました。
変数名もろもろ適当なのはご愛嬌。

N = int(input())
A = list(map(int,input().split()))

ans = 0
zenbu = 0
zenbu2 = 0

for i in range(N):
    zenbu += A[i]
    zenbu2 += pow(A[i], 2)

for i in range(1, N):
    matubi = A[-i]
    temae = pow(matubi, 2) * (N - i)
    zenbu -= matubi
    zenbu2 -= pow(matubi, 2)

    ans += temae + zenbu2 - (2 * matubi * zenbu)

print(ans)

結果はギリギリ茶パフォで、色変までの折り返し地点に到達しました。
頑張りたい。