D, Fが解けずに終了。Fで1caseTLEだったので粘ってしまったが、原因がよく分からず、結局TLEを除けなかった。
C - Digital Graffiti
あるマスが角の黒マスになるのは、ある頂点を見て、その周囲4マスのうち、「1マスが黒マス、または、3マスが黒マス」になるとき。
結構難しいと思う。結構すぐ思いつけて自分で驚いた。
D - Circle Lattice Points
誤差が重要な問題なので、X,Y,Rに予め$10^4$してから考える……というのは思いついた。
が、
・X=int(X*10**4)
としてたのがダメで、
・X=round(X*10**4)
のようにしたら通った。
X=0.0024のとき、X*10**4は23.999999999999996になるのですね。気を付けないと。
F - GCD or MIN
解法自体はツイートした通りであっていたのだけど、実装が悪かった。
kyopro_friendsさんのツイートの通りで、約数列挙とgcdを取るのを同時にやることで計算量が落ちる。（私は、ツイートを見る前に実装を見て、なるほど～、となった）
二つのパートを上手くマージすることで計算量が定数倍落ちることは結構あるけれど、オーダーが落ちることは結構珍しい気がする。
0 件のコメント:
コメントを投稿