A一完。
コンテスト後のツイート
AtCoder Regular Contest 190 (Div. 1) Aはまあまあ速かったものの、Aしか解けず。
— titia (@titia_til) January 12, 2025
A 三回あれば操作可能。二回以下でできるか丁寧に場合分け。
B メモ化再帰でN^3程度の計算量にはなったが高速化できず。(a,b)が固定されているのをどう使えば良いのか……。
A - Inside or Outside
ACしましたが、after contestでWAが出ました。
ソートの仕方がまずくて、[a,b],[a,c]と、左端が同じものがあるとき、包含関係の判定がおかしかったのが原因でした。
本番中にWAが出ていたら気付くのに非常に苦労した気がする……。運が良かった。
B - L Partition
解説AC。解説放送も見ました。
コンテスト中に考えていた再帰では間に合わなそう、ということで、何か方針転換しなくてはいけなかったのだけど、そういうとき、二項係数を考えるのは定石の一つ。考えなくてはいけない方針でした。ただ、解法ツイートなどを見てそう言われても全然思い浮かばなかったので、解くのは厳しかったかもしれない。
また、二項係数の和を順に求めていくところも、（多分やったことはあると思うのだけど）記憶にありませんでした。
C - Basic Grid Problem with Updates
解説放送を見てAC。
コンテスト中、スタートとゴールからDPして、差分計算をどうにかすれば良い……というところまでは考えていた。
あとは、それらを用いて答えがどう表せるかが分かれば良かった。ただ、各クエリごとにmin(H, W)使って良いということにも気付いていなかったので、正解に近かったという感じではないが。
ただ、Bよりは惜しかった気がするので、こっちに集中すべきだったかもしれない。
D - Matrix Pow Sum
解説AC。解説放送も見ました。
難問に思えた。実験すればある程度分かるという意見も見たけど、あまり思いつきそうにないなぁ……。
ただ、解説放送で言及していたように、行列をグラフの経路数と見て行列の累乗をn歩進むときの行き方と捉える（たとえば、ここが参考になる）という考え方は身に着けておきたい。
特に、「隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数」である。
0 件のコメント:
コメントを投稿