ferinの競プロ帳

競プロについてのメモ

競技プログラミング

ABC143 F - Distinct Numbers

問題ページ 基本的に使用している文字は公式解説と同じ意味になるように使っています. 回操作ができるような整数のうち最大のものをとする. を数列に含まれるの個数とする.回操作するとき,整数を選択できる回数は 回である.よって回操作をするときに,…

JAG2019 Day3

ABC はい E DP D 2SAT H UFマージテク G 期待値で式変形を頑張る I 係数がパスカルの三角形になってる FFTでやる J 行列を構築するやつ F よくわからん D x_i = (iを集合に入れるならtrue) とする XORについてのclosureを (not x_i) or (not x{i xor X}) と …

JAG夏合宿Day1

ABCDEJ → コンテスト中に解いた F: 凸関数 G: DP H: 2数の積の桁長 I: 誤差がやばい K: 畳み込み K 1次元につぶす https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3873509 G 解説で素直なDPとなっているDPの一例を書く.A[i][j], B…

CODE FESTIVAL 2016 Final H - Tokaido

問題ページ 考えたこと dp[すぬけくんのコマの位置][りんごさんのコマの位置][手番] としたDPはできそう 明らかに状態が多すぎるので減らしたい コマが隣接して置かれていないとき,左のコマは右に隣接するまで一つずつずらすのが最適 dp[左のコマの位置][手…

yukicoder No.878 Range High-Element Query

問題ページ 解法 マージソートの過程をセグ木に保存する方法(蟻本 p171)と同じ要領で,各頂点にその区間に対応する「高い要素」の列を保存しておく.左の子と右の子の2つの列をmergeするときには,左の子の列はそのままで,右の子の列の要素のうち左の子の列…

yukicoder No.877 Range ReLU Query

問題ページ 解法 区間]により大きい要素しかないのであれば を計算すればよい.逆に以下の要素しかなければ0を出力するだけである.区間]の和,以下の要素の個数,以下の要素の和が求まればより大きい要素と以下の要素に場合分けしてそれぞれ計算すればよい…

CODE FESTIVAL 2016 Grand Final J - 123 Pairs

問題ページ 解法 ペアとなっている2要素を区間として,区間が交差しない部分は独立に考えてよさそう.各区間でどのようなペアのとり方が存在するのか考えると以下のパターンしかない. (1) 1 (2) 2 3 … 3 2 (3) 3 1 (4) 3 3 3 2は(2)以外で使用できないので(…

TTPC2019参加記

コンテスト 東京工業大学プログラミングコンテスト2019 - AtCoder チームolphe_konaiphe(oshibori,tsutaj,ferin)で参加しました. B問題 部分文字列okyoのあとに部分文字列echが存在するかを判定すればいいことがわかったので書いてAC A問題 oshiboriさん…

ラグランジュ補間

次の問題を解くアルゴリズム 次以下の多項式 が存在する. となる の組が 個存在するときに を復元しろ. 求める の形式で場合分けする. を一つ求める (はgiven) とすると (ただしは未知の係数) と書ける.このように を定めると となるのが都合がいい. と…

CODE THANKS FESTIVAL 2018 G - Sum of Cards

問題ページ 解法 頂点のグラフで考える.枚目のカードの表に,裏に が書かれている場合,頂点 と頂点 の間に辺を引く.問題文の条件をこのグラフ上に言い換えると, 表裏を選ぶ操作→各辺を向き付けする. 種類以上の整数が見える→出次数が1以上の頂点がk個以…

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

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

AIM Tech Round 5 (rated, Div. 1 + Div. 2) D. Order book

問題ページ 解法 サンプル2について考える. 4 ADD 1 ADD 2 ADD 3 ACCEPT 2 ACCEPTが正常に行われるには2がBUYの最善かSELLの最善である必要がある.したがって2未満はBUY,2より大きいものはSELL以外にすることが不可能でどちらにすべきか確定する. このsa…

Technocup 2019 - Elimination Round 1 E. Vasya and Good Sequences

問題ページ 解法 まず区間 を一つ固定して,この区間が条件を満たせるかの判定を考える. ビットが立っている数が同じであれば作れる数字の集合は同じなため の値は本質ではなくビットが立っている数が大事. のビットが立っている数とする. とできる方法が…

Codeforces Round #290 (Div. 1) C. Fox And Dinner

問題ページ 解法 2以外の偶数は素数にならないことからa[i]とa[j]の偶奇が一致するときa[i]+a[j]は素数にならない a[i]+a[j]が素数であれば頂点iと頂点jを結んだグラフは二部グラフになる 二部グラフから各頂点の次数が2になるように辺集合を選ぶ問題に帰着…

Codeforces Round #557 (Div. 2) [based on Forethought Future Cup - Final Round] C. Thanos Nim

問題ページ 解法 どのような状態が勝ち/負けなのか考える。n=6で試してみる。0が4個以上の場合操作できないのでその時点で負けである。0が3個以下の場合、0が4個以上になるように操作して相手に渡せばよいので勝ちになる。1が4個以上の場合、どう操作しても0…

Codeforces Round #554 (Div. 2) D. Neko and Aki's Prank

問題ページ 解法 木において最大マッチングを考える場合、葉が隣接する辺から貪欲に取っていけばよい。葉が隣接する辺を取らなかったことでマッチングに追加できる辺の本数は高々1本なので取らないことで得をすることはないからである。よってTrie木で根から…

Codeforces Round #551 (Div. 2) E. Serval and Snake

問題ページ 解法 パスの端点を一つも含まないような範囲 範囲に入った後出ることを繰り返すので返ってくる値は必ず偶数 パスの端点を両方含むような範囲 範囲から出た後入るを繰り返すので返ってくる値は必ず偶数 パスの端点を片方だけ含む範囲 範囲内と範囲…

AGC018 D - Tree and Hamilton Path

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

CPSCO 2019

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

Codeforces Round #556 (Div. 2) D. Three Religions

問題ページ 解法 まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいのでdpをする。 文字列 の 番目までで(文字列1の 文字 && 文字列2の 文字 && 文字列3の 文字)をつくれるか? という愚直なdpがあるがこのままでは状態数が大き…

GCJ 2019 R1B Fair Fight

問題ページ 解法 部分点は で取りうる区間を全探索すればよい。 満点では 個の区間を全部見ているのでは間に合わない。 が最大になり、 についても条件を満たすような区間がそれぞれ何個あるか?を各 に対して求めることで答えを求める。この各区間に課され…

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 どれか一つ和を持っ…

乱択

https://codeforces.com/blog/entry/61587 の必要なところのメモ 乱数生成 rand() 乱数生成の質が微妙なのでやめよう こどふぉだと最大値が32767しかないのでさらにまずい mt19937 C++11以上で追加された機能でメルセンヌツイスターで乱数を生成する 高速 最…

Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory

問題ページ 解法 頂点a,bを結ぶパスの辺をe本と固定したときの組み合わせ数を求める。まずn-2個の頂点からパス上のe-1個の頂点を選ぶ方法がP(n-2, e-1)通りである。次にパス上の辺の重みを決定する方法について考える。mをe分割する方法はm個のボールの間(m-…

エクサウィザーズ 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番目も左に消えることに気がつく 単調性があるので…

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

問題ページ 考えたこと gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる 約数系包除で数えられそう 期待値をちゃ…

FII Code Round #1 Sugarel in Love

問題ページ 解法 dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[…