| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
レートが2000を超えて、ABCコンテストはレートがつかなくなりました。
もともとレート目的ではなく勉強目的ですので、特に関係なく参加していきます。
65分で6完、65位でした。
全問題、考察の意味ではそれほど詰まらずに行けたと思いますが、順位はそれほどでもないですね。んー、E, Fそんなに速く解けない。減点もなく、十分な出来だったと思います。
問題C – Anti-Division
・$A$ 以上 $B$ 以下で適切なものの個数を求めよ
という出題では、
・$X$ 以下で適切なものの個数を求めよ
という関数 $F(X)$ を作成して、$F(B) – F(A-1)$とやってあげます。これはパフォーマンスが最適でない場合もありますが、せいぜい定数倍です。その分、求めるものが簡略化できますし、ひとつのコードを書くときに頭を使う量を減らせるため、ミスしにくくなるという利点があります。
計算には包除の原理 を使います。全体から、$C$, $D$の倍数それぞれの個数を除いて、公倍数の個数を求めます。最小公倍数の計算は、Euclidの互除法で行えます（参考：■）。
問題D – Megalomania
問題Dにしては易しいやつでしょうか。締切の早いタスクからこなすのが最善です。
現実世界でもこういう行動をしそうですね。
問題E – Friendships
・距離2がとても多い：1点を中心に置いて、他の点と結びまくった場合。
\[
(1,2), (1,3), (1,4), (1,5), (1,6)
\] のようなグラフ（スターグラフというそうです）。
・連結にするために少なくとも$N-1$ 本の辺が必要。
・その際に、距離 $1$ で確定する$2$ 点組が$N-1$ 個以上できてしまう。
で証明できました。次に考えたことは、「完全グラフから除外していく or スターグラフに足していく」です。スターグラフに1辺追加した場合を考えると、
・距離 $1$の組が新たに1つできる。
ということがすぐに分かります。それ以外に距離 $2$ の組が失われてしまう心配を数分していましたが、よく考えると、流石に辺上にない組は距離 $1$ にはならないですねｗ
問題F – Must Be Rectangular!
まずは、言われた通り点を生成してみることを一瞬考えますが、例えば入力例3 から、「worst case では $O(N^2)$ 個の点が増える」「したがって全生成というような方針は間違いなくTLE」ということが分かり棄却します。
とりあえず、入力例 3 を自分で手で書いた。なるほど$16$。気づきとして、
・$(a,y)$ と $(b,y)$ が現れる → $(a,t)$ が最終的に塗られることと $(b,t)$ が最終的に塗られることは同値。
ということが分かります（証明も簡単）。よって、$x$ 座標 $a$ と $b$ に対する $y$ 座標集合は最終的に等しくなります。このことから、このような$a$ と $b$ を同値とした同値関係による商集合を考える発想になります。グラフ理論でいうと、$a$ と $b$ を辺で結んだグラフを作って連結成分に分けることになります。
これを $x$, $y$ ともにやってあげます。ある2点に対して、その$x$, $y$座標どちらかが同成分に属するならば、2点が同一成分となるように連結成分を作っていきます。
最終的には、各連結成分に対して
・もともと描かれていた点がいくつあるのか
・最終的に、いくつの x / y 座標の成分になるのか
を計算すると、塗られる点の個数が計算できます。
Union Find Treeを$x$, $y$ 同時に実装するような、ちょっとややこしい実装になりました。もう少し簡潔に書けるのかな？
→ $x,y$ を別世界で考えてしまったのがややこしさの原因であって、「2部グラフを連結成分に分割する」と思えば、より簡潔に実装できる気がしてきました。
私にミスしやすい場所の多い実装だったので、具体的な絵を書いて照らし合わせながら進めました。与えられているサンプルは全部の点が同じ連結成分になるなど、極端なものばかりだったので、自分でサンプルを作って進めたことで安定して進められたと思います。
[Python vs PyPy]
本問題はPyPyにすると遅くなった。Union Find等の再帰が多い場合にそうなりやすい？
（追記）
・二部グラフ化
・そもそも連結成分をまとめる処理と $x,y$ の個数などを数える処理を一緒にやろうとしているのも、ミスを増やす元になる。連結成分さえ出ればそこは後からでも計算量オーダーは変わらないので、一度に頭を使う量を減らした方がミスなく素早く実装できる。
→ 書き直し：■
さらにscipy, numpyでスッキリ → ■
実行時間も、Python+PyPyの中では最短になりました。
