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} \}$ を満たす領域である．

制約： $3 \le n \le 100$ ，　 $1 \le r \le 100$ ，　 $-100 \le x_i, y_i \le 100$

2019-07-23

2進数で有限小数となる10進有理数

数学数学-数値計算

10進法で表記した有理数を2進法の小数で表記したときに，有限の桁数で表すことができる有限小数になるための特徴付けを与える．この応用として10進法で表記した有限小数が計算機上で誤差を含む数値かどうかの判定ができる．

2019-07-21

ABC134 F問題：Permutation Oddness

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-動的計画法

問題. Permutation Oddness

$\{1, 2, \ldots, N\}$ の順列 $p$ の奇妙さを $\sum_{i = 1}^N |i - p_i|$ と定義する．奇妙さが $K$ であるような順列が何通りあるか答えよ．

制約： $1 \le N \le 50$ ，　 $0 \le K \le N^2$

2019-07-21

ABC134 E問題：Sequence Decomposing

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-動的計画法

問題. Sequence Decomposing

長さ $N$ の非負整数列 $a = (a_1, a_2, \ldots, a_N)$ が与えれられる．各要素を色で塗ることを考える．ただし，同じ色で塗られたどの 2 要素 $a_i$ と $a_j \, (i < j)$ に対しても $a_i < a_j$ が成り立つように塗る．このような塗り方の中で使用した色の種類の最小値を答えよ．

制約： $1 \le N \le 10^5$ ，　 $0 \le a_i \le 10^9$

2019-07-20

ICPC国内予選2019 C問題：天秤

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

問題. 天秤

$n$ 個の薬品と $m$ 個の分銅の重さが与えられる． $i$ 番目の薬品の重さは $a_i$ で， $j$ 番目の分銅の重さは $w_j$ である．すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ．ただし，釣り合わないときは任意の重さの分銅を 1 つだけ追加することができる．追加して釣り合うことができる分銅が複数ある場合は重さが最小のものを答えよ．

制約： $1 \le n \le 100$ ，　 $1 \le m \le 10$ ，　 $1 \le a_i \le 10^9$ ，　 $1 \le w_i \le 10^8$