参考文献 https://www.hamayanhamayan.com/entry/2017/12/19/152143 https://qiita.com/drken/items/4b4c3f1824339b090202 木の重心: その頂点を取り除いたときにできる部分木の要素数が元の半分以下になる頂点 重心は1個か2個必ず存在する 部分木の要素数を…

問題ページ 答え = (N-1)! * 期待値 期待値 スライム が を通る確率 スライム j が [i,i+1] を通る確率 → j+1~i が j より前に選ばれる確率で 1/(i-j) → jだけの式にしたほうが楽なので変形すると 1/j ～ の後に が来る確率が なのとか立式するパート実質 AG…

桁に着目して状態をまとめてDPするテク 取り扱える条件の代表的な例としては 以下の数，桁和，倍数 などである 桁DP自体の解説は以下のサイトなどがわかりやすい Digit DP 入門 by とーらすさん 桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか …

問題ページ i桁目で一致する状況 下の桁で繰り下がりがない && X[i]=0 && A[i]=0 下の桁で繰り下がりがある && X[i]=9 && A[i]=9 dp[下からi桁目][下の桁で繰り下がりが発生したか？」 という DPテーブルを持ち，以下の遷移を行う． chmax(dp[i+1][0], max(d…

最近フロー関連をやってたのでそのメモ 最大流 頂点辺の有向グラフ 各辺には容量が定義されている をそれぞれ頂点から出る/入る辺の集合とする 始点を，終点をとする LPの形で書くと以下の通り ford-fulkerson 最大流を求めるアルゴリズムの一つ 最大流の流…

燃やす埋める問題は以下の問題である 頂点を赤と青に塗り分ける 塗り方の依存関係によってスコアが変動する (例) 頂点 が赤で頂点 が青に割り当てられたとき 失う スコアの和の最小化を行え この問題は最小カットに帰着して解くことができる 必ず赤が割り当…

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

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}) と …

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…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題ページ 考えたこと 部分和問題っぽくて貪欲は無理そうだし制約小さいしまあ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以上で追加された機能でメルセンヌツイスターで乱数を生成する 高速 最…