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

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

2020-02-01から1ヶ月間の記事一覧

フォルシアゆるふわ競プロオンサイト #3 D - Banana Game locked

すごく面白かった! 問題へのリンク 問題概要 個の袋があって、それぞれには 激辛バナナが 本 美味しいバナナが 本 がある。先手と後手が以下のことを交互に行う。 激辛バナナを 0 本または 1 本取り出す 美味しいバナナを好きな本数だけ取り出す ただし、激…

フォルシアゆるふわ競プロオンサイト #3 C - Bananas Multiplier (Hard) locked

ツリー上のパスクエリについての教育的典型題だった 問題へのリンク 問題概要 (意訳) 頂点の重み付きツリーが与えられる。以下の 個のクエリに答えよ。 各クエリは 2 頂点 , と値 が指定され、ツリー上の と とを結ぶパス上の辺の重みの積を求め、それと を…

フォルシアゆるふわ競プロオンサイト #3 B - Median Permutation locked

後ろから見たらわかった 問題へのリンク 問題概要 の順列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 任意の 以下の奇数 に対して、 のメディアンは である 制約 考えたこと 簡単のため、 を奇数として考えてみる。この…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (黄色, 700 点)

遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AtCoder ARC 033 C - データ構造 (試験管青色)

BinaryTrie を確認した!!! 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…

AtCoder AGC 006 C - Rabbit Exercise (赤色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (緑色, 400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

AtCoder ABC 154 D - Dice in Line (茶色, 400 点)

期待値の線形性!!! 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…

AtCoder ABC 154 C - Distinct or Not (灰色, 300 点)

こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う std::set や std::map などの連想配列を用いて管理する ソートしてソート順に処理していく 問題へのリンク 問題概要 個の整数 が与えられる。この整数列のどの 2 つの要素も…

AtCoder ABC 154 E - Almost Everywhere Zero (水色, 500 点)

DP しなくても間に合うけど、桁 DP 的な考え方が役に立つ! 問題へのリンク 問題概要 100 桁以下の整数 が与えられる。 以上 以下の整数であって、十進法表記で 0 以外の数値がちょうど 個であるようなものが何個あるのかを求めよ。 制約 の桁数 考えたこと …

AtCoder ABC 154 F - Many Many Paths (青色, 600 点)

すっごく色んな方法がありそう!!! 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…

第6回 ドワンゴからの挑戦状 本選 2020 A - 2525敷き詰め (500 点)

面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…

CADDi 2018 F - Square (橙色, 900 点)

面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…

CADDi 2018 E - Negative Doubling (黄色, 800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

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

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

Codeforces Round #617 (Div. 3) E2. String Coloring (hard version) (R2000)

これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…

Educational Codeforces Round 74 F. The Maximum Subtree (R2300)

木 DP シリーズ!!! 問題へのリンク 問題概要 区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。 さて、 頂点の木が与えられる。この木の連結な部分グラフ (…

木の直径 (AOJ Course GRL_5_A)

めちゃめちゃ簡単な実装で良いことがわかったので。 なんか、DFS 2 回か、全方位やるかなのかと思ってたけど、とても簡単な木DPで直径が求められることを知った。 問題へのリンク 問題概要 頂点の重み付き木が与えられるので、その直径の長さを求めよ。 制約…

Educational Codeforces Round 74 E. Keyboard Purchase (R2200)

こういうのを素早く処理できるようになりたい 問題へのリンク 問題概要 長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。 順列のスコアは、 上のすべての連続する 2 文字…

Educational Codeforces Round 74 D. AB-string (R1800)

面白かった 問題へのリンク 問題概要 文字列 が good であるとは、 の連続部分文字列であって回文であるような区間をすべてとってきたときに、それらによって が被覆されることをいう。たとえば "aaba" は、"aa" と "aba" によって被覆されるので good であ…

キーエンス プログラミング コンテスト 2020 F - Monochromization (銅色, 1100 点)

「操作によって出来上がるものが何通りあるか?」という問題では、まず判定問題を考える!(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…

円と多角形の共通部分の面積 (AOJ Course CGL_7_H)

円と多角形の共通部分の面積を求めるライブラリ、一念発起して整備した!!! サブルーチンとして「円と "線分" の交点を求める」というライブラリが必要となる。 問題へのリンク 問題概要 原点を中心とした半径 の円と、 頂点の多角形が与えられる。これら…

Educational Codeforces Round 2 E. Lomsat gelral (R2300)

マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…

Educational Codeforces Round 2 D. Area of Two Circles' Intersection (R2000)

円と円の共通部分の面積!!! 問題へのリンク 問題概要 円が 2 つ与えられる。それらの共通部分の面積を求めよ。 制約 座標の絶対値が 以下 解法 「接する場合」を除くと、以下の 3 パターンにわかれる 完全に disjoint (面積は 0) 2 点で交わる 一方が他方…

yukicoder No.980 Fibonacci Convolution Hard (母関数)

すごい面白かった!!! 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…

yukicoder No.979 Longest Divisor Sequence

LIS の亜種だけど、雰囲気違って面白い! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…