7K12 blog

猫でも分かる何か

ABC305に参加した感想


C問題もう少し早く解法に気づきたかった。アルゴリズムは数学的性質を使うことが多いので、もう少し数学的に処理する意識を持つべきだったように思う。


https://atcoder.jp/contests/abc305/submissions/42145904
まず、問題文を見た瞬間に任意マスの近傍8マスを調べたい気持ちになる。ただ、食べたマスの位置によって近傍8マスの状況が結構違うので場合分けが面倒そうという気持ちになる。かなり悩んだが、発想の転換して列と行の数に数学的性質があるのではということに気づく。食べたマスが1マスなので列と行の#の数が他に比べて-1されるので、それを調べれば答えが求まる。

D - Sleep Log


https://atcoder.jp/contests/abc305/submissions/42163265
累積和を取って二分探索して包除原理で計算する。方針はすぐに出てきたけど、バグらないよう細心の注意を払って実装する必要があり結構時間がかかった。ただ同レート帯での提出速度と比較すると同じくらいなので悪くない提出速度だったように思う。