アルゴリズム

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

問題. Circles - Intersection of a Circle and a Polygon 平面上の単純多角形 と円板 が与えられる.このとき, の面積を求めよ.単純多角形とは自己交差していない多角形で, は の頂点を反時計回りに訪れた頂点の列 で与えられ, の座標を で表す. また…

ABC134 F問題:Permutation Oddness

問題. Permutation Oddness の順列 の奇妙さを と定義する.奇妙さが であるような順列が何通りあるか答えよ.制約: ,

ABC134 E問題:Sequence Decomposing

問題. Sequence Decomposing 長さ の非負整数列 が与えれられる.各要素を色で塗ることを考える.ただし,同じ色で塗られたどの 2 要素 と に対しても が成り立つように塗る.このような塗り方の中で使用した色の種類の最小値を答えよ.制約: ,

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

問題. 天秤 個の薬品と 個の分銅の重さが与えられる. 番目の薬品の重さは で, 番目の分銅の重さは である.すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ.ただし,釣り合わないときは任意の重さの分銅を 1 つだけ追加するこ…

ARC016 C問題:ソーシャルゲーム

問題. ソーシャルゲーム 種類のカードと 種類のくじがある. 番目のくじを引くのにかかる費用は で,くじを引いたときに得られるカードの集合を とする.また, 番目のくじを引いて 番目のカードが当たる確率を とする. 最適な戦略でくじを引いて全種類のカ…

ABC133 C問題:Remainder Minimization 2019

問題. Remainder Minimization 2019 非負整数 が与えられる. を求めよ.制約:

ABC132 F問題:Small Products

問題. Small Products 正整数からなる長さ の数列で,隣り合うどの 2 要素の積も 以下となるものが何通りあるか求めよ.制約: ,

ABC132 E問題:Hopscotch Addict

問題. Hopscotch Addict 有向グラフ と,頂点 が与えられる. から への移動回数の最小値を求めよ.ただし,任意の頂点 からの 1 回の移動とは, から距離がちょうど 3 離れた頂点へ移動することである(弧重みは 1).また, から へ移動することができない…

ABC132 D問題:Blue and Red Balls

問題. Blue and Red Balls 個の青いボールと 個の赤いボールがある.この 個のボールを一列に並べたものを としたとき, から青いボールが無くなるまで次の操作を行う. の中にある連続する青いボールの部分列を任意に取り除き,取り除いてできた列を とする…

ARC055 B問題:せんべい

問題. せんべい 1 から までの番号が付けられた 枚のせんべいが一様ランダムに並べられている.このせんべいを先頭から順番に食べるかどうかを選び最大で 枚を食べる. 番目のせんべいを食べるかどうか決めるときに, 番目のせんべいの番号は分からないが, …

ABC131 F問題:Must Be Rectangular!

問題. Must Be Rectangular! 平面上に 個の点があり, 番目の点の座標は である. のうち3点が存在するときに残りの1箇所に点を追加するという操作を行う.最大でこの操作を何回行えるかを求めよ.制約: ,

ABC131 E問題:Friendships

問題. Friendships 非負整数 が与えられたとき次を満たすグラフを構成せよ.ただし,そのようなグラフが存在しない場合は "-1" を出力せよ. 頂点数 の単純連結無向グラフ 辺重みは 1 最短距離が 2 である頂点対 の数がちょうど 個 制約: ,

ABC130 F問題:Minimum Bounding Box

問題. Minimum Bounding Box 平面上に 個の点がある.時刻 0 のときの 番目の点の座標を とする.各点は時刻 0 から秒速 1 で決まった方向に同時に動き出す.ただし,動く方向は軸並行に左右上下のいずれか一方向のみである(または動かない).ある時刻での…

ABC130 E問題:Common Subsequence

問題. Common Subsequence 長さ の整数列 と長さ の整数列 が与えられる. と の等しい部分列が何通りあるか求めよ.制約: , と の各要素は 1 以上 以下

ARC129 F問題:Takahashi's Basics in Education and Learning

問題. Takahashi's Basics in Education and Learning 初項 と公差 からなる長さ の等差数列 がある.この等差数列を一列に並べたものをひとつの整数として見たときの による剰余を答えよ.制約: , , 等差数列の要素はすべて 未満

ABC129 E問題:Sum Equals Xor

問題. Sum Equals Xor 正整数 が二進表記で与えられる.次の条件を満たす非負整数の対 がいくつあるか求めよ. ・ ・ 制約: ( の先頭文字は必ず 1 )

M-SOLUTIONS プロコンオープン D問題:Maximum Sum of Minimum

問題. Maximum Sum of Minimum 頂点からなる木 と,正の整数 が与えられる.全単射 のスコアを各辺 に対して の総和とする.スコアを最大とする全単射を求めよ.制約: ,

ARC014 C問題:魂の還る場所

問題. 魂の還る場所 赤青緑の3色からなる 個のボールが1列に並んでいる. 番目の色は である.1番目のボールから順番に円筒の左側か右側の好きな方向から入れる.同じ色が2個並ぶとそれらのボールは消える.すべてのボールを入れた後に円筒に入っているボー…

ARC009 C問題:高橋君,24歳

問題. 高橋君,24歳 写像 で となるものが何通りあるかを (素数)で割った余りで答えよ.ただし, とする.制約: ,

ARC008 C問題:THE☆たこ焼き祭り2012

問題. THE☆たこ焼き祭り2012 時刻 0 に 1 番目の人から 番目の人へたこ焼きを1つ渡すことを考える. 番目の人は平面上の にいて,受け取る速度の上限が で,渡す速度の上限が である.たこ焼きの受け渡しはいくつかの人を経由してもよいが,すべての人に対し…

ARC006 C問題:積み重ね

問題. 積み重ね 個のダンボールがある.ダンボールは 1 から N まで番号付けされており, 番目のダンボールの重さは である.1番目のダンボールから順番に部屋に収納する.このとき, に対して なら 番目のダンボールの上に 番目のダンボールを重ねることが…

メモ:競プロで使う C++

競プロで使う C++ の STL の雑多なメモ

ABC128 E問題:Roadwork

問題. Roadwork 1次元上の原点に 人の人がいる. 番目の人は時刻 に正の方向に速度 1 で進む.ただし,道路工事が行われている場所に到達するとこれ以上歩くのを止める.道路工事は 個行われており, 番目の道路工事は時刻 から の間に場所 で行われている.…

Chokudai SpeedRun 002 L問題:長方形 β

問題. 長方形 β 個の長方形があり, 番目の長方形の幅と高さはそれぞれ である. 個の長方形の内いくつかを選び軸平行に順番に重ねていく.このとき,前に置かれている長方形の内部で辺に接しないように設置する必要がある.このとき,最大で何個の長方形を…

Chokudai SpeedRun 002 J問題:GCD β

問題. GCD β 自然数のペアが 個与えられる. 番目のペアは である.各ペアからちょうど1つの自然数を選んでそれらの最大公約数をとる.このときの考えられる最大公約数の最大値を求めよ.制約: ,

メモ:用語集

競プロ関係で出てくる知らなかった用語の雑多なメモ

ARC002 C問題:コマンド入力

問題. コマンド入力 A, B, X, Y の 4種類からなる長さ のコマンド列 が与えられる.長さ 2 の 2 種類のショートカットキー L と R を設定することによって, の連続する 2 つのコマンドで L または R に一致するものを L または R に置き換えることができる…

ARC004 B問題 : 2点間距離の最大と最小 ( Maximum and Minimum )

問題. 2点間距離の最大と最小 ( Maximum and Minimum ) 平面上に 個の点があり,0 から まで番号付されている.任意の に対して, 番目と 番目の点の間の距離 が与えられる.このとき,0 番目と 番目の点の間の距離としてとりうる最大値と最小値を答えよ.制…

ARC011 A問題 : 鉛筆リサイクルの新技術

問題. 鉛筆リサイクルの新技術 本の使用済みの鉛筆から新たに 本の鉛筆が作り出される.初めに 本あるときに合計で何本の鉛筆を販売することができるか求めよ.制約: ( と は互いに素)

Google Code Jam 2019 Round2 : Contransmutation

問題. Contransmutation 種類の金属があり,1番目の金属は鉛である. 番目の金属を1グラム使用して, 番目と 番目の金属をそれぞれ1グラム生成できる.最初に 番目の金属は グラムある.金属の生成方法を繰返し行い鉛のグラム数を最大化せよ.そして,そのと…