ferinの競プロ帳

競プロについてのメモ

AtCoder

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(頂…

SoundHound Programming Contest 2018 Masters Tournament 本戦 D - Propagating Edges

問題ページ 考えたこと addとcheckだけなら簡単 completeで辺がO(N^2)本できるので辺を持つとやばい 辺はやばいけど頂点を持てばO(N)個しかない completeで完全グラフになった頂点集合をまとめておけばよさそう checkはaddで追加された辺に該当するものがあ…

ARC097 E - Sorted and Sorted

問題ページ 解法 転倒数が答えになるので転倒数の定義を考える。最初の数列をA、最終状態の数列をBとする。(転倒数) = (A[ia]=B[ib]=x,A[ja]=B[jb]=yとしたときにia<jaかつib>jbとなるペア(x,y) (x</jaかつib>

Tenka1 Programmer Contest E - Equilateral

問題ページ 考えたこと 45度回転 これ以降チェビジェフ距離で考える 距離が等しい点はある正方形上の点になる 2点を固定してその2点のどちらとも距離が等しい点を探す 各点を中心として2点間の距離*2を1辺の長さとする正方形を書く 2点どちらとも距離が等し…

Tenka1 Programmer Contest D - Crossing

問題ページ 考えたこと とりあえず実験 部分集合の大きさを4に固定してみる 1つ目の集合に異なる要素が3個は入っていないと、積集合の大きさが1となる条件を満たせない 1つ目と2つ目、1つ目と3つ目、1つ目と4つ目については以下のように取れば条件を満たす 1…

Tenka1 Programmer Contest C - Align

問題ページ 思考過程 ジグザグにするのがよさそう 一番小さい、大きいのを端に置くと損してる ジグザグな山みたいなのをつくるのがよさそう 一番小さいのを中央に置くか、一番大きいのを中央に置くかで2種類あるのに気をつけながら書くと通った #include <bits/stdc++.h> us</bits/stdc++.h>…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

問題ページ 解法 回文が成り立つ⇔奇数個の文字が1種類以下 である。回文が成り立つかの判定を高速にするため hash = (文字種iが奇数個だったらiビット目を1とする) となるハッシュを考える。このハッシュを使うと 回文が成り立つ⇔1のビットの数が1個以下 と…

Mujin Programming Challenge 2017 A - Robot Racing

問題ページ 考えたこと ロボットiの前にたくさんロボットがいるとロボットiがゴールするのは不可能 ロボットiがゴールする前にある程度捌けてもらわないといけない ロボットiがゴールするのに必要な条件を考える 1 or 2マスジャンプなので2台連続でロボット…

ARC014 C - 魂の還る場所

問題ページ 考えたこと sample1のうちGBGGBGみたいな部分列は一方向から入れ続けても全部消せる 上のような部分列は当然消せる これを消した後はRGBGBRみたいに同じ色が絶対に隣り合わない列となる 筒に入っているボールをできるだけ消すとして考えてみると…

ARC101 E - Ribbons on Tree

問題ページ 考えたこと とりあえず木DPっぽい dp[頂点i][部分木iでまだペアが確定していない頂点の数j] みたいなのを考える 頂点数がdpテーブルに来てるし二乗の木DPっぽい 遷移がどうなるか考えるけど全くまとまらない 数学できれいになるのかなあと思って…

ARC072 E - Alice in linear land

問題ページ 考えたこと まずどんな動きをするのか試してみる 進行方向が反転だったりを考える必要はなくて目的地までの距離だけ使えばよさそう 現在の目的地までの距離をXでd[i]を入力するとX' = min(X, abs(X-d[i])) に変化する Xは単調に減少していくいう…

CODE FESTIVAL 2016 Elimination Tournament Round 1 A - グラフ / Graph

問題ページ 考えたこと Q=1ならどうか? SとTの間に重み0の辺を張ってMSTを求めればよい MSTを求めるのをQ回やったら当然TLE MST+αのやつは元のグラフのMSTを求めてそこからいじるのがよくあるパターン 元のグラフのMSTと辺を追加したグラフのMSTは何が違う…

QUPC2018 G - Tapu & Tapi 2

問題ページ 部分点 たぷとたぴが連結にならないようにする→カットなので最小カットを求めればよい。N<=500ならば最大フローを求めるアルゴリズムで間に合うのでdinicなどのライブラリを貼ればよい。 満点解法 木DPをする。dp[i][j] = (頂点iの部分木でiと連…

QUPC2018 F - Team Making

問題ページ 解法 bitDPで数え上げる。dp[S] = (集合Sがすでにチームが決まっているときの組み合わせ数) とする。TをSに含まれない要素の集合とすると集合Tから1人、2人、3人を選んでチームとする。このチームをSに新たに加えた集合をS'とするとdp[S'] += dp[…

QUPC2018 D - Novelist

問題ページ 考えたこと 区間が何個取れますかなので区間スケジューリングっぽい 都市Aに行ったあと王国に帰るなら一番早い依頼をうけるべき 王国→都市→王国 と移動するのにかかる区間を列挙しておく この区間を何個取れますか?という問題になった これは区…

QUPC2018 B - Tapu & Tapi

問題ページ 考えたこと 1円玉が奇数枚だったら無理 10円玉が奇数枚だったら1円玉で10円分をつくらないとだめそう 100円玉が奇数枚だったら10,1円玉で100円分をつくらないとだめそう 貪欲に取っていくのを書いたら落ちた 冷静になって考えると100円玉が10^9枚…

AGC028 C - Min Cost Cycle

問題ページ サンプル2眺めてたらA,Bまとめて小さい方からN個取れるとうれしい気持ちになって他のサンプルもそれであったのでそれで考えた。大体合ってたけどB問題で時間溶かしたら詰めきれなかった。 解法 A,Bまとめて小さい方からN個取ったときにハミルトン…

AGC028 B - Removing Blocks

問題ページ i番目がカウントされる回数= sum_{j=1}^N (j番目を取り除く時にi番目と連結なパターン数) までは考察できたけど連結なパターン数を求めるパートで無限に詰まって終了した。数え上げで全通りの数え上げは実質期待値と同じなので確率っぽい考え方が…

ARC102 E - Stop. Otherwise...

問題ページ 考えたこと 出目i,jを使わずにK面サイコロをN個降る組み合わせ数がわかればよさそう dp[i][j] = (i面サイコロでj個振るときの出目の組み合わせ数) とする これは実質パスカルの三角形なので dp[i][j] = dp[i-1][j] + dp[i][j-1] としてO(N^2)で求…

AGC012 C - Tautonym Puzzle

問題ページ 1を2個並べると1(=2^1-1)通り、1を4個並べると7(=2^3-1)通り、1を2n個並べると2^(2n-1)-1通りみたいになってるのでうまく2べきっぽいのを作って貪欲に取るみたいな方針でハマって終了した。回文系でよくあるんだし片方は固定してしまってもう片方…

AGC021 C - Tiling

問題ページ 考えたこと HとWが偶数だと考えやすそう Wが奇数だったら1列分どう頑張っても1種類目のタイルを置けない なので1列分2種類目のタイルを敷き詰めてしまってよさそう Hが奇数のケースも同様に1行分1種類目のタイルを敷き詰めてよさそう これでHとW…

AGC024 C - Sequence Growing Easy

問題ページ 考えたこと sampleを試すと数をつくるには 0,1,2,3,4,5,… と1ずつ増える列を組み合わせてつくる以外不可能そう i < a[i] となるiがあれば a[i] を作るのは不可能なので-1 0,0,2,3 のような2以上増えているような列は作れるか? 一回x[1]=1にした…

AGC009 C - Division into Two

問題ページ 考えたこと 集合を2分割する系なのでDPを考える 集合に入っている要素のうち一番大きい要素が大事 集合が空のときを考えるのは面倒なのでX,Yには-infが入っているものとしておく dp[i][j] = (集合にs[i]まで挿入していて、Yに最後に入れた要素がs…