脳log[20251018]

2025年10月18日 (土) [AtCoder] 今日は AtCoder Beginner Contest 428（Promotion of AtCoderJobs） があった。21 時数分前にスタンバイしてよそ見をしているうちにページ右下に表示される待ち時間が 30 分ちかくに増えていた。どうやら Codeforces ではよくあることらしいが AtCoder では初めて。■A 問題「Grandma's Footsteps」。これを書いている今問題名を読んでいる。おばあちゃんの足跡？足音？ 問題文中のゲームの説明を読むとだるまさんが転んだぽいので「だるまさんが転んだ 英語」で検索するとイギリスでの言い方らしかった(「だるまさんがころんだって英語でなんて言うの？ - DMM英会話なんてuKnow?」)。A+B 秒のかたまりがいくつあるかと余りと A の少ない方。かたまりには A を掛けて、両方に S を掛ける。AtCoder では秒と分を混ぜたような問題は出さないし、答えに単位も要求しない。■B 問題「Most Frequent Substrings」。何を答えるのかがとても難しい。わかれば全部分文字列を切り出してカウントするだけ。■C 問題「Brackets Stack Query」。( を +1、) を -1 として総和がゼロである必要があるんだけど、途中で負になることがあると壊れているので、累積和と同時に負になった回数もカウントした。■E 問題「Farthest Vertex」。最近 ADT で木の中心を扱う問題を解きました。これ「Diameter set」。過去に解いているにもかかわらず WA を４回も出して、それは直径を求めたあとで中心を求める手順が誤っていたのが原因だった。たぶん以前に解いたときも同じ間違いをして苦しんでいたような気がしないでもない。今日は３度目の正直で間違えなかった。直径の一端から遡る途中にあるのが中心。うっかりミスで WA を１回出しながら 50 分かけて実装したんだけど、解説には実装を簡潔にするアイデアが２つ書いてあって、前半はさすがに自分の提出と同じ構成だったけど、後半がとてもシンプルな実装だった。１つ目のアイデアが１未満の極小の長さを持つ辺と頂点を付け加える方法で、値が同じ場合に添字の大小で順番を付けるときに (値,添字) でペアを作ってソートする方法に似てる。実装で示された２つ目のアイデアは直径を探すときに N から逆順に端点を探して最初に見つかったものを優先することだった。ループの向きだけならどちらでも良くて、昇順にやるならあとから見つかった同等以上の頂点で上書きする。■D 問題「183184」。とても難しい。解法もよくわからないし、計算量がどうやって抑えられるのかもわからない。事前に平方数を列挙してプリフィックスで分類する？ 間に合わない。ルートで区間内にある平方数の個数を数える？ 区間が連続してないんだよね。プリフィックス(C) が邪魔だし、プリフィックスを取り除いたとき D+x の部分がゼロで始まっていてもいけない。E 問題を通したあとで桁数を固定することを思いついた。下限の桁数で区間の下限を、上限の桁数で区間の上限を特別扱いしたら、それ以外の区間では下限を C10..0 とし、上限を C99..9 とできる(たぶん)。テストケース数 30 万に桁数を掛けてルートの計算量を掛けると計算量が不安だけど他に手はない。上限と下限にイコールが付くかどうか、それに合わせて上限と下限に +1、-1 する必要があるかどうか、WA を出しながら修正して３度目の正直で WA が１減ってまだ WA×3 (#70271576)。マルチテストケースで７割 AC は 99 % 正解では？