ABC408参加記録
Published on 2025-06-03Last Modified 2025-06-03
Table Of Contents
まえがき
TOUPC001に参加してきた を公開してからすでに1カ月経過したらしい。 あの時から今日までに、ここに書こうか迷っていた面白い出来事はいくつかあった。 しかし、如何せん全てへのやる気が失われていたため放置されていた。
少なくとも1カ月に1本くらいの更新はしたいと思っているので、（割と成功回だったということもあり）直近のABCの参加記録を久しぶりに書いた。
相も変わらず AtCoder Beginner Contest408 に参加してきた。 解けた問題について、考察と解法を軽く説明する。
A - Timeout
解法
肩をたたかれてから$S + 0.5$秒経過で寝るので、ある肩たたきから次の肩たたきまでの時間を見ていけばよい。 この時間は単に引き算で求めることができる。 $0$秒時点で肩たたきをしていることに注意。
import std;
void main () {
int N, S;
readln.read(N, S);
auto T = readln.split.to!(int[]);
T = 0 ~ T;
bool ok = true;
foreach (i; 0 .. N) {
if (S < T[i + 1] - T[i]) {
ok = false;
}
}
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 - Compression
解法
いくつかやり方はあるが、std::uniqueのような関数を使うのが楽だろう。
std::unique
$A$の値域が小さいので、バケットを用意するのもアリだと思う。
どう考えて解くか？については特になくて、このような処理は頻出なのである程度やり方を覚えているとしか言いようがない気がする。
import std;
void main () {
int N = readln.chomp.to!int;
auto A = readln.split.to!(int[]);
A = A.sort.uniq.array;
writeln(A.length);
writefln("%(%s %)", A);
}
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 - Not All Covered
解法
壊す城壁を決め打ちしたときのことを考えてみると、その城壁がいくつの砲台に守られているかがわかればよい。 守っている砲台の数を城壁ごとに探すとそれぞれに対して$\Theta (M)$時間が必要なので、ここをどうにかするのが問題になる。
城壁ごとに独立に考えるのではなく、各城壁がいくつの砲台に守られているかを一括で管理することにすると、典型アルゴリズムが適用できる形に帰着できる。具体的には、
- 区間$[L _ i, R _ i]$に$+1$
- 最小値を出力
とすればよい。 詳しいことは別途調べてほしいが、offline区間加算はimos法というアルゴリズムにより実現できる。
この手の「個別に考えると厳しいが、一括でシミュレートすると耐える」みたいな問題はよくあるので、各ケースで解くのが難しいときは検討してみても損はないと思う。（偉そうに講釈垂れているが、 ABC389F で私もやらかしている。）
import std;
void main () {
int N, M;
readln.read(N, M);
auto L = new int[](M);
auto R = new int[](M);
foreach (i; 0 .. M) {
readln.read(L[i], R[i]);
}
// imos
auto imo = new int[](N + 10);
foreach (i; 0 .. M) {
imo[L[i]]++;
imo[R[i] + 1]--;
}
foreach (i; 0 .. N + 9) {
imo[i + 1] += imo[i];
}
int ans = int.max;
foreach (i; 1 .. N + 1) {
ans = min(ans, imo[i]);
}
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 - Flip to Gather
解法
$\Theta (N ^ 2)$は簡単だが、そこから落とすのが結構大変そうな印象を受けた。
最終的に残す1たちにおいて、もともと1だったものを0に変更しても得しない。したがって、1の列を2つ選択して、隙間の0を反転させると考えてよい。 $o(N ^ 2)$時間に改善するならどちらか片方を固定したときにもう片方を$o(N)$時間で選択できるようにアルゴリズムを設計するという方針になりそう。
連続部分列の問題なので、多分右側固定して変数分離に近いことをやるんだろうなと思いつつ、この方針でできるか不安だったので別の方針を考えてみる。
最終的に00…11…00…のような文字列になるので、先頭から文字を確定させていく過程で、どのような割り当てをしたとしても、
- まだ残すべき1の列に到着していない
- 残すべき1の列に到着している
- 残すべき1の列を抜けたあと
の3状態しか取れない。 そこで、次の動的計画法を行う。
dp[i][j] = 先頭i文字の割り当てを確定させて、状態がjになるような最小の変更数
一般に耳dpと呼ばれるタイプのdpらしい。 運よくこれが見えたのでこれをやったが、別方針が見えなければ+10分はかかったと思う。
import std;
void main () {
int caseNum = readln.chomp.to!int;
auto ans = new int[](caseNum);
foreach (caseid; 0 .. caseNum) {
int N = readln.chomp.to!int;
string S = readln.chomp;
auto T = new Tuple!(int, int)[](0);
int l = 0, r = 0;
while (l < N) {
while (r < N) {
if (S[l] != S[r]) {
break;
}
r++;
}
T ~= tuple(S[l] - '0', r - l);
l = r;
}
const int M = T.length.to!int;
auto dp = new int[][](M + 1, 3);
foreach (d; dp) {
d[] = int.max / 2;
}
dp[0][0] = 0;
foreach (i; 0 .. M) {
// 維持 or 進む
if (T[i][0] == 0) {
dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + T[i][1]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + T[i][1]);
dp[i + 1][2] = min(dp[i + 1][2], dp[i][2]);
dp[i + 1][2] = min(dp[i + 1][2], dp[i][1]);
}
else {
dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + T[i][1]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][1]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][0]);
dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + T[i][1]);
dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + T[i][1]);
}
}
ans[caseid] = min(dp[M][0], dp[M][1], dp[M][2]);
}
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));
}
}
連長圧縮が必要だと思っていたがいらなかった。（連長圧縮しても正しい結果を返すので別にしてもよい。）
E - Minimum OR Path
解法
一見ダイクストラで通りそうだが、サンプル2で落ちる。 これは最小化のために一旦上位bitを取るべき場面が存在するからである。 なので違う方針を考える。
例えば、$1$から$N$を結ぶパスであって、29bit目を埋めないようなものが存在したとする。 このパスは29bit目を埋める任意のパスよりも小さくなる。
これは2進数だと非自明に思うかもしれないが、10進数で考えると当たり前に感じるだろう。 1*は*にどんな数が入ろうとも20より小さいということだ。
だから、最上位bitを使わなくても$1$と$N$の連結性が保てる場合、最上位bitを使ってはいけないということになる。 あとは「重みの最上位bitが0であるような辺集合」に対して最上位のひとつ下のbitで同じことをやって使える辺集合をどんどん削っていけばよい。
発想自体は極めて自然なため、もしかしたらDの方が難しいかもしれない。（どっちも同じくらい苦戦した。）
import std;
void main () {
int N, M;
readln.read(N, M);
auto u = new int[](M);
auto v = new int[](M);
auto w = new int[](M);
foreach (i; 0 .. M) {
readln.read(u[i], v[i], w[i]);
u[i]--, v[i]--;
}
// 上の桁から貪欲に決めていけばよさそう。
// lo[i] := ibit目がlo[i]以下の辺なら使っていいよ。
auto lo = new int[](30);
lo[] = 1;
auto q = DList!(int)();
auto vis = new bool[](N);
foreach_reverse (dig; 0 .. 30) {
// lo[dig]を0に設定できるかチェック
lo[dig] = 0;
auto graph = new int[][](N);
foreach (i; 0 .. M) {
bool ok = true;
// 判定
foreach (j; 0 .. 30) {
int b = (w[i] & (1 << j)) == 0 ? 0 : 1;
if (lo[j] < b) {
ok = false;
}
}
if (ok) {
graph[u[i]] ~= v[i];
graph[v[i]] ~= u[i];
}
}
vis[] = false;
vis[0] = true;
q.insertBack(0);
while (!q.empty()) {
auto pos = q.front();
q.removeFront();
foreach (to; graph[pos]) {
if (!vis[to]) {
vis[to] = true;
q.insertBack(to);
}
}
}
if (!vis[N - 1]) {
lo[dig] = 1;
}
}
int ans = 0;
foreach (i; 0 .. 30) {
ans |= lo[i] << i;
}
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));
}
}
F - Athletic
解法
自分より高い足場に飛び移れないため、自由度が低い方から考えると筋がよさそうに見える。以後、低い足場から決めていく方法を考える。 まず、高さ1の足場はどこへも飛び移れないことがわかる。
高さが1でない足場は、高さがより小さい足場のどれかに移動することになる。だから、各足場から移動できる最大値がわかっていれば確定させられそうだ。 この集約はしんどそうだが、データ構造に載りそうな雰囲気を感じる。
ここで高さ$i$の足場から飛び移れる回数の最大を「$H$において$i$があった場所」に代入しておく。 このとき、今決めようとしている値以外は全て確定値が入るので、更新がrange maximum queryに帰着できる。 セグメント木が使えそうだ。
ところでもう一つの制約「差がD以上でないといけない」があるが、これはrange maximum queryの対象に入る時刻をずらしてやればよい。 例えば高さ$x$の足場の情報が確定したとき、すぐに反映させるのではなく、キューなどに積んでおいて高さ$x + D$の足場を確定させる直前に反映させてやればよい。
これで全ての不安点が解消された。
余談だが、このタイプの列への載せ方を「位置ベース」と呼んでいる。一方、$i$番目に値$i$に関する情報を載せる「値ベース」もある。
import std;
void main () {
int N, D, R;
readln.read(N, D, R);
auto H = readln.split.to!(int[]);
auto rmq = new SegmentTree!(int, (int a, int b) => max(a, b), () => -int.max)(N);
auto ord = iota(N).array;
ord.sort!((a, b) => H[a] < H[b]);
auto q = DList!(Tuple!(int, int))();
foreach (i; ord) {
// 今の高さを見てセット
while (!q.empty() && H[q.front()[0]] + D <= H[i]) {
auto top = q.front();
q.removeFront();
rmq.set(top[0], top[1]);
}
int lo = max(0, i - R);
int hi = min(N, i + R + 1);
int v = max(-1, rmq.prod(lo, hi));
q.insertBack(tuple(i, v + 1));
}
foreach (item; q) {
rmq.set(item[0], item[1]);
}
writeln(rmq.prod(0, 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));
}
}
// segment tree省略
あとがき
6月は何本か更新したい。