ABC346参加記録
Published on 2024-03-29Last Modified 2024-03-29
Table Of Contents
はじめに
前回のエントリ同様に、更新できていませんでしたが更新します。
戦績
- 順位 : 1492th
- パフォーマンス : 1389
- レーティング変化 : 1340 → 1345 (+5)
問題
A - Adjacent Product
隣接項の積を求めれば良いです。ループを回しましょう。
import std;
void main () {
int N = readln.chomp.to!int;
auto A = readln.split.to!(int[]);
foreach (i; 0..N - 1) {
write(A[i] * A[i + 1]);
if (i < N - 1) write(" ");
}
write("\n");
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
B - Piano
$W, B$が十分小さいため、$S$の最初の200文字程度を考えれば十分です。あとは連続部分列を全部攫っても間に合います。
import std;
void main () {
int W, B; readln.read(W, B);
string S = "wbwbwwbwbwbw";
string T = "";
foreach (i; 0..100) T ~= S;
foreach (i; 0..T.length) {
foreach (j; i + 1..T.length) {
int w = 0;
int b = 0;
foreach (k; i..j) {
if (T[k] == 'w') w++;
if (T[k] == 'b') b++;
}
if (w == W && b == B) {
writeln("Yes");
return;
}
}
}
writeln("No");
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
C - Σ
$K$が結構大きいため、$O(K)$は避けたいところです。ということで、$(総和) - (Aに現れたもの)$を考えるとうまく行きます。 補集合を考えるのは典型テクと言えるでしょう。
import std;
void main () {
int N, K; readln.read(N, K);
auto A = readln.split.to!(int[]);
bool[int] mp;
foreach (a; A) mp[a] = true;
long ans = 1L * K * (K + 1) / 2;
foreach (key, val; mp) if (key <= K) ans -= key;
writeln(ans);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
D - Gomamayo Sequence
与えられた文字列をgomamayoに変化させる最小コストを問う問題です。
どこでgomamayoを作るかを探索できるかを考えます。
すると、gomamayo部分以外は必ず0101...または1010...となるので、元の文字列の連続部分列をこれらのいずれかに変化させるコストがわかれば良さそうです。
すなわち、変化させるコストの累積和を持てば良いことがわかります。
前半部分が0101...であるとき、gomamayo部分で2文字消費するため、後半は1010...の方を適用すれば良いです。
逆も同様です。
import std;
void main () {
int N = readln.chomp.to!int;
string S = readln.chomp;
auto C = readln.split.to!(int[]);
solve(N, S, C);
}
void solve (int N, string S, int[] C) {
// どこを揃えるか探索
auto zero_one = new long[](N + 1);
auto one_zero = new long[](N + 1);
foreach (i; 0..N) {
if (i % 2 == 0) {
if (S[i] == '0') {
zero_one[i + 1] = zero_one[i];
one_zero[i + 1] = C[i] + one_zero[i];
}
else {
zero_one[i + 1] = C[i] + zero_one[i];
one_zero[i + 1] = one_zero[i];
}
}
else {
if (S[i] == '0') {
zero_one[i + 1] = C[i] + zero_one[i];
one_zero[i + 1] = one_zero[i];
}
else {
zero_one[i + 1] = zero_one[i];
one_zero[i + 1] = C[i] + one_zero[i];
}
}
}
long ans = long.max;
foreach (i; 0..N - 1) {
{ // 0
long candi = 0;
if (i % 2 == 0) { candi += zero_one[i] + (one_zero[N] - one_zero[i + 2]); }
else { candi += one_zero[i] + (zero_one[N] - zero_one[i + 2]); }
if (S[i] == '1') candi += C[i];
if (S[i + 1] == '1') candi += C[i + 1];
ans = min(ans, candi);
}
{ // 1
long candi = 0;
if (i % 2 == 0) { candi += one_zero[i] + (zero_one[N] - zero_one[i + 2]); }
else { candi += zero_one[i] + (one_zero[N] - one_zero[i + 2]); }
if (S[i] == '0') candi += C[i];
if (S[i + 1] == '0') candi += C[i + 1];
ans = min(ans, candi);
}
}
writeln(ans);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
dpでも解けることをコンテスト終了後知りました。 前から順番に確定させていくことにします。このとき、最新の場所では
- 最後が何か
- すでにgomamayoを達成したか
がわかれば十分です。 したがって、$\mathrm{dp}[i][j][k] \coloneqq (\text{「先頭$i$項確定させて、最後の項が$j$で、すでにgomamayoかどうかが$k$」に至る最小コスト})$ とすれば良いです。
import std;
void main () {
int N = readln.chomp.to!int;
string S = readln.chomp;
auto C = readln.split.to!(int[]);
solve(N, S, C);
}
void solve (int N, string S, int[] C) {
// 前からdpで決めていく
auto dp = new long[][][](N + 1, 2, 2);
// dp[i][j][k] := 先頭i文字確定して、最後がjで、すでにgomamayoかどうかがk
foreach (d; dp) foreach (dd; d) dd[] = long.max;
dp[1][0][0] = (S[0] == '0' ? 0 : C[0]);
dp[1][1][0] = (S[0] == '1' ? 0 : C[0]);
foreach (i; 1..N) {
foreach (j; 0..2) {
foreach (k; 0..2) {
if (dp[i][j][k] == long.max) continue;
int cost_1 = 0;
if ((j + 1) % 2 != S[i] - '0') cost_1 = C[i];
dp[i + 1][(j + 1) % 2][k] = min(dp[i + 1][(j + 1) % 2][k], dp[i][j][k] + cost_1);
// gomamayoを作りに行く
if (k == 0) {
int cost_2 = 0;
if (j != S[i] - '0') cost_2 = C[i];
dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][0] + cost_2);
}
}
}
}
long ans = min(dp[N][0][1], dp[N][1][1]);
writeln(ans);
}
E - Paint
巨大なグリッド上に、1行(列)ずつ色を塗っていく問題です。 まず、シミュレーションは無理なことがわかります。どうにかうまくやる必要があります。
さて、自分も結構突っかかりましたが、これらのクエリは後ろのクエリのほうが強いという性質があります。 縦か横かに関係なく、後ろのクエリならばそれより前のクエリより優先されます。 この性質により、一番最後から見ていけば楽になります。 縦と横で、すでに採用された本数を記録しておくことで、次に引く線が何回かき消されるかがわかるからです。
これが見えてしまえば割と簡単でした。
import std;
void main () {
int H, W, M; readln.read(H, W, M);
auto paint = new Tuple!(int, int, int)[](M);
foreach (i; 0..M) {
int T, A, X; readln.read(T, A, X);
A--;
paint[i] = tuple(T, A, X);
}
solve(H, W, M, paint);
}
void solve (int H, int W, int M, Tuple!(int, int, int)[] paint) {
// クエリを後ろから見れば良さげ？
paint.reverse;
auto color_count = new long[](2 * 10^^5 + 1);
auto used_h = new bool[](H);
int count_h = 0;
auto used_w = new bool[](W);
int count_w = 0;
foreach (p; paint) {
int T = p[0];
int A = p[1];
int X = p[2];
if (T == 1) {
if (used_h[A]) continue;
used_h[A] = true;
count_h++;
color_count[X] += W - count_w;
}
if (T == 2) {
if (used_w[A]) continue;
used_w[A] = true;
count_w++;
color_count[X] += H - count_h;
}
}
int count = 0;
long sum = 0;
foreach (i, v; color_count[1..$]) if (0 < v) {
sum += v;
count++;
}
color_count[0] = 1L * H * W - sum;
if (0 < color_count[0]) count++;
writeln(count);
foreach (i, v; color_count) {
if (v == 0) continue;
writeln(i, " ", v);
}
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
色0の処理には少し注意が必要です。(2ペナ食らいました。)
F - SSttrriinngg in StringString
部分列判定をする問題です。 典型テクとして、「答えで二分探索」を考えます。 これができることはほぼ明らかなので、一回の判定問題をある程度高速に解ければOKです。 関数$f$の方はあくまで元の文字列をつなげたものなので、文字列の構造自体は破壊されません。 すでに使用した周回数と現在のカーソル位置を持てば、消化したい文字列を順番に見ていくことで判定問題を$O(|T| \alpha)$くらいで解けます。($\alpha$はそんなに重くないやつくらいで考えてください。) あとは場合分けを頑張るとACできます。
import std;
void main () {
long N = readln.chomp.to!long;
string S = readln.chomp;
string T = readln.chomp;
solve(N, S, T);
}
void solve (long N, string S, string T) {
// 前から消化していく感じで二分探索
bool[char] S_mp;
foreach (c; S) S_mp[c] = true;
foreach (t; T) {
if (t !in S_mp) { // Tの文字でSにはいってないやつがある。
writeln(0);
return;
}
}
auto idx = new int[][](26, 0);
// idx[i][j] := S中で文字iが前からj番目に現れるインデックス
foreach (i, c; S) idx[c - 'a'] ~= i.to!int;
bool f (long x) {
if (x == 0) return true;
long used = 0;
int cur = 0;
foreach (t; T) {
/*
writeln("char : ", t);
writeln("used : ", used);
writeln("cur : ", cur);
writeln();
*/
long X = x;
// curがどこか探索
if (cur <= idx[t - 'a'][$ - 1]) {
int ng = -1, ok = idx[t - 'a'].length.to!int - 1;
while (1 < abs(ok - ng)) {
int mid = (ok + ng) / 2;
if (cur <= idx[t - 'a'][mid]) {
ok = mid;
}
else {
ng = mid;
}
}
enforce(cur <= idx[t - 'a'][ok]);
enforce(ng == -1 || idx[t - 'a'][ng] < cur);
enforce(ng + 1 == ok);
// 今のページで消化しきれる？
if (X <= idx[t - 'a'].length - ok) {
// できる
cur = idx[t - 'a'][ok + X - 1] + 1;
if (S.length <= cur) {
cur = 0;
used++;
}
continue;
}
else {
// できないので、端数処理する
X -= idx[t - 'a'].length - ok;
used++;
cur = 0;
}
}
else {
// 次ページに進む
used++;
cur = 0;
}
used += X / idx[t - 'a'].length;
long rem = X % idx[t - 'a'].length;
if (rem == 0) used--;
cur = idx[t - 'a'][($ + rem - 1) % $] + 1;
if (S.length <= cur) { cur = 0; used++; }
if (N < used) return false;
}
if (0 < cur) return used < N;
return used <= N;
}
long ok = 0, ng = 10L ^^ 18;
while (1 < abs(ok - ng)) {
long mid = (ok + ng) / 2;
if (f(mid)) {
ok = mid;
}
else {
ng = mid;
}
}
writeln(ok);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
細かい場合分けが多いので詳細は書きませんが、概ね消化する文字の最初と最後に気を使うとうまく行く気がします。 真ん中あたりは割り算でガッとやりましょう。
これdiff高いのかなり非自明です。(相対的に)作業量多いだけ感がありました。
終わりに
本番でFをギリギリ通せなかったのが少し悔しいですが、概ねやりきれたと思います。 DEをちゃんとACできて嬉しいです。