| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | TLE |
全体感想
5完。Fは、1時間以上かけられる状況だったのに、正確な実装・高速化がしきれなかったです。少しバグはまると1時間なんてあっという間で…、短時間競技のプレッシャーになかなか対応できていないですね。
問題C – Prison
$N$枚のカードの情報を持って、毎回$L_i,L_i+1,\ldots,R_i$のカードに注目しようとすると、$O(N^2)$になってしまいます。結局条件を満たすのはある区間$[L,R]$なので、カードを全て持つ必要はない。2点だけ持つ方向性で考えると、自然と$O(N)$になります。
問題D – Integer Cards
小さい数の書き換えほど優先度が高い。大きい数への書き換えほど優先度が高い。ということに気づけば、大きい数を小さい方から書き換えていくという具体的手順が分かります。連番に同じ操作をするので、numpyのsliceで綺麗に書ける。
問題E – Cell Distance
対称性より全ての2点間の距離が同じ回数ずつ加算されることがすぐに分かります。これだけだと、2点の組が$O((NM)^2)$あってダメです。さらに$x$, $y$を分けて扱うことで、$x$座標の問題に専念します。
どのような$x$座標の差が何回出てくるのかを考えて立式。あとは小さい場合に検算をしながら式を作って実装。
せいぜい高校数学レベルですが、組み合わせの計算や数列の和の計算など数学要素が苦手な人にはやや難易度があったようで、Fが解けていてもEが解けていない人も割と居るみたいでした。
問題F – Absolute Minima
$\sum_{i}|x-a_i|$の最小値を求める問題。$|x-a|$が数直線における2点の距離に等しいことに注目すると、$x$が$\{a_1,a_2,\ldots\}$の中央値のときに最小値を与えることが分かります。
中央値を求めるだけならば、ソートして真ん中をとるだけなのですが、今回の問題では関数を書き換えながら求値クエリが降ってくるため、毎回ソートしていては間に合いません。動的に$a_i$を追加しながら、常に簡単に中央値が分かる仕組みを用意しておく必要があるというのが題意です。
これを実現するために、上側集合と下側集合を用意して、それぞれの元の個数が等しい（あるいは1の差）状態をキープしながら上下に挿入していきます。元の個数の差が2以上になったら上側から下側へ最小値をうつす……等々。
追加される数と、下側集合の最大値、上側集合の最小値の大小関係、また元の個数の差によって処理が細かく変わるため、場合分けの多い難しいコードを書いてしまいました。時間内に解消しきれず。
終了後に他の人のコードを見ていたら、ほぼ同じAC解を見つけました。必要があろうがなかろうが、とりあえず下側の最大値・上側の最小値を取り出して、追加する値と合わせて3つの元をソートしたあとで適切に上下に格納します。
上側・下側どちらかの更新の必要がないときも含めて3つを取ってきてソートして戻すという共通処理にすることで、バグも出にくく定数倍改善も試しやすい。
終了後ACにしたもの→■
