けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

競技数学色強め

Xmas Contest 2020 C - Candies Candidates

Grundy 数がフラクタルっぽい構造を示していた! 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…

Xmas Contest 2020 B - Beterminant

なぜか埋め込みにこだわってしまい、本番 AC できなかった... 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす最大の正の整数 を求めよ (存在しない場合は -1、無限個存在する場合は -2)。 確率 % で表が出るサイコロを 回振るとする 表が出…

AOJ 3217 Cafe au lait (OUPC 2020 I)

数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

JOI 春合宿 2013 day1-4 JOI Poster (難易度 6)

幾何だ!! ジャッジページへのリンク editorial 問題概要 の長方形の紙上に 個の点がある。これらの点は互いに相異なる。 これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中…

AtCoder ABC 182 C - To 3 (灰色, 300 点)

これ灰色ってマジか!! 問題へのリンク 問題概要 どの桁の値も 0 でないような正の整数 が与えられる。 に含まれるいくつかの数値を除去することで、 が 3 の倍数となるようにしたい。 除去すべき数値の個数の最小値を求めよ (最初から 3 の倍数の場合は 0 …

Codeforces Round #682 (Div. 2) C. Engineer Artem (R2000)

グリッドグラフは二部グラフ!!! 問題へのリンク 問題概要 のマス目に整数値 (マス には ) が書かれている。 各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異…

AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題! 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …

AtCoder AGC 035 A - XOR Circle (茶色, 300 点)

面白かった。でも茶色ってことは流石になさそう......(コンテスト中は、全部の XOR 和が 0 かどうかを判定する、という嘘解法が AC になっていたらしい) 問題へのリンク 問題概要 個の非負整数 が与えられる。これらを円環状に上手に並べることで、 「どの整…

AtCoder AGC 039 D - Incenters (赤色, 1000 点)

銅色 diff 問題が自力で解けて嬉しい。(修正:赤色になった) 問題へのリンク editorial 問題概要 原点を中心とする半径 1 の円周上に 個の点 がある (偏角が入力として与えられる)。 これらの点からランダムに 3 点選んでできる三角形の内心の座標の期待値を…

CodeChef Practice(Easy) GCD Sum

添字 GCD 畳み込みの練習問題! 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…

AOJ 2638 Hyperrectangle (JAG 夏合宿 2014 day2-J) (550 点)

りんごさんセット!!! 問題へのリンク 問題概要 次元空間において () を満たす部分の体積を とすると は整数値となる。この整数値を 1000000007 で割ったあまりを求めよ。 制約 考えたこと 最初は色々迷走していた。三次元の場合を考えていて思っていたの…

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

AOJ ???? Stick Combination (KUPC 2020 D)

面白かった 問題へのリンク 問題概要 という 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。 制約 考えたこと こういう…

AOJ 2678 Cube Coloring (JAG 春コン 2014 B) (450 点)

頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…

AOJ 2385 Shelter (JAG 冬合宿 2010 day4-G) (700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

HHKB プログラミングコンテスト 2020 F - Random Max (橙色, 600 点)

時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…

AtCoder ABC 154 F - Many Many Paths (青色, 600 点)

すっごく色んな方法がありそう!!! 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…

AOJ 2378 SolveMe (JAG 冬合宿 2010 day3-J) (1200 点)

伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…

AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点)

| x - a | + | x - b | + | x - c | + ... の最小値を求める問題には定石があるぞいぞい 問題へのリンク 問題概要 長さ の整数列 が与えられます。整数 をいろいろ変えたときの の最小値を求めてください。 制約 考えたこと 非本質だけど、 って普通「変数」…

AtCoder ABC 130 C - Rectangle Cutting (茶色, 300 点)

長方形を直線で真っ二つに割る方法について 直線が長方形の対角線の交点を通る 直線が長方形を二等分する というのは同値だという話。結構、中学受験の算数では定番の話だったりする。 問題へのリンク 問題概要 二次元平面上で を頂点とした長方形と、その内…

AtCoder ABC 126 E - 1 or 2 (水色, 500 点)

これまた Union-Find を用いる教育的問題!!!!! 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

AtCoder AGC 001 E - BBQ Hard (1400 点)

当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける!!! というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…

AtCoder AGC 008 C - Tetromino Tiling (青色, 600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

AtCoder ABC 115 D - Christmas (緑色, 400 点)

再帰関数の使い方に慣れるための教育的問題。 この手の再帰的なフラクタルっぽい構造を読み解く問題は「十分回数を重ねると最初の方の模様が収束する」みたいなことをするイメージがあるけど、今回はそういうのじゃなくて純粋に再帰関数の使い方を問われる問…

yukicoder No.819 Enjapma game

好き! 確かに天才系問題だけど、実験を積み上げると見えて来る感じが最高!!! 問題へのリンク 問題概要 × の盤面に何個かのコマが置かれている。先手と後手が交互に、以下のいずれかの動作を繰り返す: コマを 1 つ選び、それを 1 マス左か下に動かす (た…

CPSCO 2019 session2 D - Two Piles

これ好き!!! しばらく、CPSCO の良さげな問題を解説するターンをやってみたい。 問題へのリンク 問題概要 石の山が 2 個あって、それぞれ初期状態では 個積まれている。ここから先手と後手が交互に 残っている石の山から 1 つ選び、その石の個数を とする…

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

AtCoder AGC 007 A - Shik and Stone (茶色, 200 点)

高校の頃とかに「グリッドの左上から右下まで行く最短路が何通りあるか」みたいな問題に親しんでいれば、自然に思えるかもしれない 問題へのリンク 問題概要 のグリッドがあって、最初は駒は左上隅に置かれていた。 駒が上下左右に動きながら右下隅まで移動…