脳log[20231108]

2023年11月08日 (水) [AtCoder] 精進。ABC212-F「Greedy Takahashi」(黄 diff)。問題選びは AtCoder Daily Training ALL 2023/11/8 による。自分の場合最終の I 問題だけが解かれていないというケースが最も多い。次に多いのは全問解かれている。だから水色までの人が対象になるのかな。２年以上前の ABC 本番では TLE に終わった問題が今ではどうか。■提出 #47384638 (AC / 1377 Byte / 1264 ms)。無事通りました。タイムラインに沿って高橋くんを移動させていけばいい問題。だけどうっかり Q 人の高橋くんを M 回移動させるわけにはいかないから、高橋くんの集団を移動させたい。一度合流した高橋くんは以降同じルートを辿る。集団と集団の合流に神経を使う。マージテクでもいいのかもしれないけど UnionFind で。集団から位置を、逆に位置から集団を引けるように追跡している。合流する集団と付随情報を同時に管理するのがたいへんややこしかった。■クラス名から判断するとダブリングで通している人もいる>提出 #24727196。その解法も一瞬考えたけど、１つ上の親、２つ上の親、みたいなのと違って何が倍々になるのかわからなくて捨てたのだった。今改めて検討すると、１つ目に乗る電車が何か、２つ目に乗る電車が何かで良さそう。電車が特定できれば発着時刻も発着場所も、必然的に次に乗ることになる電車も特定できる。あとは到着時刻 T(+0.5) が Z 未満である限りできるだけ多くのバスに乗るようにすればいい。今気がついたけど電車じゃなくてバスだった。変数名 Tr(ain) にしちゃった。■提出 #47398469 (AC / 619 Byte / 1357 ms)。これはダブリング解。NxTr 関数の 26 行目に条件式が(ループの中の更新条件と同じ式があらためて)必要だということに最後まで気がつかなかった。境界条件が難しい。