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

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

前処理

AtCoder ABC 143 E - Travel by Car (500 点)

この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…

AtCoder ABC 143 F - Distinct Numbers (600 点)

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

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

Codeforces Round #584 - Dasha Code Championship E. Rotate Columns (R2400)

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

AtCoder ARC 065 E - へんなコンパス / Manhattan Compass (900 点)

めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

AtCoder ABC 129 D - Lamp (400 点)

これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…

CODE FESTIVAL 2018 Final B - Theme Color (300 点)

さ、300 点!? 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…

diverta 2019 F - Edge Ordering (1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

AtCoder ARC 074 D - 3N Numbers (500 点)

昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…

AtCoder ABC 125 C - GCD on Blackboard (300 点)

累積和!累積和!累積和!!! でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…

Tenka1 2019 C - Stones (300 点)

これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N -…

AtCoder ARC 096 E - Everything on It (900 点)

部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい! 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

AtCoder ABC 122 C - GeT AC (300 点)

これも累積和!!! ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com

AtCoder ABC 084 D - 2017-like Number (400 点)

累積和を用いる典型な感じ! atcoder.jp ここで解説を行った: qiita.com

Educational Codeforces 62 E - Palindrome-less Arrays

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

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

AtCoder ARC 045 C - エックスオア多橋君

XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決めて…

AOJ 3062 Product (RUPC 2019 day2-L)

本当に悔しい。BFGS に無限にこだわってしまった。なぜ方針転換を図れなかったのか。。。 そしてこの問題、本当に本当に整数論の魅力がたっぷり詰まった楽しい問題だった。作問してくれた会津大チームにすごく感謝!!!!!!!!!! 問題へのリンク 問題…

AOJ 3053 Phone Number (RUPC 2019 day2-C)

一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。 問題へのリンク 問題概要 "31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。 今、 137 456 …

AtCoder AGC 008 B - Contiguous Repainting (400 点)

操作を逆順に見るとよいという、すごく良い例題!大好き!!! 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

CS Academy FII Code #1 E - Sugarel’s Garden

にはできたけど、 にできなかった。 問題へのリンク 問題概要 二次元平面上に 点が与えられる。 点から 4 点を選んでできる四角形のうち、内部にちょうど 個の点をもつものすべてを考えたとき、その面積の最小値を求めよ。 制約 どの 3 点も同一直線上にはな…

AtCoder ABC 073 D - joisino's travel (400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

全国統一プログラミング王決定戦 本選 A - Abundant Resources (200 点)

累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…

AtCoder ABC 070 D - Transit Tree Path (400 点)

一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…

AtCoder ABC 054 D - Mixing Experiment (400 点)

なんだろ 問題へのリンク 問題概要 個の薬品があって、それぞれ成分 A, B を グラムずつ含んでいる (すべて整数値)。 これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど : となるようにしたい。 そのようなことが可能となる薬品…

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…

AOJ 0660 たのしいたのしいたのしい家庭菜園 (JOI 2019 本選 C)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない」ようにしたい。それが可能となる操…

AOJ 0658 勇者ビ太郎 (JOI 2019 本選 A)

とりあえず 1 問目やってみた!累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される N × M の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) …