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

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

2020-11-02から1日間の記事一覧

Codeforces Round #680 (Div. 1) C. Team-Building (R2500)

undo 付き Union-Find ってなんぞ!? 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…

AOJ 1610 竹の花 (ICPC 国内予選 2016 C) (250 点)

面白い。けど問題文長い...。問題概要を短くまとめてみた。 問題へのリンク 問題概要 正の整数 が与えられる。 あなたは、 以上の整数を 個用意する ( とする)。この 個の整数のスコアを、以下の条件を満たす最小の整数 として定める。 は のいずれでも割り…

AOJ 2858 Prime-Factor Prime (JAG 模擬地区 2017 C) (350 点)

貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使え…

yukicoder No.843 Triple Primes

エラトステネスの篩の練習問題に良さそう 問題へのリンク 問題概要 以上 以下の素数の組 であって、 を満たすものの個数を求めよ。 制約 考えたこと のときは明らかにダメ。 また、偶数かつ素数である整数は 2 のみであることに注意する。 がともに奇数とす…

Codeforces Round #680 (Div. 1) B. Divide and Sum (R1900)

本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…

Codeforces Round #680 (Div. 1) A. Division (R1500)

面白かった 問題へのリンク 問題概要 正の整数 が与えられる。 の約数であって、 の倍数ではないような整数の最大値を求めよ。 (というデータセットが 個与えられる) 制約 考えたこと の約数をすべて列挙したのでは間に合わない。とりあえず 自身が で割り切…

AtCoder ABC 181 C - Collinearity (灰色, 300 点)

幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。 問題へのリンク 問題概要 二次元平面上に 個の点 () が与えられる。 これらのうちの 3 点であって、同一直線上にあるものが存在するかど…

AtCoder ABC 181 D - Hachi (茶色, 400 点)

整数 を 8 で割ったあまりは、 の下三桁を 8 で割ったあまりに等しい! 問題へのリンク 問題概要 整数 が長さ の文字列として与えられる ( は '1'〜'9' のみで構成される)。 の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを…

AtCoder ABC 181 E - Transformable Teacher (緑色, 500 点)

頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!! 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…