ABC352参加記録
Published on 2024-05-06Last Modified 2024-05-06
Table Of Contents
はじめに
いくつかの理由でしばらく更新していませんでしたが、久しぶりに更新することにしました。
戦績
- 順位: 771th
- パフォーマンス: 1697
- レーティング変動: 1509 → 1529 (+20)
問題の振り返り
A - AtCoder Line
駅$Z$が駅$X$と駅$Y$の間にあれば行くことができます。逆に、そうでない時は行くことができません。 したがって、$\min(X, Y) < Z < \max(X, Y)$が真であるかどうかで判定することができます。
import std;
void main () {
int N, X, Y, Z; readln.read(N, X, Y, Z);
if (min(X, Y) < Z && Z < max(X, Y)) {
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 - Typing
なかなかの難読です。 題意としては次のような感じです。
$S$を部分列として含む$T$が与えられる。$T$の部分列$S$であって、インデックスが辞書順最小であるものを求めよ。
これは$T$を前から見ていき、$S$の文字を貪欲にとっていくことで達成できます。
import std;
void main () {
string S = readln.chomp;
string T = readln.chomp;
int[] ans;
int lat = 0;
foreach (i, t; T) {
if (S.length <= lat) continue;
if (S[lat] == t) {
lat++;
ans ~= i.to!int + 1;
}
}
foreach (i, a; ans) {
write(a, i == ans.length - 1 ? '\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));
}
}
C - Standing On The Shoulders
求める答えは、$\max _ {1 \leq i \leq N} (\text{(巨人$i$を除いた肩までの高さの総和)} + \text{(巨人$i$の頭までの高さ)})$です。 累積和をとると、一人を除いた肩までの高さの総和を$\mathcal{O}(1)$で求めることができます。 よって、全体の計算量オーダー$\mathcal{O}(N)$で求めることができます。
import std;
void main () {
int N = readln.chomp.to!int;
auto height = new Tuple!(int, int)[](N);
foreach (i; 0..N) {
int A, B; readln.read(A, B);
height[i] = tuple(A, B);
}
// 累積和でOK
auto acc = new long[](N + 1);
acc[0] = 0;
foreach (i; 0..N) {
acc[i + 1] = acc[i] + height[i][0];
}
long ans = 0;
foreach (i; 0..N) {
// i人目を最後に立たせる。
long v = acc[i] + (acc[N] - acc[i + 1]);
v += height[i][1];
ans = max(ans, v);
}
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));
}
}
また、$\text{(肩までの高さ)} \leq \text{(頭までの高さ)}$が成立するため、求める答えは$\text{(肩までの高さの総和)} + \max _ {1 \leq i \leq N}(\text{(巨人$i$の頭までの高さ)} - \text{(巨人$i$の肩までの高さ)})$とも表すことができます。こちらも$\mathcal{O}(N)$で解けますし、楽です。
import std;
void main () {
int N = readln.chomp.to!int;
long ans = 0;
int diff_max = 0;
foreach (i; 0..N) {
int A, B; readln.read(A, B);
ans += A;
diff_max = max(diff_max, B - A);
}
ans += diff_max;
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 - Permutation Subsequence
求める値は、$\min _ {1 \leq i \leq N - K + 1}(\text{($i$から$i + K - 1$のすべての数を含む最小の連続部分列の長さ)})$と表すことができます。 すなわち、上記のような連続部分列の右端と左端のインデックスにのみ興味があります。
ここで、$\mathrm{index}[i] = \text{($i$のインデックス)}$を導入します。 これを用いると、上の値は$\max _ {i \leq x \leq i + K - 1} (\mathrm{index}[x]) - \min _ {i \leq x \leq i + K - 1} (\mathrm{index}[x])$ になります。 すなわち、長さ$K$の連続部分列の最大/最小を求める問題に帰着しました。
これをセグメントツリーを用いて求めると計算量オーダー$\mathcal{O}((N - K) \log N)$で解けます。
import std;
void main () {
int N, K; readln.read(N, K);
auto P = readln.split.to!(int[]);
P[] -= 1;
solve(N, K, P);
}
void solve (int N, int K, int[] P) {
// static range min queryとstatic range max queryが解ければよい。
auto RmQ = new SegmentTree!(int, (int a, int b) => min(a, b), () => int.max)(N);
auto RMQ = new SegmentTree!(int, (int a, int b) => max(a, b), () => -int.max)(N);
foreach (i; 0..N) {
RmQ.set(P[i], i);
RMQ.set(P[i], i);
}
int ans = int.max;
foreach (i; 0..N) {
if (N < i + K) break;
ans = min(ans, RMQ.prod(i, i + K) - RmQ.prod(i, i + K));
}
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));
}
}
セグメントツリーは長いので省略しました。
また、連続部分列の最大/最小値を求めるまでの考察は同じですが、平衡二分木を用いる解法もあります。 $i$から$i + K - 1$の連続部分列に対する値を求めた後、$i + 1$から$i + K$の連続部分列に対する値を求めることを考えると、$\mathcal{O}(1)$個の要素をremove/insertするだけで良いです。 これを続ける事で$\mathcal{O}(N \log N)$で解くことができます。
import std;
void main () {
int N, K; readln.read(N, K);
auto P = readln.split.to!(int[]);
P[] -= 1;
solve(N, K, P);
}
void solve(int N, int K, int[] P) {
auto rbt = new RedBlackTree!(int, "a < b", true)();
auto index = new int[](N);
foreach (i; 0..N) index[P[i]] = i;
foreach (i; 0..K - 1) rbt.insert(index[i]);
int ans = int.max;
foreach (i; K - 1..N) {
rbt.insert(index[i]);
ans = min(ans, rbt.back() - rbt.front());
rbt.removeKey(index[i - K + 1]);
}
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 - Clique Connect
クラスカル法を適用することを考えます。 すなわち、できるだけ安い辺を用いて連結成分を伸ばしていきます。 $A _ i$に含まれる頂点が一つの連結成分に属するようにしていき、最後に全体が連結であればよいです。
というわけで、$A _ i$に含まれる頂点を連結にする最安の方法がわかればよいです。 これは$A _ i$の全域木の一つをとればよいです。 例えば辺$e = (A _ {i, j}, A _ {i, j + 1})$をすべて見ることで達成できます。
import std;
void main () {
int N, M; readln.read(N, M);
auto K = new int[](M);
auto C = new int[](M);
auto A = new int[][](M, 0);
foreach (i; 0..M) {
readln.read(K[i], C[i]);
A[i] = readln.split.to!(int[]);
A[i][] -= 1;
}
solve(N, M, K, C, A);
}
void solve (int N, int M, int[] K, int[] C, int[][] A) {
// クラスカル法に突っ込む
auto UF = UnionFind(N);
auto index = iota(M).array();
index.sort!((a, b) => (C[a] < C[b]));
long ans = 0;
foreach (i; index) {
foreach (j; 0..K[i] - 1) {
if (UF.same(A[i][j], A[i][j + 1])) continue;
UF.unite(A[i][j], A[i][j + 1]);
ans += C[i];
}
}
int cc = 0;
foreach (i; 0..N) if (UF.root(i) == i) cc++;
if (1 < cc) {
writeln(-1);
}
else {
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));
}
}
UnionFindの実装は省略しました。 本番では超頂点をかませる微妙に怪しい方針でACしたため、こっちだけ載せておきます。
あと、「クリーク」という単語を知らなかったため調べてみました。 クリーク(グラフ理論) - Wikipedia
ざっくりいうと、グラフ$G$の極大な完全部分グラフのことをクリークと呼ぶらしいです。 この問題名との関連性で言うと、$A _ i$の中で出来るだけ辺をはると頂点数$K[i]$のクリークになるからということでしょうか。
F - Estimate Order
微妙に間に合わずACを逃しましたが、upsolveしたので載せておきます。 とりあえず、与えられた情報をできるだけ、すなわち、ある人が出てくる情報が高々1つになるようにまとめます。 こうすることで、わかっている順位の情報はパズルピースのようになります。 例えば、入力例3は
1______8
27__6
54
3
という4ピースになります。 このようにしてできたピースを組み合わせて、横幅$N$マスのパズルを完成させます。
さて、順位情報が確定できるというのは次のように言い換えることができます。
ピース$i$がある1つの場所以外にはめられた場合、他のピースをどのようにはめてもパズルを完成させることができない。
これをどうにか判定したいです。 というわけで、自分以外のピースを用いたときに実現できる盤面を列挙できれば良いです。 ピース数がそこそこ大きいため、単純な全探索は通りません。(多分) そこで、次の動的計画法を適用します。 $$\mathrm{dp}[i][S] \coloneqq (\text{先頭$i$個のピースを用いて盤面$S$を実現できるか})$$ $$\mathrm{rdp}[i][S] \coloneqq (\text{後ろ$i$個のピースを用いて盤面$S$を実現できるか})$$ これは$\mathcal{O}(N 2^N)$で計算できます。
このテーブルを用いることで、一つのピースが確定できるかを$\mathcal{O}(N 2^N)$で判定できます。 これで、全体$\mathcal{O}(N^2 2^N)$になります。
import std;
void main () {
int N, M; readln.read(N, M);
auto info = new Tuple!(int, int, int)[](M);
foreach (i; 0..M) {
int A, B, C; readln.read(A, B, C);
info[i] = tuple(A, B, C);
}
solve(N, M, info);
}
void solve (int N, int M, Tuple!(int, int, int)[] info) {
// 連結成分がパズルピースみたいになって順位が確定する。
// dfsによる探索だと間に合わない。 -> bitDPで埋めていく感じでできそう。
// ピースを作るよ
// ここがバグっていると思う。具体的には、現状の手法だと本来連結なのに連結でないと判定されてしまうようなピースが存在しうる。
int[][] piece;
// BFSでうまいことやりましょう。
auto vis = new bool[](M);
{
auto Q = DList!(int)();
void bfs (int cur) {
Q.insertBack(cur);
// 新規作成
piece ~= new int[](60);
auto p = piece[$ - 1];
p[] = -1;
while (!Q.empty) {
auto h = Q.front(); Q.removeFront();
vis[h] = true;
{ // 追加処理
bool add = false;
() {
foreach (index, v; p) {
if (v == info[h][0] || v == info[h][1]) {
add = true;
if (v == info[h][0]) p[index - info[h][2]] = info[h][1];
if (v == info[h][1]) p[index + info[h][2]] = info[h][0];
return;
}
}
}();
if (!add) {
p[30] = info[h][0];
p[30 - info[h][2]] = info[h][1];
}
}
foreach (index, I; info) {
if (!(I[0] == info[h][0] || I[1] == info[h][0] || I[0] == info[h][1] || I[1] == info[h][1])) continue;
if (vis[index]) continue;
Q.insertBack(index.to!int);
}
}
}
foreach (i; 0..M) {
if (vis[i]) continue;
bfs(i);
}
}
// 存在しない人を入れるよ
{
bool[int] mp;
foreach (I; info) mp[I[0]] = mp[I[1]] = true;
foreach (i; 1..N + 1) if (i !in mp) {
piece ~= [i];
}
}
// 前に詰めるよ + 後ろも詰めるよ
foreach (ref p; piece) {
foreach (i; 0..p.length) if (p[i] != -1) {
p = p[i..$];
break;
}
foreach_reverse (i; 0..p.length) if (p[i] != -1) {
p = p[0..i + 1];
break;
}
}
// bit変換するよ
auto piece_bit = new int[](piece.length);
foreach (i; 0..piece.length) {
foreach (j, v; piece[i]) {
if (v == -1) continue;
piece_bit[i] |= 1 << j;
}
}
int pN = piece_bit.length.to!int;
// dp[i][S] := 先頭iピースを用いてSを達成できるか？
auto dp = new bool[][](pN + 1, 1 << N);
dp[0][0] = true;
foreach (i; 0..pN) {
foreach (S; 0..(1 << N)) {
if (!dp[i][S]) continue;
int p = piece_bit[i];
while ((p | S) < (1 << N)) {
if ((p & S) == 0) dp[i + 1][S | p] = true;
p <<= 1;
}
}
}
auto rdp = new bool[][](pN + 1, 1 << N);
// rdp[i][S] := 後ろiピースを用いてSを達成できるか？
rdp[0][0] = true;
foreach (i; 0..pN) {
foreach (S; 0..(1 << N)) {
if (!rdp[i][S]) continue;
int p = piece_bit[pN - i - 1];
while ((p | S) < (1 << N)) {
if ((p & S) == 0) rdp[i + 1][S | p] = true;
p <<= 1;
}
}
}
// 判定
auto ans = new int[](N);
ans[] = -1;
foreach (i; 0..pN) {
int p = piece_bit[i];
int pad = 0;
int lpad = 0;
int count = 0;
while (p < (1 << N)) {
foreach (S; 0..(1 << N)) {
if (0 < (p & S)) continue;
int complement = (1 << N) - 1 - (p | S);
if (dp[i][S] && rdp[pN - i - 1][complement]) {
lpad = pad;
count++;
break;
}
}
pad++;
p <<= 1;
}
if (1 < count) continue;
foreach (index, v; piece[i]) {
if (v == -1) continue;
ans[v - 1] = (index + lpad + 1).to!int;
}
}
foreach (i, a; ans) {
write(a, i == ans.length - 1 ? '\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));
}
}
ピースの構築をうまくやる方法が思い浮かばず、かなり汚いコードになってしまいました。 初めてのdifficulty2000+のACです。わーい。
あまり関係ない話
本編はおしまいです。ここまで読んでいただきありがとうございます。 残りは参加記録を書くという建前がないと書けない、とるに足らない話を書きます。 物好きな人は読んでいってください。
1か月前くらいから累積和の変数をaccにすることに変えました。accumulateから来ています。
プログラムを書き始めたころからこういった微細な変化を積み上げてここまで来ましたが、積み重ねによりかなり原型から離れてきた実感があります。
いつか歴史を編纂したいなという野望だけがありますが、面倒くさいので多分やりません。
僕がAtCoderを始めた2022年11月あたりの提出を見てみると、今とはかなり異なるスタイルで書いていることがわかります。(言語も異なりますし。)
微細な変更つながりで言うと、今回のエントリからビッグオーを$O$ではなく$\mathcal{O}$に変更してみました。ちょっとかっこいいですよね。
しばらくkatexを書いているので、結構書き方に慣れてきました。私のkatexは基本的にMathJaxとMarkdownで可搬性のある数式を書くにはに沿うようにしています。これ実際すごくお勧めです。
最近僕のわがままで電通大競プロサークルの人を招集してバチャをやるという企画をやっています。 前回は昔からTwitterをフォローしてもらっているtetorapentagonさんに会ったり、PG battleでチームを組んだryotaさんと会ったりしました。 みなさんとても賢そうな印象でした。ずっとわけわからないことを言っている僕が浮いていないかすごく心配になります。 ともかく、皆さん参加ありがとうございます。また競技プログラミングの話をしましょう。
僕は結構Twitterを見ています。しかし、Twitterが僕に及ぼす悪影響が大きいなと思うことが多くなってきました。 競技プログラミングに関する話題によって精神的に参ってしまいそうになります。 少し距離を置こうと思います。 何に参ってしまいそうになるのかというと、やっぱり「隣の芝は青い」現象です。あまり詳細な言及は避けますが、自己肯定感がとんでもなく下がるような投稿が目についてしまい、苦しいです。 元来僕は謎に負けず嫌いであるというのもあり、精神的に良くないです。 これはレーティングシステムにも言える話です。最近、レーティングばかり気にする悪癖が再開している実感があります。1200にのるかどうかくらいの時もこういうことがありました。 これはレーティングというもの自体が抱える問題なので、簡単に避けるのは難しいです。しかし、レーティングはやはり価値評価の一側面でしかないということを念頭に置く必要があるでしょう。 ratismという単語がありますが、これは最もバカバカしいものであり、避けなければならない意識を持たねばなりません。 重要なのはレートではなく、より多くのアルゴリズム、データ構造についての知識をつけ、熟練することです。 僕の当面の目標は、拡張ユークリッド互除法の詳細な理解と、Treapの理論と実装を学ぶことです。 満足したらエントリにしたいです。気力が続けばですが。
大学が始まって1ヵ月くらい経ちましたが、結構忙しくてまいっています。参加記録を書くだけの精神的余裕がない原因のほぼすべてがこれです。 というわけで、また少しさぼってしまう見込みです。新しいエントリが出たときは何かを犠牲にしているかえらいかの2択になる見込みです。(実際、エントリを書くのって3時間くらいはかかるので…)
ではまた。