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

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

2019-04-01から1ヶ月間の記事一覧

AtCoder ABC 062 D - 3N Numbers (ARC 074 D) (青色, 500 点)

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

AtCoder AGC 032 E - Modulo Pairing (銅色, 1200 点)

楽しかった。7 時間かかったけど自力 AC できたー! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…

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

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

AtCoder ABC 125 D - Flipping Signs (緑色, 400 点)

操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…

AtCoder AGC 021 D - Reversed LCS (黄色, 900 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

Codeforces 554 DIV2 D. Neko and Aki's Prank (R2000)

こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…

AtCoder ABC 113 D - Number of Amidakuji (水色, 400 点)

あみだくじ 問題へのリンク 問題概要 縦棒の個数が 、横棒が縦方向に 刻みのあみだくじであって、 番目からスタートすると 番目に到着するようなものを数え上げよ。 制約 考えたこと いかにも DP という感じではあるね。 dp[ i ][ j ] := 縦棒を上から i 刻…

AtCoder ABC 122 D - We Like AGC (水色, 400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

Codeforces 553 DIV2 E. Number of Components (R2100)

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

Codeforces 315 DIV1 B. Symmetric and Transitive (R2100)

ベル数の練習に 問題へのリンク 問題概要 (超意訳) 個の区別できる要素から何個か選んで残りを捨てて ( 個以上捨てなければならない)、選んだ要素を何個かのグループに分ける方法が何通りあるか求めよ。 制約 考えたこと 個選ぶとすると選び方は 通りあり、…

Tenka1 2019 F - Banned X (赤色, 800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

Tenka1 2019 D - Three Colors (黄色, 600 点)

お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…

AOJ 2213 多項式の解の個数 (UTPC 2010 J)

今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com コード 形式的冪級数を用いてみた。 // // Formal Power Series (on runtime mod) // // verified: // Yosupo Judge // https://judge.yosupo.jp/problem/inv_of_formal_power_se…

Tenka1 2019 E - Polynomial Divisors (橙色, 800 点)

最大公約数を求めるときに abs つけてれば通ってた。。。 なにこれ悔しすぎる。。。 問題へのリンク 問題概要 次の整数係数多項式 が与えられる。任意の整数 に対して が で割り切れるような素数 をすべて求めよ。 制約 考えたこと めっちゃ好き!!!!!!…

Tenka1 2019 C - Stones (緑色, 300 点)

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

yukicoder No.140 みんなで旅行

スターリング数っぽい数え上げの練習 問題へのリンク 問題概要 組の夫婦がいて、合計で 人がいる。 人をいくつかのグループにわける方法のうち、各グループに夫婦が 組以上いるような場合の数を で割ったあまりを求めよ。 制約 考えたこと ひとまずグループ…

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

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

yukicoder No.391 CODING WAR

写像12相の 玉は区別する 箱も区別する 各箱の玉は 1 個以上 という場合の問題!!! 問題へのリンク 問題概要 個の互いに区別できる玉を、 個の互いに区別できる箱に入れる。 ただし、どの箱についても玉が 1 個以上入るようにするな方法が何通りあるか、10…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

AtCoder ABC 006 D - トランプ挿入ソート (試験管青色)

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…

AtCoder ARC 068 E - Snuke Line (黄色, 700 点)

こういうのを得意になるぞー!!! でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

Codeforces 552 DIV3 E. Two Teams (R1800)

超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

AtCoder ABC 115 C - Christmas Eve (灰色, 300 点)

今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…

AtCoder ABC 124 D - Handstand (緑色, 400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AtCoder ABC 124 C - Coloring Colorfully (灰色, 300 点)

一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…

AtCoder ABC 124 B - Great Ocean View (灰色, 200 点)

こういうのが素早くストレスなく書けるようになるといい感じな気がする 問題へのリンク 問題概要 海から順番に建物 があって、それぞれの高さは である。 海が見える建物が何個あるかを求めよ。なお、 番目の建物から海が見えるとは より前の 番目の建物より…