ferinの競プロ帳

競プロについてのメモ

AtCoder

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

問題ページ 解法 とする. 高橋くんが勝つのが 回,青木くんが勝つのが 回,引き分けが 回起きるとする. 期待値の前にまず確率がどのようになるか考える.高橋くんが最後に勝つのは確定で,それ以外の部分は確率 の操作が 回,確率 の操作が 回,確率 の操…

AGC018 D - Tree and Hamilton Path

問題ページ 考えたこと 完全グラフだと辺の本数が多すぎてつらそう 木の任意の頂点間を移動できると思った方がよさそう 任意の順番で木上を移動するとき最長となる経路長を答える問題になった よくわからないので実験する ある頂点からはじめて最も遠い頂点…

CPSCO 2019

全部解いたので略解と感想メモ Session1 A: 算数 B: 各文字の出現回数を数える C: binom(32, 6) の全探索 D: 8*5n-1 E: 各数は高々1回しか消されないのでsetとかで愚直に書いてもok F: 最小値の最大化と言われたので二分探索を考える 満足度を決めると各果物…

Tenka1 Programmer Contest 2019 E - Polynomial Divisors

問題ページ 解法 解説放送で言ってることを自分流に書いたもの pを一つ固定してその素数が条件を満たすか判定することを考える。pで割り切れるか考えるので以降ではmod pで考える。任意のxに対してf(x)=0 mod pとなればよい。フェルマーの小定理よりx=x^pで…

Tenka1 Programmer Contest 2019 D - Three Colors

問題ページ 考えたこと 部分和問題っぽくて貪欲は無理そうだし制約小さいしまあDP dp[i番目まで][R=j][G=j] みたいなDPを考える R,G,Bは90000くらいまで取りうるのでどう考えても無理 三角形の成立条件を考える R+G>B && R+B>G && B+G>R どれか一つ和を持っ…

エクサウィザーズ 2019 E - Black or White

問題ページ 考えたこと i回目までに両方ある/白しかない/黒しかない確率をそれぞれ求めたい これがわかればi回目の答えは (両方ある確率)/2 + (黒しかない確率) になるので解ける 黒しかないを知るには黒がj個あるがわかるとよさそう dp[i番目][黒がj個] = …

エクサウィザーズ 2019 D - Modulo Operations

問題ページ 考えたこと sの順列でX%s_1%s_2%s_3…を求める 制約を見るとDPをしてくださいと言っている dp[i番目][modがj]みたいなの 挿入DP?みたいな感じになりそうだけど遷移がやばそう ここでmodの性質を思い出すとmod xをしたあとにmod y(y >= x)をしても…

エクサウィザーズ 2019 C - Snuke the Wizard

問題ページ 考えたこと i番目にいた人が消える条件は何か?で考えるけどまともな形にならない 方針転換して二分探索をすることにする 消える人数を固定したところで何も嬉しくない i番目が左に消えるときi-1番目も左に消えることに気がつく 単調性があるので…

ARC062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題ページ 解法 立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか?という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。 ただし、回転等…

ARC084 E - Finite Encyclopedia of Integer Sequences

問題ページ 解法 まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。 ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような…

ARC065 E - へんなコンパス / Manhattan Compass

問題ページ 解法 まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。 コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不…

みんなのプロコン 2019 F - Pass

問題ページ 解法 dp[i][j] = (結果の列のi+j番目まで見たときに赤をi個、青をj個使っているとき何通りあるか) でDPをする。DPの遷移は dp[i+1][j] += dp[i][j] 次に赤を置くことが可能 dp[i][j+1] += dp[i][j] 次に青を置くことが可能 の2通りになる。次に赤…

みんなのプロコン 2019 D - Ears

問題ページ 解法 とりあえず散歩によって作れる列がどのようなものであるのか実験する。ある区間を往復するときに大きく往復するのではなく一つずつ独立に往復していくと考えられるので各要素は独立に値を決められる。いろいろ実験していると数列の取りうる…

CODE THANKS FESTIVAL 2018 F - Coins on the tree

問題ページ 解法 辞書順最小を求めるときは前から貪欲に決めていくのが典型。まずv[1]=1と決めてみたときに残りの木の状態と操作回数とコイン枚数について条件を満たせるのであればv[1]=1と決定してしまってよい。条件を満たさないのであればv[1]=2として同…

第5回 ドワンゴからの挑戦状 本選 C - Interval and MST

問題ページ 解法 boruvka法を使って最小全域木問題を解く。各連結成分から他の連結成分へつなぐ最もコストが小さい辺をO(N)やO(NlogN)程度で求められるときに有効な方法になる。ある区間が他の区間と交差するのは4パターンに分類できる。 その区間の右側と他…

TDPC T - フィボナッチ

問題ページ 解法 きたまさ法メモ - よすぽの日記 この記事を自分なりに理解したメモ 問題では1-indexになっているが0-indexで扱うとする。つまり以下の数列Aの第n項を求めろという問題になる。 A[i] = 1 (i<k) A[i] = A[i-1] + A[i-2] + … + A[i-k] (i>=k) 行列累乗を使えばO(K^3N)で解ける(cf. 蟻本p114</k)>…

EDPC Q - Flowers

問題ページ 解法 花を削除するのではなく条件を満たしつつ追加していくと考える。高さが低い花から順番に挿入していくと考える。dp[i] = (高さがiの花を挿入したときの美しさの最大)としてDPをする。dp[i] = max(dp[j], j

EDPC J - Sushi

問題ページ 解法 寿司がa[i]個乗っている皿がどこにあったとしても選ばれる確率に影響はない。したがってN要素の数列a[i]ではなくcnt[i]=(i個乗っている皿の数)と情報を持つことができる。 dfs(x, y, z) = (1個乗っている皿がx枚、2個乗っている皿がy枚、3個…

AGC030 D - Inversion Sum

問題ページ 考えたこと 全パターンについて数え上げなので確率で考える ペア(A[i], A[j])について反転している確率を求めてこれを足して2^Qを掛ければよさそう A[i]>A[j],i

AGC030 B - Tree Burning

問題ページ 考えたこと まず部分点を取りに行く 木を燃やすときにi番目が燃えているがi-1番目を燃やさずに飛ばすような方法はない 状態がN^2個で収まりそう dp[反時計回りにi個燃やした][時計回りにj個燃やした] = (かかる最大の時間) みたいなDPをしたい 遷…

Xmas Contest 2018 B - Bit Smaller

問題ページ 解法 入力が与えられないので条件を満たす数を予め全列挙するプログラムをローカルで実行しておきその答えをtextで提出すればよい。数nをa1,b1,a2,b2,…,ak,bk,cと切れ目を入れたときに条件を満たしているような切り方があれば数nを答えに追加すれ…

CADDi 2018 E - Negative Doubling

問題ページ 解法 最終的な列はマイナスとプラスが ----/++++ のように並ぶはずである。したがってマイナスとプラスの区切り位置を決めると、+の列/-の列についてそれぞれ考えられる。符号が全て同じであれば4倍する操作を繰り返すと考えればよく、符号を無視…

AGC006 D - Median Pyramid Hard

問題ページ 解法 K番目の値を求めるときは二分探索がよくあるパターンである。二分探索を使うことでK番目の値がX以上か?という判定問題に置き換える。K番目の値がA以上であればA以下の数Bについても判定が真となるので単調性はある。数列をX以上とX未満の2…

AGC029 D - Grid game

問題ページ 解法 高橋くんが動かなかった場合、青木くんも動かなければゲームが終了するので高橋くんは動けるならば動くべきである。各行について駒がたどりつける最大の列txが求まっていたとする。このときtx以下の地点に障害物が存在していればその障害物…

AGC029 B - Powers of two

問題ページ 解法 各値を頂点に持ち、値を足すと2べきになる頂点間に辺を張るとする。このグラフで最大マッチングが求められればいいが、N<=10^5だと二部マッチングでもTLEしそうなので貪欲なりDPなりでマッチングを高速に求められる構造がなければできなさそ…

AGC029 A - Irreversible operation

問題ページ 解法 操作を終えたあとの最終的な文字列がどうなっているか考えます。BWと並んでいるところがあればまだ操作が続くはずなので一度Bが出てきた後にWがでてくることはありません。したがって最終的な文字列はWW…WWBB…BBとなるはずです。Wの前にBが…

天下一プログラマーコンテスト2015本戦 E - 天下一コップ

問題ページ 解法 順列全てや部分列それぞれについて計算しろといった問題で与えられた通りに数えるのはTLEしてしまうので別の視点から数え上げるのが有効な場合が多い。今回の問題ではi番目の長方形が底でj番目の長方形の高さまで水が入っているような並び方…

第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題ページ 解法 3つ組のうちaとcを動かしていくことを考える aがcを追い抜かすことはない [a, c]についてs[a]=='D'であれば答えに sum(区間[l,i]のMの数) (a<=i<=c, s[i]=='C') を加算する 現在の区間についてMの数(=mnum)、Cの数(=cnum)、DMC(=now)の数を…

第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

問題ページ 考えたこと 上のbitから順番に決めていく 2^i > 2^i-1 + … + 2^0 より上のbitから貪欲に決めてよいはず 2^i の位が1となっている区間がk個以上存在した場合、2^iを1とできる 一旦1と決めた位が合った場合、その下の位で使える区間が限定される i…

ARC086 E - Smuggling Marbles

問題ページ 解法 木DPを行う。dp[i][j][k]=(j回動かしたときに頂点iにk個(=0,1か2個以上)ビー玉が存在するような初期配置の数) と定義してDPをする。頂点iの子をc_0とc_1とする。これらの子の情報dp[c_0]とdp[c_1]をマージする方法について考える。j=0~d(頂…