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

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

縦に見るものを横に見る

AtCoder ABC 159 F - Knapsack for All Segments (600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

Codeforces Round #617 (Div. 3) F. Berland Beauty

面白かった!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs (R2300)

面白かった!!!こういうのを確実に通せるようにならないと!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…

AtCoder ABC 151 E - Max-Min Sums (500 点)

こういう系の「個別要素に分解して考える」という問題が三連発だ!!!!! これもあれも! drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…

AtCoder ABC 150 E - Change a Little Bit (500 点)

面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

AtCoder ABC 143 F - Distinct Numbers (600 点)

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

AtCoder ABC 127 E - Cell Distance (500 点)

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

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

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

Codeforces 553 DIV2 E. Number of Components (R2100)

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

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

AtCoder AGC 005 B - Minimum Sum (400 点)

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

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …

AtCoder ABC 116 C - Grand Garden (300 点)

整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

キーエンス プログラミング コンテスト 2019 F - Paper Cutting (900 点)

このシンプル設定でこの深み...すごい!!! や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…

Tenka1 2018 C - Align (400 点)

今週のお題「わたしとバレンタインデー」 提出するまでが怖かった 問題へのリンク 問題概要 整数が N 個与えられます。 i 個目の整数は Ai です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。 考えたこと うおっ…

AtCoder ARC 092 D - Two Sequences (500 点)

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

Codeforces Manthan Codefest 18 F - Maximum Reduction

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

yukicoder 399 動的な領主

ツリー上のクエリの練習 問題へのリンク 問題概要 (意訳) N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。 2 頂点 u, v 間のパス上に含まれる頂点すべて (u, v も含む) の値を +1 する。 Q 回の操作後の各頂点の値…

TCO 2018 Round 3B Med TestProctoring

楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…