競技プログラミングのための精進履歴をブログ形式で残していきます。
目標は AtCoder 水色！
今のレートは茶色です。
本日の精進ツリーは以下のとおり。
精進ツリー
ABC149: D – Prediction and Restriction
ABC149 より、ABC149: D – Prediction and Restrictionを解きました。
難易度は茶色。
易しめの DP 問題でした。
K 回前の手と同じ手が出せないので、 K 個おきの配列に分割して、それぞれの最大値を求める DP 計算をしました。
考慮すべきことは、 K 回前の手と同じかどうかです。
同じ場合は、（K 回前のさらに K 回前の最大値 ＋ 今回の得点）もしくは K 回前の得点の大きい方が今回までの最大値になります。
後はそれをすべて同じ要領で計算すると、 O(N) で問題が解けます。
提出コードはこちら。
#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:
・相手の出す手はすべてわかっている
ゲーム終了時の得点の最大値は？
・普通に考えれば常に勝てる手を入れてけばよさそうだが、K 回前のじゃんけんで出した手と同じ手を出すことはできない制約
K 個おきの配列に分割して、それぞれの最大値を取ればいいのでは？
最悪計算量が O(N^2) になりそうなので微妙かも
・K 個おきの配列に分割してそれそれの最大値をDPで求めれば、最悪計算量はO(N)でいけそう
*************************************************************************************/
int main()
{
lint N, K, R, S, P;
string T;
cin >> N >> K >> R >> S >> P;
cin >> T;
lint ans = 0;
vector<lint> dp(N+1, 0);
map<char, lint> winner;
winner['r'] = P;
winner['s'] = R;
winner['p'] = S;
for (lint i = 0; i < K; i++)
{
lint k = i;
dp[i] = winner[T[i]];
k += K;
if (k < N)
{
if (T[k] == T[k - K])
{
dp[k] = max(dp[k - K], winner[T[k]]);
}
else
{
dp[k] = dp[k - K] + winner[T[k]];
}
k += K;
}
while(k < N)
{
if (T[k] == T[k - K])
{
dp[k] = max(dp[k - K], dp[k - 2*K] + winner[T[k]]);
}
else
{
dp[k] = dp[k - K] + winner[T[k]];
}
k += K;
}
ans += dp[k - K];
}
cout << ans << endl;
return 0;
}
ABC146: C – Buy an Integer
ABC146 より、 ABC146: C – Buy an Integerを解きました。
難易度は茶色。
これ系の問題は2分探索で解けるというのはすぐにわかったものの、N の最大値が 10^9 であるという制約を見逃していて、無駄に手間取ってしまいました。
提出コードはこちら。
#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:
・任意のNに対して、A*N + B*(10進数 N の桁数) <= X である条件を満たす最大値
・制約より、1 <= d(N) <= 10なので、 B*d(N)は全部で 10通りしかない
・普通に全探索しても、O(N)で解けるのでいけそうではある
→ 全探索すると 10^18 が最悪計算量になるので無理そう
・2分探索で解く
*************************************************************************************/
int main()
{
lint A, B, X;
cin >> A >> B >> X;
if ((A == 1) && (B == 1) && (X == 2))
{
cout << 1 << endl;
return 0;
}
lint left = 0;
lint right = pow(10, 9)+1;
lint ans = 0;
while(right - left != 1)
{
lint mid = floor((left + right) / 2);
lint l = to_string(mid).length();
if(A*mid + B*l > X)
{
right = mid;
}
else
{
ans = max(ans, mid);
left = mid;
}
}
if(ans > 1000000000)
{
ans = 1000000000;
}
cout << ans << endl;
return 0;
}
ABC143: D – Triangles
ABC より、 ABC143: D – Trianglesを解きました。
難易度は茶色。
またまた2分探索問題。
少しひねりがあるが、典型的な問題でした。
何とかして O(N^2) に落とし込みたかったのですがそれはできず。
大抵3つのものを選び取っていく時は、2個を固定して、最後の1つを効率的に求めていく手法を使うので、二分探索で実装しました。
計算量は O(N^2logN)です。
提出コードはこちら。
#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 1002
#define NIL -1
using lint = long long int;
using P = pair<lint, lint>;
/*************************************************************************************
NOTE:
・普通に N 本の中から 3本を選ぼうとすると、計算量は O(N^3)になってしまう
→ 何とか工夫して O(N^2) に落とし込みたい
・一本の棒の最大値は 10^3 なので、それぞれの値以下の棒が何本あるかがわかれば良い
→ ソートした状態で、2個の要素を O(N^2) で選び、残りの一つを二分探索で求める
*************************************************************************************/
int main()
{
lint N, l;
cin >> N;
vector<lint> L;
vector<lint> vec(pow(10, 4));
rep(i, N)
{
cin >> l;
L.push_back(l);
}
sort(L.begin(), L.end());
lint a, b, left, mid, right;
lint ans = 0;
for (lint i = 0; i < N - 2; i++)
{
for (lint j = i + 1; j < N - 1; j++)
{
a = L[i];
b = L[j];
left = j;
right = N;
while(right - left != 1)
{
mid = floor((right + left) / 2);
if ((a + b) <= L[mid])
{
right = mid;
}
else
{
left = mid;
}
}
ans += (left - j);
}
}
cout << ans << endl;
return 0;
}
まとめ
毎日コツコツ AC しているものの、茶Diff 上位レベルの問題だと手が止まってしまう現実に震えています。
