ABC428 （2025/10/18）
〇A問題
まーす.icon 愚直にfor文で高橋君の動作を記述．
Kaplam.icon毎秒走ってるか調べた
wataumi.iconprint((X//(A+B) * A + min((X % (A+B)), A))*S)
21:30スタートだったので遅刻せずに参加できた。
N_N.icon1つの式で解くことに拘って無駄に時間をロス．式はwataumi.iconさんと同じ．
CarpDay.iconwataumi.iconさんと同じ内容を複数行で実装．
〇B問題
まーす.icon $ Sの長さ$ Kの連続部分列をdictで数え挙げる．
Kaplam.iconスライスでとる感じ
wataumi.icon読み飛ばしてて、長さ K以下の文字列と勘違いしていました。
N_N.icon 辞書順に出力するを読み飛ばしててWAを一回食らう．解法は，まーす.iconさんと同じ．
CarpDay.iconWAまで含めて，N_N.iconさんと同じ（^^;
N_N.icon 出力例の順序を勝手に脳内で入れ替えて合ってると判断し，投稿しちゃいました．．．
〇C問題
Kaplam.iconかっこ列を満たさなくなった場所を覚えておく的な
まーす.icon stackの問題．())のように(の数よりも))の数が多いと，それ以降に何を追加しても良くない括弧列であることが，この問題のキモだと思った．
まーす.icon 今気が付いたのだけれど，問題文にも書いてあったね．
wataumi.icon同上
N_N.icon (の出現数から)の出現数を引いた数と，その数がマイナスになった回数をそれぞれスタックで覚えるようにした．両方の数が0になったときが良い文字列．
CarpDay.icon Kaplam.iconさんと同じっぽい
〇D問題
Kaplam.icon下に置く数字が桁上がりするタイミングを見てisqrtで挟むみたいな ここまでで瞬間320位ぐらいだった
まーす.icon 難しい......．制約的にひとつのテストケースに対して，$ O(1)とか位しか許されないと思うのだが......
wataumi.iconint → strの型変換で桁数 llen() を把握
N_N.icon 解き方は多分合ってると思うけど，WA×4から減らせなかった．．．考え方は，Kaplam.iconさんと同じだと思うんだけど，式とか境界値とかをきちんと考えるのがしんどかった．
CarpDay.iconまーす.iconさんと同じ考察で手も足も出ず．
CarpDay.iconE問題とは異なり，何も降りて来なかったので上の伏字をチラ見する．ああああ．個数を求めるだけなのだからそれで良いよね．．．素直にAC．
〇E問題
Kaplam.iconごりごりに重実装してたけど出した後にWAケースに気付いた、見てみるとやたら通してる人が多かったので木の直径の端っこから探索して長い方とかでそういや出来なかったっけ？ と思い出して出したもののWA、まぁそんな簡単なわけないか～と思って今解説を見て一番大きい頂点の条件入れ忘れてたことに気付いて今倒れています_(:3」∠)_
Kaplam.icon↑なおして通ったわふぁっきゅー、17WAも出やがって_(:3」∠)_
wataumi.iconどんまい、そもそも入力例２がWAになるのでは？
wataumi.iconなるほど、私は入力例２がWAになって気づいた人なので（運がよかった？）
まーす.icon 使ったアルゴリズム：多始点BFS
まーす.icon 具体的な考え方：頂点$ 1と距離が最大となる頂点の集合のうち，添え字が最大のものを$ kと置く．同様に頂点$ k と距離が最大となる頂点の集合と$ kのうち，添え字が最大のものを$ u，その次に添え字が大きい頂点を$ vとする．このとき，頂点$ i \ (i = 1, 2, \dots, N)に対する解の候補は，$ uか$ vであるから，これを多始点BFSによってさらに解を絞り込む．
wataumi.icon木の (直径) := (木に含まれる頂点のうち最も離れている 2 頂点の距離) を利用
CarpDay.icon 木の直径求めるためにDFS2回行うことまでは想定内だったけど，直径の逆側からもう1回DFSして遠い方を取る発想がなかった．各点へ行くには直径上のどの点から行くことになるのか，という情報を保持して何とかACにしたけど，その方法の方が圧倒的にスマート．コンテスト中に思いつくなんてすごいなぁ．横浜の本番，楽しみだ！
CarpDay.icon無茶苦茶時間かかってゴリゴリに実装（自分の子孫の子供のうち最も深い点と2番目に深い点をを保持するみたいな）するも，WAくらってからWAケースに気付いてお手上げ．本日お疲れだったのでUnratedにしておいたけど，それでも残念．D問題もE問題も解説見ようか悩みつつ，明日まで我慢することにする．
CarpDay.icon木の直径を考えたら単純では？と就寝前に枕元でお告げがあったので，翌日起床してハンドシミュレーション．入力例のサイズが小さいのは，解法がシンプルなのばれないようにするためだったのね．問題なさそうだったので実装するもTLE．再帰をキュー型に変更したらAC．「PyPyだから再帰遅いの忘れてたよ．CPythonなら再帰でも通る？」としたら，却ってTLEケース増える．．．もう再帰でもPyPyの方が速い？
CarpDay.icon解説見たら，上記の再帰の話書いてあったね．今後はcodon使うこと前提で問題作ってくる？？
〇F問題
〇G問題