A - ペアリング
問題文
4つの数が与えられる。各ステップで同じ値の2つの数字を選んで削除する。この操作を最大何回行えるかを求める。
解法
シミュレーションを行う。
コード
コードを表示
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
map<int, int> m;
m[a]++;
m[d]++;
m[c]++;
m[b]++;
int ans = 0;
for (auto& i : m)
{
ans += i.second / 2;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - ゴミ収集
問題文
n種類のゴミがある。i番目のゴミは日付をq_iで割った余りがr_iの場合に回収される。Q回のクエリがあり、j回目のクエリではゴミの種類t_jと投棄日d_jが与えられる。そのゴミが次に回収される日付を出力せよ。 注：投棄日と回収日が同じ場合、当日に回収される。
解法
シミュレーションを行う。
コード
コードを表示
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
void solve()
{
int n;
cin >> n;
vector<int> q(n), r(n);
for (int i = 0; i < n; ++i)
{
cin >> q[i] >> r[i];
}
int Q;
cin >> Q;
while (Q--)
{
int t, d;
cin >> t >> d;
t--;
int qi = q[t], ri = r[t];
int now = d % qi, ans;
if (now == ri)
{
ans = d;
}
else if (now < ri)
{
ans = d + ri - now;
}
else
{
ans = d + qi - now + ri;
}
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - 繰り返し
問題文
長さnの正整数列A = (A_1, A_2, ..., A_n)が与えられる。列B = (B_1, B_2, ..., B_n)を以下のように定義する。i = 1, 2, ..., nに対して、j < i かつ A_i = A_j を満たすjが存在すればB_i = j、そうでなければB_i = -1とする。
解法
シミュレーションを行う。タイムリミット回避のためにsetを使ってiより前に出現した要素を記録する。
コード
コードを表示
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
void solve()
{
int n;
cin >> n;
vector<int> v(n), b(n, -1);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
set<int> s;
for (int i = 0; i < n; i++)
{
if (s.count(v[i]))
{
for (int j = i - 1; j >= 0; j--)
{
if (v[j] == v[i])
{
b[i] = j + 1;
break;
}
}
}
s.insert(v[i]);
}
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - 単純パスの数え上げ
問題文
h行w列のマップが与えられる。'.'は空き、'#'は障害物である。各マスから始まる、障害物を含まない長さk+1のパスの個数（一度通ったマスは再び通れない）を求める。
解法
データサイズが非常に小さいため、DFSで全探索する。
コード
コードを表示
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 15;
char mp[mxn][mxn];
bool vis[mxn][mxn];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int h, w, k;
int ans;
void dfs(int x, int y, int step)
{
if (step == k)
{
ans++;
return;
}
for (int i = 0; i < 4; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 0 || tx >= h || ty < 0 || ty >= w || vis[tx][ty] || mp[tx][ty] == '#')
{
continue;
}
vis[tx][ty] = true;
dfs(tx, ty, step + 1);
vis[tx][ty] = false;
}
}
void solve()
{
cin >> h >> w >> k;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> mp[i][j];
}
}
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (mp[i][j] == '.')
{
vis[i][j] = true;
dfs(i, j, 0);
vis[i][j] = false;
}
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
E - mod和問題
問題文
n, mが与えられる。以下の式を求める。
解法
配列Aの累積和をSとすると、元の式は以下のように変形できる。 0 ≤ S_l-1, S_r < M なので、 さらに以下のように変形できる。 X_rの計算には、BIT（Binary Indexed Tree）を使用する。t_x は S_{l-1} = x となる l の個数を表す。このとき、X_r = t_{S_r + 1} + t_{S_r + 2} + ... + t_{m-1} であり、その後に t_{S_r} に1を加算する。 BITについての解説：動画1 動画2 B站の動画が分かりやすい。
コード
コードを表示
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
int n, m, ans;
int t[mxn];
inline int lowbit(int x)
{
return x & -x;
}
void update(int p)
{
while (p <= m + 1)
{
t[p]++;
p += lowbit(p);
}
}
int qury(int p)
{
int res = 0;
while (p)
{
res += t[p];
p -= lowbit(p);
}
return res;
}
void solve()
{
cin >> n >> m;
vector<int> a(n + 1), Sr(n + 1), Sl(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] %= m;
Sr[i] = (Sr[i - 1] + a[i]) % m;
Sl[i] = Sl[i - 1] + Sr[i];
}
for (int r = 1; r <= n; r++)
{
ans += Sr[r] * r - Sl[r - 1];
int X = qury(m + 1) - qury(Sr[r] + 1);
ans += X * m;
update(Sr[r] + 1);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
コンテストリンク: https://atcoder.jp/contests/abc378