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

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

CodeforcesCombined

Codeforces Global Round 12 E. Capitalism (R2700)

なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…

Codeforces Global Round 12 F. The Struggling Contestant (R2400)

こういう個数合わせ系の問題は実は得意かもしれない 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して の順列 であって、 のどの隣接する二項も同じ数値でないようなものを考える。 そのような順列 のうち、 を満たさない の個数の最小値を…

Codeforces Global Round 12 H1. Multithreading (Easy Version) (R2900)

ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…

Codeforces Global Round 12 D. Rating Compression (R1800)

頑張った 問題へのリンク 問題概要 正の整数のみからなる長さ の数列 が与えられる。各 に対して、以下の問に答えよ。 数列 を左から順に「連続する 個の最小値」をとっていってできる長さ の数列が、 の順列になっているかどうかを判定せよ。 制約 の総和 …

Codeforces Global Round 12 C2. Errich-Tac-Toe (R2300)

これ好き! 問題へのリンク 問題概要 のグリッドがあって、"." と "O" と "X" のいずれかが描かれている。"O" または "X" の描かれているマス目の個数を とする。 今、いくつかのマスに対して、"O" または "X" のマス目の "OX" を入れ替える操作を行う。それ…

Codeforces Round #586 (Div. 1 + Div. 2) D. Alex and Julian (R1900)

すごく面白かった 問題へのリンク 問題概要 (表現改) 個の正の整数 が与えられる。これらから最小個数を取り除いて、以下の条件を満たすようにせよ。 残った整数から重複を許して奇数個選ぶどのような方法に対しても、選ばれた整数を 2 つに分けてそれぞれの…

Codeforces Round #586 (Div.1 + Div.2) E. Tourism (R2200)

結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…

Codeforces Round #584 (Div. 1 + Div. 2) F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

Codeforces Round #584 (Div. 1 + Div. 2) E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

Codeforces Round #584 (Div. 1 + Div. 2) D. Cow and Snacks (R1700)

面白かった! 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…

Codeforces Round #584 (Div. 1 + Div. 2) C. Paint the Digits (R1600)

ちょっとややこしかった 問題へのリンク 問題概要 '0' 〜 '9' からなる 文字の文字列があたえられる。各文字を白黒に塗る。 どの黒く塗られた数も、あらゆる白く塗られた数以上である 白く塗られた数を元の文字列の順序で抜き取ったとき、数値は単調非減少で…

Codeforces Round #584 (Div. 1 + Div. 2) A. Paint the Numbers (R900)

誤読して大きく出遅れた... 問題へのリンク 問題概要 個の整数 があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。 これを実現するための…

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

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

Codeforces AIM Tech Round (Div. 1 + Div. 2) 5 F. Make Symmetrical (R2900)

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

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) F - Maximum Reduction (R2500)

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

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) E. Trips (R2100)

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

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) D. Valid BFS? (R1700)

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

Codeforces #502 (Div. 1 + Div. 2) C. (R1600)

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