最終的に塗られることは同値。いうことが分かります(証明も簡単)。座標集合は最終的に等しくなります。同値とした同値関係による商集合を考える発想になります。辺で結んだグラフを作って連結成分に分けることになります。ともにやってあげます。$y$座標どちらかが同成分に属するならば、2点が同一成分となるように連結成分を作っていきます。座標の成分になるのかを計算すると、塗られる点の個数が計算できます。同時に実装するような、ちょっとややこしい実装になりました。別世界で考えてしまったのがややこしさの原因であって、「2部グラフを連結成分に分割する」と思えば、より簡潔に実装できる気がしてきました。私にミスしやすい場所の多い実装だったので、具体的な絵を書いて照らし合わせながら進めました。与えられているサンプルは全部の点が同じ連結成分になるなど、極端なものばかりだったので、自分でサンプルを作って進めたことで安定して進められたと思います。PyPy]本問題はPyPyにすると遅くなった。個数などを数える処理を一緒にやろうとしているのも、ミスを増やす元になる。連結成分さえ出ればそこは後からでも計算量オーダーは変わらないので、一度に頭を使う量を減らした方がミスなく素早く実装できる。実行時間も、Python+PyPyの中では最短になりました。45分6完1ペナルティで31位でした。62分6完(1ペナルティ)で88位でした。86分6完(3ペナルティ)で45位でした。91分6完(3ペナルティ)で47位でした。36分6完1ペナで、64位でした。形式的べき級数解説pythonその他タイトルとURLをコピーしました。