金魚亭日常

読書，ガジェット，競技プログラミング

AtCoder ARC #043 B - 最短路問題

AtCoder 競技プログラミング

B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder

距離が同じもの同士は，ペアの選び方が {}_nC_2 なので， 2^{{}_nC_2} 通り

距離 i から i+1 は ，距離 i+1 のそれぞれから 距離 i のそれぞれについてつなぐ・つながない 二通りあって，全部つながないというのを除くので，

距離 i が t 通り，距離 i+1 が s 通りあるとすると， (2^t - 1)^s 通り

Rubyで書いていて，2乗 の範囲を間違っていてREになってずっと考えていた．

Python は pow があって楽だった．

AtCoder ARC #044 B - 最短路問題

AtCoder ARC #043 B - 最短路問題

AtCoder ARC #042 B - アリの高橋くん

AtCoder 競技プログラミング

頂点の座標が O(0, 0), A(a, b), B(c, d) の三角形の面積 S は

\displaystyle S = \frac{|ad - bc|}{2}

（サラスの公式）

なので，点を原点まで平行移動した後，面積を求めて， 2 S を底辺の長さで割ると辺までの距離が出る．

AtCoder ARC #042 B - アリの高橋くん

AtCoder ARC #041 B - アメーバ

AtCoder 競技プログラミング

端の列を除いて，4近傍の最小値を取っていく． 値が決まったら，元の4近傍から値を引いておく．

解説は，上から順番に決めていく方式だった．

AtCoder ARC #041 B - アメーバ

AtCoder ABC #075 D - Axis-Parallel Rectangle

AtCoder 競技プログラミング Rust

最初，ユークリッド距離で近い順にK点選んで長方形を作る，ってやっていたけど，だめだった．

x座標とy座標それぞれソートしてから長方形を全部作り，K点以上含まれるかどうか判定する．

O(N^5) で，Ruby で書くとTLEだったので Rust．

AtCoder ABC #075 D - Axis-Parallel Rectangle