金魚亭日常

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

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

頂点の座標が  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 - アメーバ

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

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

AtCoder ARC #041 B - アメーバ

AtCoder ABC #075 D - Axis-Parallel Rectangle

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

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

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

AtCoder ABC #075 D - Axis-Parallel Rectangle

AtCoder ARC #040 B - 直線塗り

B: 直線塗り - AtCoder Regular Contest 040 | AtCoder

再帰でやると思ったが違っていた.

AtCoder ARC #040 B - 直線塗り

AtCoder ABC #075

Rating 変動なし

A

場合分け

B

爆弾の8近傍をプラス1していく

C

取り除く辺を決めて,Union Findして連結判定する

AtCoder ABC #075

AtCoder ARC #039 B - 高橋幼稚園

出来るだけ個数が均等に配る方が良い.

アメの個数が足りているときは,x を 余り x = K % N として

 {}_{N}C_{x}

足りてないときは,

 {}_{N + K - 1}C_{K}

(重複組み合わせ)

を出力.

AtCoder ARC #039 B - 高橋幼稚園

AtCoder ARC #038 B - マス目と駒

B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

メモ化全探索

こういうのは 最後の盤面の状態から決めて行くのがいいらしい.

AtCoder ARC #038 B - マス目と駒