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

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

最大回数・最大個数を求める

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

Codeforces Global Round 15 C. Maximize the Intersections (R1800)

企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…

ウクーニャたんお誕生日コンテスト D - ukuku

ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…

AtCoder ABC 311 D - Grid Ice Floor (緑色, 400 点)

壁にぶつかるまで動く設定の迷路問題! 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…

AtCoder Library Practice Contest D - Maxflow

グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題! 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…

AtCoder ABC 297 C - PC on the Table (灰色, 300 点)

前から "PC" 詰めしていけば OK!! 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 '.' か 'T' が書かれている。今、次の操作をできるだけ多く行いたいとする。 左右に 2 文字連続した "TT" を "PC" に置き換える 操作回数の最大化を目指…

AtCoder ABC 180 D - Takahashi Unevolved (茶色, 400 点)

2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…

AtCoder ABC 169 D - Div Game (茶色, 400 点)

久しぶりに素因数分解する問題が来た!!!!!!!!!!! 問題へのリンク 問題概要 正の整数 に対して、以下の操作を何回行うことができるか、その最大回数を求めよ。なお、素数 と正の整数 を用いて の形で表すことのできる整数を「素数べき」と呼ぶこと…

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点)

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…

Educational Codeforces Round 83 E. Array Shrinking (R2100)

区間 DP な問題って、あまり見なくなったなと。貴重なので記録。 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、…

DISCO ディスカバリーチャンネル 2020 予選 D - Digit Sum Replace (青色, 500 点)

すごく面白かった! 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…

AtCoder ABC 143 F - Distinct Numbers (黄色, 600 点)

かなり辛いことを頑張ったけど、本当はすごく明快な問題だった!! 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…

AtCoder ABC 120 C - Unification (灰色, 300 点)

久しぶりのカッコ列の整合判定問題!!! カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

AtCoder AGC 029 A - Irreversible operation (茶色, 300 点)

一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…

AtCoder ABC 100 C - *3 or /2 (灰色, 300 点)

結構好きな問題 ABC 100 C - *3 or /2 問題概要 N 個の整数 a1, a2, ..., aN があって 1 回の操作で以下が行える 各整数について「3 倍」「2 で割るなら 2 で割る」のいずれかを行う どれかの整数については「2 で割る」の方をしなければならない 最大で何回…