問題ページ 速度を何回も上げ下げする必要はない．したがって1,3,9,27,9,9,3,3,1のように一回上げて下げるような変化を考えればよい．時間を短くするには，貪欲にできるだけ早い速度にするべきである． 速度を上げられる 秒で目標の時間を過ぎない 速度を維…

問題ページ ある列の高さを変更する場合，隣の高さに合わせる以外の中途半端な高さにして解が改善されることはない．よって前からDPを行うとき，番目を変更するならば番目の高さに揃えるとしてよい．番目の高さをのどれに揃えたか？という情報を持っておけば…

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

問題ページ 自分のコンテスト中の思考過程に沿って書きますが，公式解説の方がシンプルで高速に解けると思います．というか未証明です． まず， のペアを並び替えて が昇順になるようにする．この操作をしても一般性を失わない． 最も大きい に着目する． を…

問題ページ これは を最小化するように空港を設置する問題である．もし と が同じ木の頂点であれば，どのように空港を配置しても2点間の距離は変化しない．木の2点間の距離はLCAなどを用いることによって で求めることができる． ここからは と が違う木に属…

問題ページ が の中央値のとき は最小になる．Wavelet Matrixを用いると数列のある連続する区間のk番目の数を求めることができるので，各クエリに対して中央値を求めることができる． 未満の要素の個数 未満の要素の和 以上の要素の和 以上の要素の個数 が答…

問題ページ で0である桁について， を1にしたとしても と のビットカウントが1ずつ増加するだけである． が増えて損するだけなので， で1にする桁は も1の桁だけである． 下の桁から順に を0にするか1にするかを決定していくdpを行う． のうち を0/1のどちら…

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

問題ページ 基本的にやるべきことは問題文に書いてあるのでそのシミュレーションを行う．ただし， の範囲で を1ずつ増やしてシミュレーションをすると当然TLEなので，シミュレーションに関わってくる重要な時刻のみ取り扱う．人が席を立つ時刻 と水を汲み終…

問題ページ まず，開括弧と閉括弧の数が一致していなければ答えは0である．以下では開括弧と閉括弧の数が一致しているとする． s=((())())() x=1232121010 次に，与えられた文字列が正しい括弧列でなかった場合を考える．'('が来たら+1，')'が来たら-1をする…

問題ページ の人を無料で投票させるのには，他の人全員から投票されていなければならない．したがって， の人から1人(最も買収するのにお金がかかる人)以外は必ず買収する必要がある． の人を無料で投票させるには，が未満の人数で買収した人数 人を の人か…

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

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

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

数え上げにおいてときどき現れる．括弧列の数・多角形の分割・グリッドの経路数などがカタラン数で表される． 参考資料 wikipedia 括弧列・二分木・最短経路・三角形分割・平面グラフ・非交差分割 高校数学の美しい物語 トーナメント・最短経路・三角形分割 …

J 各操作で左崎さんは，右男さんはを必ず1減らす 相手の値を減らせるなら減らすべきなので数列に0が存在しないときは[1,n]を選択するべき よって回[1,n]を選択する操作を繰り返す この操作をした後はお互いa_1とa_nを減らし合って先に0になった方が負けにな…

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…