torus711 のアレ

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

AtCoder Beginner Contest 187, F : Close Group

問題文 https://atcoder.jp/contests/abc187/tasks/abc187_f 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G = ( V, E )$ がある.このグラフをクリークで被覆するときの最小のクリーク数を求めよ*1. 制約 $1 \leq N \leq 18$ $0 \leq M \leq \frac{ N ( N …

AtCoder Beginner Contest 186, D : Sum of difference

問題文 https://atcoder.jp/contests/abc186/tasks/abc186_d 問題概要 $N$ 項からなる正整数列 $\{ A_i \}_{ i \in [ 0, N ) }$ が与えられる.$$\sum_{ i = 1 }^{ N - 1 } \sum_{ j = i + 1 }^N | A_i - A_j |$$ を求めよ. 制約 $2 \leq N \leq 2 \times 1…

AtCoder Beginner Contest 186, E : Throne

問題文 https://atcoder.jp/contests/abc186/tasks/abc186_e 問題概要 正整数 $N, S, K$ が与えられる.$S + xK \equiv 0 \pmod N$ となる最小の $x$ を求めよ. $T$ ケース処理せよ. 制約 $1 \leq T \leq 100$ $2 \leq N \leq 10^9$ $1 \leq S \leq N$ $1 …

AtCoder Beginner Contest 185, E : Sequence Matching

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_e 問題概要 長さ $N$ の正整数の列 $\{ A_i \}_{ i \in [ 0, N ) }$ と長さ $M $ の正整数の列 $\{ B_i \}_{ i \in [ 0, M ) }$ が与えられる.これらからいくつかの要素を取り除き(,残った要素を…

AtCoder Beginner Contest 185, D : Stamp

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_d 問題概要 $N$ 個のマスが一列に並んでいる.これらの $N$ 個のマスははじめ,白または青で塗られている.青色のマスは $M $ 個あり,それらの座標は数列 $A_i$ で与えられる(位置 $J$ について,…

AtCoder Beginner Contest 185, F : Range Xor Query

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_f 問題概要 長さ $N$ の正整数の列 $A$ について,以下の 2 種類のクエリが $Q$ 個飛んでくる.順に処理せよ. クエリ 1 : $A_{ X_i }$ を $A_{ X_i } \oplus Y_i$ で置き換える クエリ 2 : $\oplus…

AtCoder Beginner Contest 185, C : Duodecim Ferra

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_c 問題概要 長さ $L$ ($L$ は整数)の棒を $11$ 箇所で切断して $12$ 本の棒(各棒の長さは整数)を作ることを考える.切断の仕方は何通りあるか? 制約 $12 \leq L \leq 200$

AtCoder Beginner Contest 185, B : Smartphone Addiction

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_b 問題概要 バッテリー容量が $N$ [mAh] のスマートフォンを携帯し散歩をすることを考える(単位の話は Wikipedia 先輩に 任せる.面倒なので以降無単位量として扱う). 散歩の詳細は, バッテリー…

列挙問題と Reverse Search

はじめに 競技プログラマ的な視点で「列挙問題」について解説してみる,という記事です.競技プログラミング要素はこれだけです(ごめん).元々脈絡無く用意していた記事ですが,Competitive Programming (1) Advent Calendar 2020 の枠が変に空いていたの…

AtCoder Beginner Contest 184, F : Programming Contest

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_f 問題概要 $N$ 項の正整数列 $\{ A_i \}$ が与えられる.$A$ の部分列であって総和が $T$ 以下となるものの内で,総和が最大のものの総和はいくらか? 制約 $1 \leq N \leq 40$ $! \leq T, A_i \leq…

AtCoder Beginner Contest 184, E : Third Avenue

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_e 問題概要 $H \times W$ のグリッド状の迷路がある.空きマスは,単なる空きマスと,英小文字が書き込まれたものがある. 移動は 上下左右の隣接するマスへ移動する 現在地に書かれている文字と同…

AtCoder Beginner Contest 184, D : increment of coins

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_d 問題概要 金貨が $A$ 枚,銀貨が $B$ 枚,銅貨が $C$ 枚ある.いずれかの種類のコインが $100$ 枚になるまで以下の試行を繰り返す. コインを一様ランダムに選ぶ 選ばれたコインと同種のコインを …

AtCoder Beginner Contest 184, C : Super Ryuma

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_c 問題概要 グリッド状の無限に広い盤面の位置 $( r_1, c_1 )$ に駒が置かれている.この駒が位置 $( a, b )$ にあるとき,次の条件のいずれかを満たす位置 $( c, d )$ へ一手で動かすことができる…

AtCoder Beginner Contest 184, B : Quizzes

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_b 問題概要 クイズをしていて,正答で $+1$ 点,誤答は $-1$ 点が加算される.$0$ 点のときに誤答しても点数は負にはならない. 今 $X$ 点もっていて,この状態から続く $N$ 問の正誤判定が与えられ…

AtCoder Regular Contest 108, A : Sum and Product

問題文 https://atcoder.jp/contests/arc108/tasks/arc108_a 問題概要 正整数 $S, P$ が与えられる.$N + M = S, N \times M = P$ となる正整数 $N, M $ はあるか? 制約 $1 \leq S, P \leq 10^{ 12 }$

AtCoder Beginner Contest 183, F : Confluence

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_f 問題概要 $N$ 人の人がいて,人 $i$ はクラス $C_i$ に属している.以下の 2 種のクエリを処理せよ. クエリ 1 : 人 $a, b$ が含まれる集団が合流する クエリ 2 : 人 $x$ が属している集団で,ク…

Weighted-Union Heuristic

はじめに 界隈で「データ構造をマージする一般的*1なテク」と呼ばれている技法があります.``Introduction to Algorithms'' [1] では Data Structure for Disjoint Sets の章で ``Weighted-Union Heuristic'' として挙げられています. hatena diary の終了…

AtCoder Beginner Contest 183, E : Queen on Grid

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_e 問題概要 高さ $H$ ,幅 $W$ のグリッド状の盤面を考える.セル $( i, j )$ は空白か壁かのいずれかである. この盤面の位置 $( 1, 1 )$ に駒が置かれている.駒は,右,右下,下のいずれかの方向…

AtCoder Beginner Contest 183, D : Water Heater

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_d 問題概要 給湯器がひとつあり,毎分 $W$ リットルのお湯を出せる. 給湯器を使いたい人が $N$ 人いて,$i$ 番目の人は時刻 $S_i$ から $T_i$ まで($T_i$ 丁度は含まない),$P_i$ リットルのお湯…

AtCoder Beginner Contest 183, C : Travel

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_c 問題概要 $N$ 個の街があり,街 $i$ から街 $j$ へ移動するのにかかる時間は $T_{i,j}$ である. 街 $1$ を出発して,街 $1$ 以外のすべての街を丁度一度ずつ訪問してから街 $1$ に戻ってくるルー…

AtCoder Beginner Contest 183, B : Billiards

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_b 問題概要 二次元空間を考える.$X$ 軸は鏡面である. ここで,$( S_x, S_y )$ から光を発射して,鏡面に反射させ,$( G_x, G_y )$ に光を届けることを考える.鏡面にぶつかるときの $x$ 座標の値…

AtCoder Beginner Contest 182, C : To 3

問題文 https://atcoder.jp/contests/abc182/tasks/abc182_c 問題概要 各桁に $0$ が出現しない正整数 $N$ が与えられる.$N$ の桁を(全部ではなく)削除して得られる整数で $3$ の倍数を作るとき,削除する桁の最小数を求めよ. 制約 $1 \leq N \leq 10^{ …

AtCoder Beginner Contest 182, B : Almost GCD

問題文 https://atcoder.jp/contests/abc182/tasks/abc182_b 問題概要 $N$ 項からなる正整数の列 $\{ A_i \}$ が与えられる.$2$ 以上の整数であって,$A_i$ を割り切る $i$ の個数が最大のものを求めよ. 制約 $1 \leq N \leq 100$ $1 \leq A_i \leq 1000$

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 181, E : Transformable Teacher

問題文 https://atcoder.jp/contests/abc181/tasks/abc181_e 問題概要 奇数 $N$ について $N$ 個の正整数 $H_i$ と,$M $ 個の正整数 $W_i$ が与えられる.$W$ の要素を一つ $H$ に追加してからソートしたときの,隣接する奇数番目の要素と偶数盤面の要素の…

AtCoder Beginner Contest 181, D : Hachi

問題文 https://atcoder.jp/contests/abc181/tasks/abc181_d 問題概要 数字からなる列 $S$ が与えられる.$S$ を並べ替えて作れる文字列を整数として読んだとき,$8$ の倍数を作ることはできるか? 制約 $1 \leq |S| \leq 2 \times 10^5$

AtCoder Beginner Contest 181, C : Collinearity

問題文 https://atcoder.jp/contests/abc181/tasks/abc181_c 問題概要 2 次元空間上の点が $N$ 個与えられる.同一直線上に乗る 3 点はあるか? 制約 $3 \leq N \leq 10^2$ 点の座標は相異なる

AtCoder Beginner Contest 181, B : Trapezoid Sum

問題文 https://atcoder.jp/contests/abc181/tasks/abc181_b 問題概要 $N$ 個の正整数の対 $( A_i, B_i )$ が与えられる.$\sum_{ i = 1 }^N \sum_{ j = A_i }^{ B_i } j$ を求めよ. 制約 $1 \leq N \leq 10^5$ $1 \leq A_i \leq B_i \leq 10^6$

AtCoder Regular Contest 107, D : Number of Multisets

問題文 https://atcoder.jp/contests/arc107/tasks/arc107_d 問題概要 正整数 $N, K$ が与えられる.次の条件を満たす,有理数の多重集合 $S$ の総数 $\pmod{ 998{,}244{,}353 }$ で求めよ. $|S| = N$ $\sum_{ x \in S } x = K$ $x \in S$ は $\frac 1 { 2^…

AtCoder Regular Contest 107, C : Shuffle Permutation

問題文 https://atcoder.jp/contests/arc107/tasks/arc107_c 問題概要 $N \times N$ 行列 $a$ と整数 $K$ が与えられる.$a$ の要素は $1$ ~ $N^2$ の整数をちょうど一つずつ含む.ここで,次の 2 種類の操作を好きな順序で好きな回数行うことができる. 任…