2021-09-17

ICPC国内予選2020 B問題：接触追跡

問題. 接触追跡

あるアプリを利用している人が $m$ 人いる。その中で $p$ 番目の利用者は感染者である。時刻順に濃厚接触の記録が $n$ 件与えられる。 $i$ 番目の記録 $a_i \neq b_i$ は $a_i$ 番目と $b_i$ 番目の利用者が濃厚接触したことを表している。感染者と直接的または間接的に感染した疑いのある利用者の総数を求めよ。

制約： $1 \le m \le 100$ 、 $0 \le n \le 1,000$

2021-09-17

ICPC国内予選2020 C問題：荷物

競プロ-ICPC アルゴリズム-探索

問題. 荷物

正整数 $p$ が与えられる。正整数 $w, d, h$ で $p = w \times d \times h$ を満たすもの中で $w + d + h$ の最小値を答えよ。

制約： $1 < p < 10^{15}$

2021-03-06

Visual Studio での競技プログラミング管理方法

環境-ツール競プロ

Visual Studio を使った競技プログラミングの始め方について紹介したいと思います．

（追記）競プロなどの手軽な環境としては Visual Studio Code を使用するのがベストだと思います（この記事の存在意義は...）．

2020-10-27

Visual Studio で Ubuntu ライクな競プロ環境

環境環境-ツール

概要

今まで競プロを Ubuntu 上でテキストエディタは Spacemacs でコンパイラは gcc でコマンドライン
から参加していました．最近とあることから Windows に改宗して開発環境を Visual Studio にしたため競プロから離れていました（本当は違う理由）．改宗しても今まで慣れ親しんだ環境が忘れられなく Windows 上で近い環境を構築したのでメモを残します．

2019-08-01

円板と多角形の共通部分の面積

アルゴリズムアルゴリズム-計算幾何アルゴリズム-紹介競プロ競プロ-AOJ

問題. Circles - Intersection of a Circle and a Polygon

平面上の単純多角形 $P$ と円板 $C$ が与えられる．このとき， $P \cap C$ の面積を求めよ．

単純多角形とは自己交差していない多角形で， $P$ は $P$ の頂点を反時計回りに訪れた頂点の列 $(p_1, p_2, \ldots, p_n)$ で与えられ， $p_i$ の座標を $(x_i, y_i)$ で表す．
また，円板 $C$ は中心 $c$ で半径 $r$ としたとき $C = \{ \|p - c\| \le r \mid p \in \mathbb{R}^{2} \}$ を満たす領域である．