torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

二分法

AtCoder Beginner Contest 341, D : Only one of two

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_d 問題概要 正整数 $n, m, k$ ($n \neq m $) が与えられる.正整数であって,$n, m $ のどちらか一方でのみ割り切れる数の内,小さい方から $k$ 番目のものを求めよ. 制約 $1 \leq n, m \leq 10^8$…

AtCoder Beginner Contest 324 F : Beautiful Path

問題文 https://atcoder.jp/contests/abc324/tasks/abc324_f 問題概要 $N$ 頂点 $M $ 辺の有向グラフ $G = ( V, E )$ があり,$i$ 番目 ($0 \leq i *1は頂点 $u_i$ から $v_i$ を結び,その「美しさ」は $b_i$ で「コスト」は $c_i $である. 頂点 $0$ から…

AtCoder Beginner Contest 299, D : Find by Query

問題文 https://atcoder.jp/contests/abc299/tasks/abc299_d 問題概要 長さ $N$ の秘密の列 $S = S_1 S_2 \dots S_N$ があり,$S_1 = 0$ かつ $S_N = 1$ かつ $S_i \in \{ 0, 1 \}$ である. $S_i$ を尋ねる操作を 20 回まで行える.$S_i \neq S_{ i + 1 }$ …

AtCoder Beginner Contest 267, E : Erasing Vertices 2

問題文 https://atcoder.jp/contests/abc267/tasks/abc267_e 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G$ が与えられ,頂点 $i$ には整数 $A_i$ が書かれている. ここで,一つの頂点を削除する以下の操作を $N$ 回繰り返すことでグラフを空にすることを…

AtCoder Beginner Contest 258, E : Packing Potatoes

問題文 https://atcoder.jp/contests/abc258/tasks/abc258_e 問題概要 $N$ 種類の荷物があり,種類 $i$ の重さは $W_i$ である. 今,荷物が無限に運ばれてきて,$i$ 番目 (0-indexed) の荷物の種類は $i \bmod N$ である.これらの荷物を次のように処理する…

AtCoder Beginner Contest 181, F : Silver Woods

問題文 https://atcoder.jp/contests/abc181/tasks/abc181_f 問題概要 二次元空間上に $N$ 個の点がある.$i$ 番目の点の座標は $( x_i, y_i )$ である. ここで,正の実数 $r$ を一つ決めて,位置 $( -10^9, 0 )$ に半径 $r$ の円を置く.その後,この円を…

AtCoder Beginner Contest 174, E : Logs

問題文 https://atcoder.jp/contests/abc174/tasks/abc174_e 問題概要 丸太が $N$ 本あり,$i$ 番目の丸太の長さは $A_i$ です. この丸太を,合計 $K$ 回まできることができるとき,最も長さい丸太の長さとして有り得る値の最小値はいくらか? 小数点以下を…

TopCoder SRM 681, Division 1, Level 1 : FleetFunding

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651 問題概要 $1$ から $M $ で番号付けられた $M $ 個のパーツを使って作られる機械がある.一つの機械は,$1$ から $M $ のパーツを一つずつ使って構成される. パーツは,…