競技プログラミングのための精進履歴をブログ形式で残していきます。
目標は AtCoder 水色！
今のレートは茶色です。
本日の精進ツリーは以下のとおり。
精進ツリー
ABC137: C – Green Bin
ABC137 より、 ABC137: C – Green Binを解きました。
難易度は茶色。
茶Diff 中位の割りにはかなり Easy な問題でした。
そのまま計算すると O(N^2) になってしまうので、まず文字列をソートし、ソートした文字列の連想配列を使って解きました。
提出コードはこちら。
#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:
・文字列のカウントの比較で計算すると、すべての文字列の判定にあたり O(10N) の計算が必要となる
・異なる二つの文字列を選んだ時に、それぞれに含まれる文字が一致する場合をカウントするのは O(N＾2)なので無理
・すべての文字列をソートした後に map にするのが良いのでは
ソートに O(N logN)
*************************************************************************************/
int main()
{
lint N;
cin >> N;
string S;
map<string, lint> SS;
for (lint i = 0; i < N; i++)
{
cin >> S;
sort(S.begin(), S.end());
if (auto iter = SS.find(S); iter != end(SS))
{
iter->second++;
}
else
{
SS.insert(make_pair(S, 1));
}
}
lint ans = 0;
for (auto s : SS)
{
if (s.second > 1)
{
ans += floor((s.second * (s.second - 1) / 2));
}
}
cout << ans << endl;
return 0;
}
ABC136: D – Gathering Children
ABC136 より、ABC136: D – Gathering Childrenを解きました。
難易度は茶色。
解法自体はすぐわかったのですが、実装で悩みました。
こういう境目までの連続した同じ値をカウントしていく場合は、ランレングス法というアルゴリズムが使えるようです。
こちらの記事を参考にさせていただきました。
AtCoder ABC 136 D – Gathering Children (茶色, 400 点) – けんちょんの競プロ精進記録
提出コードはこちら。
#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:
・試行回数は 10^100 で、全探索は不可能なので、周期性を見つける必要がある
・S <= 10^5 より、最低でも 10^5 回以内に周期性が見つかる
・選択できる移動可能な範囲は 右か左かなので、10^5 回以内に必ず L-R を繰り返すポイントにぶつかる
全員の移動を全探索すると O(N^2) かかってしまう
連続した L か R の個数の最大値が、配置が固定になる周期の最初の一回目までの移動回数
今いる位置から次の L もしくは R までのステップが偶数か否か
・全員の移動が固定化されたタイミングが偶数か奇数かで、10^100 回目の位置も決まる
*************************************************************************************/
int main()
{
string S;
cin >> S;
vector<lint> res(S.size(), 0);
vector<lint> div({0});
for (lint i = 0; i < S.size();)
{
lint j = i;
while ((j < S.size()) && S[i] == S[j])
{
j++;
}
div.push_back(j);
if (S[i] == 'L')
{
lint A = div[div.size() - 2] - div[div.size() - 3];
lint B = div[div.size() - 1] - div[div.size() - 2];
res[i - 1] = (A + 1) / 2 + B / 2;
res[i] = A / 2 + (B + 1) / 2;
}
i = j;
}
for (lint i = 0; i < res.size(); ++i) cout << res[i] << " ";
cout << endl;
}
ABC133: C – Remainder Minimization 2019
ABC133 より、 ABC133: C – Remainder Minimization 2019を解きました。
難易度は茶色。
これは割と簡単でした。
始めは境目を 2019 にしようと考えていましたが、 2019 の素因数である 673 でも同じ役割を果たせることに気づいたので少しだけ効率化をしました。
提出コードはこちら。
#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:
・mod 2019 の最小値なので、取りうるの値の 0 <= a <= 2018
・全探索だと難しいので、探索範囲を絞る、もしくは周期性を見つけ出す
・i を固定したときに j を一つずつ増やしていくと、 (i*j)mod2019 は i ずつ増えていく
・つまり、iの範囲は L <= i <= L + 2019 でOK
1. R - L >= 673 なら、確実に (i, j) が 2019の倍数になる組み合わせが存在するので、 0
2. R - L < 673 なら、全探索で OK
*************************************************************************************/
int main()
{
lint L, R;
cin >> L >> R;
if (R - L >= 673)
{
cout << 0 << endl;
}
else
{
lint ans = 2019;
for (lint l = L; l < R; l++)
{
for (lint r = l + 1; r <= R; r++)
{
ans = min(ans, (l * r) % 2019);
}
}
cout << ans << endl;
}
return 0;
}
まとめ
ABC133 の茶埋めまで終わりました。
ABC127 までの茶埋めが終わったら、緑埋めと蟻本を平行してやっていこうかなと思ってます。
