😎

AtCoder Beginner Contest ABC428 解法メモ

2025/10/26に公開

Nim

AtCoder

tech

文中で使用しているのは、たとえCodonが使えようとも、同じくPythonライクでAtCoderに最適な言語の1つNimです

ABC428

ABC428A - Grandma's Footsteps

解法

$X$ のうち、 $A+B$ のセットがとれる分だけ、つまり、X div (A+B)だけ $S\times A$ 進み、
残り時間、つまり、X mod (A+B)（ただし、最大 $A$ ）だけ毎秒 $S$ メートルで進む、
と考えればよい
ACコード

メモ

怖くなって、時刻tを置いて、シミュレートした
ACコード

ABC428B - Most Frequent Substrings

解法

制約から、 $K$ を1..Nと変化させながら、出現回数を数えていき、
最大回数となった文字列をソートして答えればよい
c:Table[string,int]に出現回数を数えていけば、c.values.toSeqの最大値が $x$ となる
c.pairs.toSeqでvalueが $x$ のkeyを抽出してソートすればよい
ACコード

メモ

最後にソートし忘れてWA

ABC428C - Brackets Stack Query

解法

良い括弧列とは、
括弧列を"("を $1$ 、")"を $-1$ と読み替えた数列の累積和に、
途中にマイナスの項がなく、かつ、その最終項が $0$ になる状態を意味している
よって、累積和と、その累積和の途中にマイナスになる項があれば、その最初の位置を管理していけばよい
初項の $0$ をおいたDeque $s$ と、初めてマイナスになる位置を表す $p$ をマイナスになる項がない状態 $0$ とし、
クエリ $1$ であれば、
$s$ の最終項に"("なら $+1$ 、")"なら $-1$ した項を加え、
それが負になっていて、かつ、p==0ならp=s.len-1に更新
クエリ $2$ であれば、
s.popした上で、
s.len==pになっていたら、p=0に戻せばよい
クエリの都度、 $s$ の最終項が $0$ 、かつ、p==0かを判定して答えればよい
ACコード

メモ

クエリ $2$ でp=0に戻すときの条件を甘く書いてWA

ABC428D - 183184

解法

正整数 $x$ 以下の平方数の数は $⌊\sqrt{x}⌋$ で、 $0<x<y$ なる $x$ と $y$ の間の平方数の数は、 $⌊\sqrt{y}⌋-⌊\sqrt{x-1}⌋$ である
$x$ 、 $y$ 間が連続していればそうなるが、
この問題では $f(C,C+x)$ が、例えば1番目のテストケースなら $45,46,47,48,49,410,411,\dots$ となってしまう
そこで、 $C+x$ の桁毎に計算することを考える
$C+x$ が $2$ 桁なら $10～99$ の間、つまり、 $i$ 桁なら、 $10^{i-1}～10^{i}-1$ の間
そこに、 $C+1～C+D$ の条件を重ねればよいから、
C*10^i+max(10^(i-1),C+1)～C*10^i+min(C+D,10^i-1)の間の平方数を求めればよい
$i$ を $C+1$ の桁数から $C+D$ の桁数まで、つまり、( $(C+1)).len..($ (C+D)).len間で、
(C*10^i+min(C+D,10^i-1)).isqrt-(C*10^i+max(10^(i-1),C+1)-1).isqrtを足し合わせていけばよい
ここで、isqrtとは、整数平方根をニュートン法で求める方法で、.float.sqrt.intとしてしまうと小数の誤差でWAとなってしまう
ACコード

メモ

そもそも、正整数 $x$ 以下の平方数の数は $⌊\sqrt{x}⌋$ が浮かばない
isqrt（ニュートン法で整数平方根を求める方法）を知らない

ABC428E - Farthest Vertex

解法

木の各頂点からの最遠頂点を求めていく、という問題ゆえ、全方位木DPが有効である
最長距離と、その頂点番号を情報に持てば、
部分木のマージは最長距離が長い方とその頂点番号、同じなら、頂点番号の大きい方とすればよく、
自身から子への辺移動は、最長距離に $1$ を足せばよい
まずは頂点 $0$ を根にDFSをして
dp[頂点 $u$ ][ $i$ 番目の部分木]= $i$ 番目の隣接頂点を根とした情報(最長距離,頂点番号)を求めておき、
その上で、初めに $0$ とした根をDFSの遷移でずらしていきながら、そのすべての部分木の情報を求めていくが、これは、親頂点での情報と、各部分木の根の情報の左累積和と右累積和を使うことで、合成して算出することができる
その過程で、各頂点のすべて部分木の情報をマージした情報から、その頂点からの距離が最大となる頂点の番号を記録していけばよい
ACコード
 全方位木DPライブラリ

メモ

最遠点からの最遠点で木の直径が求まる、というが、その感覚がつかめない
この機会に全方位木DPに触れる

反復学習にはmochiがおすすめ
全問入ったdeckはこちら