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

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

総和を求める

AtCoder ABC 127 E - Cell Distance (500 点)

何をしたらよいかがすぐに見えてくる典型だけど、かなり手こずった 問題へのリンク 問題概要 整数 があたえられる。 のグリッドから 個を選んでコマを置く 通りの方法それぞれに対して 通りのコマにペアそれぞれについてのマンハッタン距離の総和 を求め、そ…

AtCoder ABC 129 F - Takahashi's Basics in Education and Learning (600 点)

重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…

diverta 2019 F - Edge Ordering (1200 点)

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

Codeforces 553 DIV2 E. Number of Components (R2100)

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

AtCoder AGC 005 B - Minimum Sum (400 点)

教育的な典型問題! 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…

AtCoder ARC 092 D - Two Sequences (500 点)

桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 090 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…

Codeforces Manthan Codefest 18 F - Maximum Reduction

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

CS Academy 076 DIV2 D - Pyramids

えーーーーー、どうしてバグに気づかなかった。。。orz 問題へのリンク 問題概要 x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。 制約 1 <= N <= 10…

2018 codeFlyer 本選 B - 交通費 (400 点)

ちょっと重たかったん。でも累積和には大分慣れて来たのん。lower_bound とか upper_bound がどっちだけ...ってのはまだなかなか慣れないから要修行なのん。でも今回は本当にどちらでもいいので、こういうところで思考停止できるようになるのが大事なのんな…

CS Academy 081 DIV2 C - All Numbers

解けたけどもっとちゃんと整理しないとなん 問題へのリンク 問題概要 N 個の整数 a_1, a_2, ..., a_N が与えられる (0 <= a_i <= 9)。これを並び替えて順につないでできる整数 (leading zero は除く) として考えられるものの総和を 109 + 7 で割った余りで求…