金魚亭日常

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

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

AtCoder ARC #040 B - 直線塗り

AtCoder 競技プログラミング

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

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

AtCoder ARC #040 B - 直線塗り

AtCoder ABC #075

AtCoder 競技プログラミング

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 - マス目と駒

AtCoder 競技プログラミング

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

メモ化全探索

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

AtCoder ARC #038 B - マス目と駒

AtCoder ARC #037 B - バウムテスト

AtCoder 競技プログラミング

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

Union Find でそれぞれの木を求め，深さ優先探索で閉路を検出し，閉路のないものの個数を出力．

AtCoder ARC #037 B - バウムテスト