torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 172, D : Sum of Divisors

問題文 https://atcoder.jp/contests/abc172/tasks/abc172_d 問題概要 正整数 $X$ について,関数 $f$ を $f( X ) = $ $X$ の約数の個数 とする. 正整数 $N$ が与えられるので,$$\sum_{ K = 1 }^{ N } K \times f( K )$$ を求めよ 制約 $1 \leq N \leq 10^…

AtCoder Beginner Contest 172, C : Tsundoku

問題文 https://atcoder.jp/contests/abc172/tasks/abc172_c 問題概要 本のスタックが 2 つあって,片方には $N$ 冊の本が,他方には $M $ 冊の本が積まれている.$N$ 札の本の内,上から $i$ 番目は読むのに $A_i$ 分かかり,$M $ 冊の本の内上から $j$ 番…

AtCoder Beginner Contest 172, B : Minor Change

問題文 https://atcoder.jp/contests/abc172/tasks/abc172_b 問題概要 英小文字からなる 2 つの文字列 $S, T$ が与えられる.$S$ の 1 文字を異なる文字に変更する操作を繰り返して $S$ を $T$ に一致させるとき,必要な操作回数の最小値はいくらか? 制約 $…

AtCoder Beginner Contest 171, D : Replacing

問題文 https://atcoder.jp/contests/abc171/tasks/abc171_d 問題概要 $N$ 項からなる正整数列 $\{ A_i \}$ がある.ここから,次の操作を $Q$ 回行う. $i$ 回目の操作では,値が $B_i$ である要素をすべて $C_i$ に置き換える それぞれの $i$ について,操…

AtCoder Beginner Contest 171, B : Mix Juice

問題文 https://atcoder.jp/contests/abc171/tasks/abc171_b 問題概要 相異なる $N$ 個の正整数からなる列 $\{ p_i \}$ が与えられる.ここから $K$ 項を選んで和を取るとき,和として有り得る値の最小値を求めよ. 制約 $1 \leq K \leq N \leq 1{,}000$ $1 …

AtCoder Beginner Contest 170, E : Smart Infants

問題文 https://atcoder.jp/contests/abc170/tasks/abc170_e 問題概要 $N$ 人の競技プログラマがいて,相異なる $1$ から $N$ の整数で番号付けされている.また,組織が $2 \times 10^5$ あり,同様に $1$ から $2 \times 10^5$ で番号付けされている.人 $…

AtCoder Beginner Contest 170, D : Not Divisible

問題文 https://atcoder.jp/contests/abc170/tasks/abc170_d 問題概要 長さ $N$ の整数列 $\{ A_i \}$ が与えられる.$A$ のインデックス $i$ であって,$i \neq j$ である任意の $A$ のインデックス $j$ について $A_j \not \mid A_i$ ($A_j$ が $A_i$ を…

AtCoder Beginner Contest 170, C : Forbidden List

問題文 https://atcoder.jp/contests/abc170/tasks/abc170_c 問題概要 整数 $X$ と長さ $N$ の整数列 $\{ p_i \}$ が与えられる.$p$ に含まれない整数であって,$X$ との差の絶対値が最も小さいものを求めよ.答えが複数ある場合は,値が最も小さいものを答…

AtCoder Beginner Contest 170, B : Crane and Turtle

問題文 https://atcoder.jp/contests/abc170/tasks/abc170_b 問題概要 庭に鶴と亀が何匹かずついる.鶴は $2$ 本の足をもち,亀は $4$ 本の足をもつ. 動物の総数が $X$ 匹であって足の総数は $Y$ であることがあり得るかどうか判定せよ. 制約 $1 \leq X, Y…

AtCoder Beginner Contest 169, C : Multiplication 3

問題文 https://atcoder.jp/contests/abc169/tasks/abc169_c 問題概要 整数 $N$ と実数 $B$ が与えられる.$A \times B$ の整数部分を出力せよ.なお,$B$ は小数点以下第 2 位まで与えられる. 制約 $0 \leq A \leq 10^{ 15 }$ $0 \leq B

AtCoder Beginner Contest 169, D : Div Game

問題文 https://atcoder.jp/contests/abc169/tasks/abc169_d 問題概要 正整数 $N$ が与えられる.$N$ に対し,以下の一連の操作を繰り返し行うことを考える. 以下の条件を満たす整数 $z$ を選ぶ ある素数 $p$ と正整数 $e$ で $p^e$ と書ける $z \mid N$ で…

AtCoder Beginner Contest 169, B : Multiplication 2

問題文 https://atcoder.jp/contests/abc169/tasks/abc169_b 問題概要 $N$ 項からなる整数列 $\{ A_i \}$ が与えられる.$\prod A$ を求めよ.ただし,値が $10^{ 18 }$ を超える場合は,代わりに $-1$ を出力せよ. 制約 $2 \leq N \leq 10^5$ $0 \leq A_i …

浮動小数点数の誤差に怯えながらも比較をしたい場合がある話

はじめに 最近出題された某問題の影響で,浮動小数点数の誤差について注目が集まっています.さて,あの問題では入力を受け取っただけ・乗算しただけで誤差が出るという話でしたが,幾何問題など,更に比較などの演算も行いたい場合があります.しかしながら…

AtCoder Grand Contest 044, B : Joker

問題文 https://atcoder.jp/contests/agc044/tasks/agc044_b 問題概要 $N \times N$ のグリッド状の盤面の各セルに人が $1$ 人ずつ,合計 $N^2$ 人いる.人は $1$ から $N^2$ の整数で,左上から row-oriented で番号付けされている. 入力でサイズ $N^2$ の…

AtCoder Beginner Contest 168, E : ∙ (Bullet)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_e 問題概要 $N$ 本のイワシがあり,$i$ 番目のイワシは 2 つのパラメータ $A_i, B_i$ をもつ.ここからイワシを一本以上選んでクーラーボックスに入れるが,イワシ $i$ と イワシ $j$ は,$A_i A_j …

AtCoder Beginner Contest 168, F: . (Single Dot)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_f 問題概要 平面上に,$Y$ 軸に平行な線分が $N$ 本,$X$ 軸に平行な線分が $M $ 本引かれている.$i$ 番目の縦線は 2 点 $( A_i, C_i )$ と $( B_i, C_i )$ を結んでいて,$j$ 番目の横線は 2 点 $…

AtCoder Beginner Contest 168, D : .. (Double Dots)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_d 問題概要 $N$ 頂点 $M $ 辺の連結な重み無し単純無向グラフが与えられる.各頂点に以下の条件を満たす「道標」を設定せよ. 道標は隣接する頂点を指す 道標が指す頂点への移動を繰り返すとき,頂…

AtCoder Beginner Contest 168, C : : (Colon)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_c 問題概要 長針の長さが $A$ ,短針の長さが $B$ で,$H$ 時 $M $ 分を指しているアナログ時計を考える(針は等角加速度で運動する). 2 つの針の先端同士の距離を求めよ. 制約 $1 \leq A, B \le…

AtCoder Beginner Contest 167, E : Colorful Blocks

問題文 https://atcoder.jp/contests/abc167/tasks/abc167_e 問題概要 正整数 $N, M, K$ が与えられる. 最初,$N$ 個のブロックが横一列に(隣接して)並んでいる.このブロックたちに色を塗りたい.次の条件を満たす色の塗り方を $\pmod{ 998244353 }$ で…

競技プログラマでも $O$-notation についてもうちょっとちゃんと考えたかった話

はじめに アルゴリズムの計算量を表現するツールとして,$O$-notation というのは競技プログラミングの文脈でもよく出てきます.その一方で,$O$-notation の導入が「ふわっ」と行われるケースはかなり多く,厳密に定義して導入する場面というのが実は少ない…

AtCoder Beginner Contest 165, D: Floor Function

問題文 https://atcoder.jp/contests/abc165/tasks/abc165_d 問題概要 正整数 $A, B, N$ が与えられる.$\mathrm{ floor }\left( \frac{ A x } B \right) - A ~ \mathrm{ floor }\left( \frac x B \right)$ の最大値を求めよ 制約 $1 \leq A \leq 10^6$ $1 \…

AtCoder Beginner Contest 166, D : I hate Factorization

問題文 https://atcoder.jp/contests/abc166/tasks/abc166_d 問題概要 正整数 $X$ が与えられる.$A^5 - B^5 = X$ となる整数 $A, B$ の組を一つ示せ.なお,解が存在するような $X$ のみが与えられる. 制約 $1 \leq X \leq 10^9$

AtCoder Beginner Contest 165, C : Many Requirements

問題文 https://atcoder.jp/contests/abc165/tasks/abc165_c 問題概要 $Q$ 個のクアドラプレット($4$ 要素タプル)が与えられる.$i$ 番目のクアドラプレットは $( a_i, b_i, c_i, d_i )$ である. また,整数 $N, M $ が与えられる.以下の条件を満たす数…

AtCoder Beginner Contest 119, C : Synthetic Kadomatsu

問題文 https://atcoder.jp/contests/abc119/tasks/abc119_c 問題概要 (原文が日本語かつ十分に簡潔なので省略)

TopCoder SRM 744, Division 1, Level 1 (Division 2, Level 3), ModularQuadrant

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=15236&rd=17373 問題概要 2 次元空間の第一象限(ちゃんと言うと,$\{ ( x, y ) \mid x, y \in \mathbb Z, x \geq 0, y \geq 0 \}$)を考える.これらの点の内,$c_1 \leq x \leq c_2, r…

CODE THANKS FESTIVAL 2017, H : Union Sets

やや無理やり通したので,釈明を残しておこうと思いました. 問題文 https://code-thanks-festival-2017.contest.atcoder.jp/tasks/code_thanks_festival_2017_h 問題概要 (原文が日本語かつ十分に簡潔なので省略)

競技プログラミングを始めて人生が変わった話

はじめに (少なくともブログ上では)お久しぶりです.この記事は,Competitive Programming (その2) Advent Calendar 2016 - Adventar の 14 日目の記事です. いわゆる思い出ポエムが流行って(?)いて,わたしも楽しく読ませてもらっています.人々の…

TopCoder SRM 684, Division 1, Level 1 : CliqueParty

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14171&rd=16688 問題概要 正整数の集合が次の条件を満たすとき,k-smooth であるとする. 任意の 2 要素 $A, B$ ($A \neq B$) について $A \leq kB$ 正整数の集合を表す配列 $a$ と正整…

GCDLCM2

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14169 問題概要 正整数の配列が与えられる.この配列に対し,以下の操作を任意回行う. 2 つの要素 $x, y$ を選ぶ $x, y$ を削除する $\mathit{ GCD }( x, y ), \mathit{ LCM }( x, y )$…

TopCoder SRM 681, Division 2, Level 2 : ExplodingRobots

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14137&rd=16651 問題概要 平面上に二つのロボットを置く.一つは座標 $( x_1, y_1 )$ に,他方は $( x_1, y_1 )$ に置く. 各ロボットは,$U, D, L, R$ からなる命令列 $\mathit{ instru…