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

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

マルチテストケース問題

AtCoder ABC 321 E - Complete Binary Tree (青色, 450 点)

この問題をキッカケに準完全二分木のライブラリを拡充した! 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…

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

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

Yosupo Library Checker - Binomial Coefficient (Prime Mod)

「二項係数 mod 素数」を verify する問題 問題へのリンク 問題概要 素数 が与えられる。整数 の組が 組与えられるので、それぞれについて を で割ったあまりを求めよ。 制約 解法 ここで書いた方法を実装することで AC できる。ただし、modint は自前のもの…

競プロキャンプ2023関西 L - (sum)mer

FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1):FPS 求めたいものは である。これはちゃんと計算すると、 …

Codeforces Round 892 (Div. 2) E. Maximum Monogonosity (R??00)

つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック!!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…

Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad (R??00)

区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…

AtCoder ARC 160 B - Triple Pair (水色, 500 点)

これ系は好き! これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…

yukicoder No.2032 Let's Write Multiples!!

floor sum の練習! 問題へのリンク 問題概要 以上 以下の の倍数をすべて十進表記で 1 回ずつ書き出した時、数字 が書かれる回数を求めよ。 (テストケースが 個与えられる) 制約 考えたこと 各桁ごとに考える。整数 の右から 桁めが である条件は を で割っ…

AtCoder ABC 206 F - Interval Game 2 (黄色, 600 点)

Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…

Xmas Contest 2020 C - Candies Candidates

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

AtCoder ABC 186 E - Throne (水色, 500 点)

一次合同方程式を解く問題です! 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動:いま座っている椅子から時計…

AOJ 3209 Times Square (OUPC 2020 A)

ABC C にありそうな教育的問題! 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…

AtCoder ARC 109 D - く (黄色, 600 点)

僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した... 問題へのリンク 問題概要 二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。 3 つの石が次の条件を満たしているとき、くの字に並んでいるといいま…

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

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

Codeforces Round #687 (Div. 1) A. Bouncing Ball (R1400)

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

AtCoder AGC 048 A - atcoder < S (緑色, 300 点)

単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …

AOJ 1254 Color the Map (ICPC アジア 2004 G) (450 点)

本質的には彩色数を求めるだけだけど、幾何パートがちょっと面倒... 問題へのリンク 問題概要 二次元平面上に 個の多角形領域 (すべて単純) がある。各領域はそれぞれある国に属している。異なる多角形領域が同一の国に属していることもある。今、国ごとに「…

Codeforces Round #681 (Div. 1) E. Black, White and Grey Tree (R3000)

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]:残…

Codeforces Round #681 (Div. 1) A. Extreme Subtraction (R1800)

区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる! 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…

Codeforces Round #597 (Div. 2) F. Daniel and Spring Cleaning (R2300)

桁 DP 苦手すぎる... 問題へのリンク 問題概要 整数 が与えられる。整数の組 であって、 xor = を満たすものの個数を求めよ。 (というテストケースが 個与えられる) 制約 考えたこと とりあえず、 xor = という条件は 「 と を二進法表現したときに、ともに …

AtCoder ARC 105 E - Keep Graph Disconnected (橙色, 700 点)

とてもシンプルな設定で面白かった!でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…

AtCoder ARC 105 D - Let's Play Nim (青色, 600 点)

これ結構好き! 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき):コインが入…

HHKB プログラミングコンテスト 2020 D - Squares (青色, 400 点)

これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…

AtCoder ABC 169 C - Multiplication 3 (茶色, 300 点)

誤差は怖い!!!!!!! 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J) (900 点)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

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

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

GCJ 2019 Round 1A C - Alien Rhyme

いい感じの Greedy 問題 問題へのリンク 問題概要 個の文字列 が与えられる。2 つの文字列 について、 の最後 i 文字と、 の最後 i 文字が共通 の後ろから i 文字目も、 の後ろから i 文字目も c である という条件を満たすとき、ラベル (i, c) をつけながら…

GCJ 2019 Round 1A A - Pylons

こどふぉにありそうな雰囲気の問題かな 問題へのリンク 問題概要 × のグリッドの各マスをちょうど一回ずつ訪れたい。ただし スタートとゴールは異なるマスでよい 毎回の移動は、上下左右斜めの 8 方向への移動は禁止 (飛車の移動も角の移動も禁止) を満たす…

CS Academy 082 DIV1 E - Water Supply

ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…

CS Academy 081 DIV2 E - Fold Polygon

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…