ABC396 A-F
Published on 2025-03-12Last Modified 2025-03-12
Table Of Contents
A - Triple Four
問題文の通り$A _ i = A _ {i + 1} = A _ {i + 2}$を判定していけば良い。各$i$について$O(1)$個の項を見れば良いので、全体で$O(N)$時間。
import std;
void main () {
int N = readln.chomp.to!int;
auto A = readln.split.to!(int[]);
bool ok = false;
foreach (i; 0 .. N - 2) {
if (A[i] == A[i + 1] && A[i + 1] == A[i + 2]) {
ok = true;
}
}
if (ok) {
writeln("Yes");
}
else {
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));
}
}
B - Card Pile
明らかにカードの山はFirst In Last Outによりシミュレーションできる。 よって、stackを用いれば良い。 実装上は、動的配列の末尾への操作によりstackを実現するのが最も簡単だと思う。
import std;
void main () {
int Q = readln.chomp.to!int;
auto que = new int[](0);
foreach (i; 0 .. 100) que ~= 0;
auto ans = new int[](0);
foreach (i; 0 .. Q) {
auto query = readln.split.to!(int[]);
int t = query[0];
if (t == 1) {
int x = query[1];
que ~= x;
}
if (t == 2) {
ans ~= que[$ - 1];
que.length--;
}
}
writefln("%(%s\n%)", 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));
}
}
C - Buy Balls
できるだけ頭を使わずにできるならそれに越したことはないので、全探索を考える。 黒を$i$個取ったとして、最適な白のとり方を考える。（このとき、黒は降順に$i$個取るのが最適なことに注意。）
「まだ取れる余裕があるのに取らないほうが得になる場合」がいつになるのか考えると、それは負の項しか残っていないときになる。これを踏まえよう。 白のうち正の項が$x$個あったとする。最適なとり方は $i \leq x$のとき、白の降順$i$個。$x < i$のとき、白の降順$x$個となる。
白、黒どちらも降順にソートした上で累積和を取っておくことで必要な値を$O(1)$時間で取得できる。
import std;
void main () {
int N, M; readln.read(N, M);
auto B = readln.split.to!(int[]);
auto W = readln.split.to!(int[]);
B.sort!"a > b";
W.sort!"a > b";
auto bcc = new long[](N + 1);
foreach (i; 0 .. N) bcc[i + 1] = bcc[i] + B[i];
auto wcc = new long[](M + 1);
foreach (i; 0 .. M) wcc[i + 1] = wcc[i] + W[i];
int wp = 0;
foreach (w; W) if (0 < w) wp++;
long ans = -long.max;
foreach (i; 0 .. N + 1) {
long candi = bcc[i];
if (wp <= i) {
candi += wcc[wp];
}
else {
candi += wcc[i];
}
ans = max(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));
}
}
D - Minimum XOR Path
一般に、XORの最小値を考えようとしても、dpのようなことをするのが難しい。（部分最適性が多くの場合成り立たないので） なので、全探索をベースに考える。 $N \leq 10$なので、十分パスの列挙ができそうな感じがするので、それを書くと通る。 visited配列を持ちながらdfsをすると効率的に列挙できるが、同じ頂点を二度通らないという制約から、順列全探索によるパス列挙を行うこともできる。
import std;
void main () {
int N, M; readln.read(N, M);
auto graph = new long[][](N, N);
foreach (g; graph) g[] = -1;
foreach (i; 0 .. M) {
int u, v;
long w;
readln.read(u, v, w);
u--, v--;
graph[u][v] = graph[v][u] = w;
}
auto ord = iota(N).array;
long ans = long.max;
void f () {
if (ord[0] != 0) return;
bool ok = true;
long res = 0;
foreach (i; 0 .. N - 1) {
if (graph[ord[i]][ord[i + 1]] == -1) {
ok = false;
break;
}
res ^= graph[ord[i]][ord[i + 1]];
// 頂点Nに到着
if (ord[i + 1] == N - 1) break;
}
if (!ok) return;
if (res < ans) {
ans = res;
}
}
do {
f();
} while (nextPermutation(ord));
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));
}
}
E - Min of Restricted Sum
いくつかのモノ同士の「関係性」が与えられたときに、グラフに関する問題に帰着することで見通しが良くなるケースがある。今回もそのような問題になっている。
思考の流れとしては次のような感じだった。
- 可能不可能のサンプルを書き下して眺める。連立方程式を解くみたいなことをするのはどう考えても厳しいので、グラフに帰着させると良さそうだと思う。
- サンプル2が不可能なことから、木であれば可能、木でなくても色々都合が良ければ可能になりそうだと思う。
- サンプル1を眺めて、最小値を達成する方法を考える。この例だと頂点1に100がないと明らかに最小値の達成は不可能になる。ここで桁ごとに独立に考えて良いことに気がつく。また、適当に取った全域木を満たしていくみたいなことは無理そうだと考える。
- 桁ごとに考えたとき、各XORの条件は「隣接頂点の桁が同じか異なるか」の指示になっていることが見えてくる。この条件を満たしたときに最小にするためには、より少ない方に1を割り当てるだけで良いことがわかる。
- 二部グラフの判定の問題に似ているので、それをやる。
桁が同じでなければいけない頂点集合を一つに潰してしまえば、完全に二部グラフ判定と等価の問題になる。あとは各連結成分について頑張って集計し、より少ない方に1を割り当てるようにすれば通る。
import std;
void main () {
int N, M; readln.read(N, M);
auto X = new int[](M);
auto Y = new int[](M);
auto Z = new int[](M);
foreach (i; 0 .. M) {
readln.read(X[i], Y[i], Z[i]);
X[i]--, Y[i]--;
}
// グラフみたいな方向で考えるのがよさそう。
// 各連結成分が木なら可能。サイクルを持っていたとしても都合が合えば可能。
// 桁ごとに独立に考えてよくて、そうするとXORの条件は頂点ラベルが等しいかどうか
// -> 二部グラフが作れるかどうか
// -> 少ない方に1を割り当ててやればよい。
bool ok = true;
auto ans = new int[](N);
foreach (b; 0 .. 30) {
// 同じ色をまとめる
auto group = UnionFind(N);
foreach (i; 0 .. M) {
if ((Z[i] & (1 << b)) == 0) {
group.unite(X[i], Y[i]);
}
}
// 二部グラフ判定
auto graph = new int[][](N);
auto color = new int[](N);
color[] = -1;
foreach (i; 0 .. M) {
if ((Z[i] & (1 << b)) == 0) continue;
graph[group.root(X[i])] ~= group.root(Y[i]);
graph[group.root(Y[i])] ~= group.root(X[i]);
}
auto que = new Tuple!(int, int)[](0);
auto paint = new int[](N);
void dfs (int pos, int c) {
foreach (to; graph[pos]) {
// 未訪問
if (color[to] == -1) {
que ~= tuple(to, c ^ 1);
color[to] = c ^ 1;
dfs(to, c ^ 1);
}
else {
if (color[to] == c) {
ok = false;
}
}
}
}
foreach (i; 0 .. N) {
if (color[i] == -1) {
que.length = 0;
color[i] = 0;
que ~= tuple(i, 0);
dfs(i, 0);
// queに入ってるのが連結成分
// 根が?である頂点がどちらになるかをここで決定しておく
int[2] count;
foreach (j; 0 .. que.length) {
count[que[j][1]] += group.GroupSize(que[j][0]);
}
if (count[0] <= count[1]) {
foreach (v; que) {
int cc = 0;
if (v[1] == 0) cc = 1;
paint[v[0]] = cc;
}
}
else {
foreach (v; que) {
int cc = 0;
if (v[1] == 1) cc = 1;
paint[v[0]] = cc;
}
}
}
}
foreach (i; 0 .. N) {
ans[i] |= paint[group.root(i)] << b;
}
}
if (ok) {
writefln("%(%s %)", ans);
}
else {
writeln(-1);
}
}
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));
}
}
/* UnionFind */
実は二部グラフにこだわる必要はなく、二部グラフ判定の途中に「色が同じ条件の辺があって、実際に色が同じような隣接頂点」の存在を許容するように改造することで、途中の頂点集合を潰すフェーズがまるごといらなくなり、集計と解への01割り当てが非常に容易になる。
import std;
void main () {
int N, M; readln.read(N, M);
auto graph = new Tuple!(int, int)[][](N);
foreach (i; 0 .. M) {
int X, Y, Z; readln.read(X, Y, Z);
X--, Y--;
graph[X] ~= tuple(Y, Z);
graph[Y] ~= tuple(X, Z);
}
// 二部グラフのアルゴリズムにこだわらなくても、整合性が取れていればスルーするようにすれば頂点集合の圧縮が必要ない上、実際の彩色の集計が非常に簡単になる。
auto q = DList!(Tuple!(int, int))();
auto color = new int[](N);
auto ans = new int[](N);
bool ok = true;
auto buf = new int[][](2);
foreach (b; 0 .. 30) {
color[] = -1;
foreach (i; 0 .. N) {
if (color[i] != -1) continue;
buf[0].length = buf[1].length = 0;
color[i] = 0;
q.insertBack(tuple(i, 0));
buf[0] ~= i;
while (!q.empty()) {
auto pos = q.front();
q.removeFront();
foreach (to; graph[pos[0]]) {
bool same = (to[1] & (1 << b)) == 0;
if (color[to[0]] == -1) {
int nex = pos[1] ^ 1;
if (same) nex = pos[1];
color[to[0]] = nex;
q.insertBack(tuple(to[0], nex));
buf[nex] ~= to[0];
}
else {
if (same && color[to[0]] == (pos[1] ^ 1)) ok = false;
if (!same && color[to[0]] == pos[1]) ok = false;
}
}
}
// 集計
if (buf[0].length < buf[1].length) {
foreach (v; buf[0].chain(buf[1])) color[v] ^= 1;
}
}
// 反映
foreach (i; 0 .. N) {
ans[i] |= color[i] << b;
}
}
if (ok) {
writefln("%(%s %)", ans);
}
else {
writeln(-1);
}
}
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));
}
}
F - Rotated Inversions
本番解けなかった。 仮にMODを取らなかったとすると、転倒数は変化しない。これは任意に二項取ってきたとき、その大小関係が保たれるからである。
逆に言うと、転倒数の変化と$M - 1$から$0$への変化は密接に結びついている。 ある数の変化でどのように変わるかを観察してみよう。 以後、数が$M - 1$から$0$に変化することを「flipする」と呼ぶ。
位置$i$にある項がflipしたとすると、$i$より前にある$0$超過の要素との寄与が+0から+1に変化し、$i$より後ろにある$0$超過の要素との寄与が+1から+0に変化する。
この観察を用いて、各項からの寄与の配列（$i$番目の項が、ペア$(*, i)$による転倒数への寄与を表す配列）をシミュレーションすることができる。
具体的には、前者は位置$i$より前にある、$A _ i$と等しくない要素がすべて+1寄与になるということなので、同じタイミングでflipするインデクスを事前に列挙しておけば$O(1)$時間で計算可能。 後者は区間$[i + 1, N)$へ-1寄与を行うとみなすことができる。
これら2つの寄与の変化は区間加算、区間和取得ができれば素直に表現可能で、遅延セグメント木を用いて計算可能。
#include <iostream>
#include <vector>
#include <atcoder/segtree>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;
using ll = long long;
// https://betrue12.hateblo.jp/entry/2020/09/23/005940
struct S{
long long value;
int size;
};
using F = long long;
S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }
int seg_op (int x, int y) {
return x + y;
}
int seg_e () {
return 0;
}
int main () {
int N, M; cin >> N >> M;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
lazy_segtree<S, op, e, F, mapping, composition, id> seg(N + 10);
segtree<int, seg_op, seg_e> rsq(M + 10);
for (int i = 0; i < N; i++) {
seg.set(i, S{rsq.prod(A[i] + 1, M + 10), 1});
rsq.set(A[i], rsq.get(A[i]) + 1);
}
vector<vector<int>> flip(M + 1);
for (int i = 0; i < N; i++) {
flip[M - A[i]].push_back(i);
}
vector<ll> ans(M);
ans[0] = seg.prod(0, N).value;
vector<int> buf(N);
for (int i = 1; i < M; i++) {
for (int j = 0; j < flip[i].size(); j++) {
buf[j] = flip[i][j] - j - seg.get(flip[i][j]).value;
}
for (auto idx : flip[i]) {
seg.apply(idx + 1, N, -1);
}
for (int j = 0; j < flip[i].size(); j++) {
seg.set(flip[i][j], S{buf[j], 1});
}
ans[i] = seg.prod(0, N).value;
}
for (auto v : ans) {
cout << v << "\n";
}
}
さて、上記解法のすべてにおいて、「寄与の配列の総和」のみをが必要であることがわかる。 実は配列全体をシミュレーションする必要はなく、総和だけ保持しておけば十分。
import std;
void main () {
int N, M; readln.read(N, M);
auto A = readln.split.to!(int[]);
auto ans = new long[](M);
auto rsq = new SegmentTree!(int, (int a, int b) => a + b, () => 0)(M + 10);
foreach (i; 0 .. N) {
ans[0] += rsq.prod(A[i] + 1, M);
rsq.set(A[i], rsq.get(A[i]) + 1);
}
auto flip = new int[][](M + 1);
foreach (i; 0 .. N) {
flip[M - A[i]] ~= i;
}
foreach (i; 1 .. M) {
long plus = 0, minus = 0;
// 増える分はflip場所のみ0の転倒数
// 減る分はflip場所のみ1の転倒数
// これらは特殊ケースなのでO(|flip[i]|)で計算可能
foreach (j; 0 .. flip[i].length) {
plus += flip[i][j] - j;
int nex = N;
if (j + 1 < flip[i].length) nex = flip[i][j + 1];
minus += 1L * (j + 1) * (nex - flip[i][j] - 1);
}
ans[i] = ans[i - 1] + plus - minus;
}
writefln("%(%s\n%)", 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));
}
}
/* SegmentTree */
もう一つアプローチがある。 ある値の異なる二項に注目したとき、それらの関係性は常に「転倒数に+1寄与」か「転倒数に+0寄与」のどちらかになり、$k$を$M - 1$まで増やしていく過程でこの関係性は$O(1)$回しか変化しない。 そこで、長さ$M$の解を入れる配列を用意して、その上ですべての二項の寄与を区間加算することでも解くことができる。
すべての二項のペアは$O(N ^ 2)$個あるが、すべてのペアを見ずともうまく区間加算を行うことができる。
ここから$o(N ^ 2)$回の区間加算で正確にシミュレートするため主客転倒を行う。そのために、元の区間加算が実際どのようになるのかを考える必要がある。
以下、$i < j$を仮定
- $A _ i < A _ j$
この場合、$A _ j$がflipしてから$A _ i$がflipするまで（タイプ1）加算を行えば良い。
- $A _ i > A _ j$
この場合、最初から$A _ i$がflipするまで（タイプ2）と、$A _ j$がflipしてから最後まで（タイプ3）加算を行えばよい。
ここからタイプごとに固定する頂点を定め、集客転倒をし、区間加算に落とし込む。 以下の議論では、「ある区間に+1をする」ではなく、「はみ出した区間を-1で打ち消す」ことを念頭に置くと理解しやすい。
- タイプ1
まず終点を考えずに+1を積もう。これは$j$側を固定して考えるとよい。 $A _ j$がflipするタイミング、つまり$\mathrm{ans} _ {M - A _ j}$に「$j$より前にあって、$A _ j$未満の項の数」を積む。
次に-1の区間加算で終点を作ろう。こちらは$i$側を固定する。 $\mathrm{ans} _ {M - A _ i}$から「$i$より後ろにあって、$A _ i$より大きな項の数」を引く。
- タイプ2
始点は$k = 0$における転倒数そのものである。これを$\mathrm{ans} _ 0$に積む。
終点は$A _ i$を固定する。$\mathrm{ans} _ {M - A _ i}$から「$i$より後ろにあって、$A _ i$より小さいもの」を引く。
- タイプ3
始点は$A _ j$を固定。$\mathrm{ans} _ {M - A _ j}$に「$j$より前にあって$A _ j$より大きなもの」を積む。
終点は考えなくてよい。
これらは値ベースのセグメント木などで計算できる。
import std;
void main () {
int N, M; readln.read(N, M);
auto A = readln.split.to!(int[]);
// ある添字組に着目し、転倒数への寄与を考える。
// 寄与を与えるタイミングと寄与が消えるタイミングを切り離して考える。
// つまり、寄与は一旦onになったらその後ずっとonのままと考えて計算し、寄与のoffを-1寄与とみなして計算することで最後に辻褄を合わせる。
// 寄与は2通り。
// 1. 最初から転倒数に寄与するペア
// 2. M - 1 -> 0のflip時に寄与し始めるペア
// 1は転倒数そのもの。k = 0から後ろに寄与。ただし、途中で一度無効化されたあとまた寄与することができるので注意。
// 2は後ろの項を固定して数え上げることにすると、自分より前の自分より小さい値の個数。これは値ベースのセグメント木で数えられる。
// それぞれに対して打ち消しがどうなるのか考える。
// 1に対する打ち消しは、値の大きい方が0にflipした瞬間を考えると都合が良い。これは自分より後ろにいるより小さいものの個数
// 2に対する打ち消しは、小さい方がflipするタイミングを考えると都合が良い。これは自分より後ろにいるより大きいものの個数
// これらをすべて区間加算として積んで、点取得をするとOK
auto rsq = new SegmentTree!(int, (int a, int b) => a + b, () => 0)(M + 1);
auto ans = new long[](M + 1);
// 寄与
foreach (i; 0 .. N) {
ans[0] += rsq.prod(A[i] + 1, M);
ans[M - A[i]] += rsq.prod(0, A[i]);
ans[M - A[i]] += rsq.prod(A[i] + 1, M);
rsq.set(A[i], rsq.get(A[i]) + 1);
}
// 打ち消し
auto count = new int[](M);
foreach_reverse (i; 0 .. N) {
ans[M - A[i]] -= N - i - 1 - count[A[i]];
count[A[i]]++;
}
foreach (i; 0 .. M) {
ans[i + 1] += ans[i];
}
writefln("%(%s\n%)", ans[0 .. M]);
}
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));
}
}
/* SegmentTree */