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

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

Codeforces

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

Codeforces 558 DIV2 D. Mysterious Code (R2200)

部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…

Codeforces 558 DIV2 C2. Power Transmission (Hard Edition) (R2000)

有理数使った 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの任意のペアを結んでできり直線たちを考える (異なるペアが同一の直線を生成するときは、一つの直線とみなす)。 これらの直線たちの交点が何点生じるかを求めよ。 制約 考えたこ…

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

Codeforces 554 DIV2 D. Neko and Aki's Prank (R2000)

こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…

Codeforces 553 DIV2 E. Number of Components (R2100)

面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …

Codeforces 315 DIV1 B. Symmetric and Transitive (R2100)

ベル数の練習に 問題へのリンク 問題概要 (超意訳) 個の区別できる要素から何個か選んで残りを捨てて ( 個以上捨てなければならない)、選んだ要素を何個かのグループに分ける方法が何通りあるか求めよ。 制約 考えたこと 個選ぶとすると選び方は 通りあり、…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

Codeforces 552 DIV3 E. Two Teams (R1800)

超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…

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

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

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …

Educational Codeforces 62 C - Playlist

楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…

Educational Codeforces 62 E - Palindrome-less Arrays

楽しかった 問題へのリンク 問題概要 未完成の数列 が与えられる。未完成部分には が書かれている。完成部分には 以上 以下の整数が書かれている。 のところを 以上 以下の整数を埋める方法であって、整数列が奇数長の回文を含まないものは何通りあるか? 制…

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…

Codeforces Yandex.Algorithm 2011 Round 2 D - Powerful array

Mo のアルゴリズムの練習第三弾!!!!! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…

Educational Codeforces Round 057 G - Lucky Tickets

NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…

Codeforces AIM Tech Round 5 F - Make Symmetrical

僕の以前書いた記事、共円がちょっと関係ある問題だ!!!!!!!!!!!!! ガウス整数!!!!!!!!!!!!!!!!!!! 問題へのリンク 問題概要 二次元平面に関する以下の 3 種類のクエリ ( 個) に答えよ 格子点 に石をおく 格子点 においてあ…

Codeforces 511 DIV1 A - Enlarge GCD

大昔 osa_k 法と呼ばれていたやつ。 問題へのリンク 問題概要 個の整数 が与えられ、 をこれらの最大公約数とする。 今、 個の整数から何個かを取り除いて、その最大公約数が より大きくなるようにしたい。取り除くべき最小個数を求めよ。ただし、どのように…

Codeforces 511 DIV1 B - Little C Loves 3 II

なんとか解けてよかった 問題へのリンク 問題概要 × の二次元グリッド盤面が与えられる。 空いているマスを 2 つ選んで、その 2 つに駒を置く。ただしその 2 マス間のマンハッタン距離が 3 でなければならない という操作を繰り返し行う。こうして出来上がる…

Codeforces Manthan Codefest 18 F - Maximum Reduction

考え方はすぐわかるけど実装が大変... 問題へのリンク 問題概要 長さ の数列 と整数 が与えられる。 この数列に対して次のような操作を繰り返す 連続する k 個の区間についての最大値をすべて書き出す この操作を 1 回行うごとに数列の長さは だけ減ることに…

Codeforces 198 DIV1 D - Iahub and Xors

領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…

Codeforces Manthan Codefest 18 E - Trips

こういうの苦手。。。 問題へのリンク 問題概要 整数 k と、N 頂点 0 辺のグラフが最初に与えられる。以下の M 個のクエリに答えよ。 a, b: 辺 (a, b) を追加する。この時点でグラフの各頂点を以下の条件を満たすように白黒に塗る「任意の黒い頂点は、隣接す…

Codeforces Manthan Codefest 18 D - Valid BFS?

こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …

Codeforces Manthan Codefest 18 C - Equalize

超苦手系。なんとか解けた。 問題へのリンク 問題概要 長さ N のバイナリ列 a, b が与えられる。a に対して 隣接二項を swap する 0 と 1 を反転する の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2) 制約 1 <= N ,= 106 考えたこ…

Codeforces 502 C - The Phone Number

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …

Codeforces 190 DIV1 C - Ciel the Commander (重心分解)

てんぷら君が解いていたのを見て... 問題へのリンク 問題概要 頂点のツリーが与えられる。 ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。 任意の 2 頂点 u, v について、u…

Codeforces Educational 046 E - We Need More Bosses

二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。できるだけ多くの辺を壊したい。うまく s, t…

Codeforces 460 DIV2 E - Congruence Equation

中国剰余定理のことをあれこれ調べていたら勢いで解いたん 問題へのリンク 問題概要 整数 が与えられる。 mod. ) が成立するような 以上 以下の整数 を数え上げよ。 制約 は素数 < 解法 Fermat の小定理から以下のことが言える: は mod. において周期 である…