ferinの競プロ帳

競プロについてのメモ

競技プログラミング

ARC014 C - 魂の還る場所

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

AGC004 D - Teleporter

問題ページ 考えたこと "ぴったり"K回の制約がやっかい 街1のテレポーターが街1につながっていればK回以下で街1にたどり着きさえすればよい 街1のテレポーターが街1以外につながっていて実現可能な構成があるか? なもりグラフのサイクル上の街から首都まで…

ARC029 D - 高橋君と木のおもちゃ

問題ページ 二乗の木DPの練習として解いた。 解法 Mステップで使う玉は置かないという選択もできる。木の深い頂点から順番に置いていけば置いた玉が捨てられることはない。したがって、木の頂点にi個置くときはM個中の大きい方i個だけを置くとするのが最善の…

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枚…

考察パターン

問題を見直していて使うと思った考察パターン、知識のメモ 後ろの括弧には白文字で使ったと思った問題などが書いてあります。 グラフや木 頂点に値をもたせて葉から決めていく(DFSや木DP)(AGC010-C,ARC063-E,ARC083-E) 仮想頂点を追加する(ARC029-C,JOI ゾ…

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…

AGC006 C - Rabbit Exercise

問題ページ 解説を読んだ。 解法 数式で扱いやすい形に変形 公式解説にある通り対称な位置の計算、位置の期待値の計算を扱いやすい形(置換)に変形する。 置換をダブリングで高速に計算 K回置換を計算するのは二分累乗、ダブリングの要領で高速にできる。置換…

AGC026 B - rng_10s

問題ページ 思考過程 よくわからないのでサンプルを試してみる i日目の昼にxで回ってきたら次に補充されるタイミングには x%b 個になってそう x%b > c であれば補充できず、mod bなのでb未満なので続けられなくなる よくよく考えてみると b > c のときとかが…

JAG夏合宿2018 day3 D - Prefix Suffix Search

問題ページ 解法 単語のリストwをソートしたものを使うと二分探索で接頭辞がpの単語の集合がわかる。各単語を反転したリストw_invをソートした物を使うと二分探索で接尾辞がsの単語の集合がわかる。wとw_invをそれぞれ座標軸にとった二次元平面上にプロット…

Typical DP Contest K - ターゲット

問題ページ 解法 円なので2次元っぽいが円の中心のy座標が0なのでこれは1次元の問題である。各円は[x-r,x+r]の区間に置き換えられこの区間でK重に内包されているよな区間があればそれはレベルKのターゲットである。区間がたくさん来たので終端でソートしてみ…

JAG夏合宿2018 day2 J - AB Sort

問題ページ 解法 解説にある通りAを+1, Bを-1に置き換えて累積和を取って標高図を書いてみる。操作を終えたあとの最終的な文字列はA…AB…Bとなる。標高図のminが最終的な標高図のminになるまでとそこから標高図のmaxが最終的な標高図のmaxになるまでの2つに分…

ABC106 D - AtCoder Express 2

問題ページ D - AtCoder Express 2 解法 区間がたくさん与えられるときはとりあえず終点でソートする。あるクエリ(p[i],q[i])が与えられるとき、数える対象となる路線はr[j]<=q[i]であるような路線のみである。したがって終点ソートしておき尺取法の要領で対…

Codeforces Round #499 (Div. 2) E. Border

問題ページ Problem - E - Codeforces 考えたこと k進数の下一桁はkで割った余りに等しい a[i] mod k を取っておいてよさそう dp[i番目][金額]=(bool)とかしたいけど10^10なので無理 a[i]がkと互いに素なら0~k-1まで全て取りうる a[i]がkと互いに素でない場…

Codeforces Round #499 (Div. 2) D. Rocket

問題ページ Problem - D - Codeforces 考えたこと p[i]を把握しないといけない y=INFを出力しようと思ったけどだめなのでy=1を出力して確認する p[i]さえわかれば二分探索すればよい m<=10^9ならクエリ回数30回あれば足りる 二分探索を実装して出すと通る y=…

Codeforces Round #499 (Div. 2) C. Fly

問題ページ Problem - C - Codeforces 考えたこと 燃料xを積んだときに旅行を達成できるか?を考えると単調性がある 判定O(N)でできそうなのでにぶたんできそう 燃料を10^9までしか使わないことが保証されている -1の判定はこれを使えばできそう 不等号に=を…

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

問題ページ C - Cheating Nim 考えたこと Nimの勝利条件から問題文を言い換えたい 不正者が勝てるのは a[0] xor a[1] xor … xor a[n-1]=0 のときだけ 山の石の数を-1する操作で上の条件を達成する問題になった xorなのでビットごとにみたくなるので2進数の形…

yukicoder No.235 めぐるはめぐる (5)

問題ページ No.235 めぐるはめぐる (5) - yukicoder 解法 HL分解の練習として解いた。クエリ0は街Xから街Yに対してC[i]*Zを加算するクエリ、クエリ1は街Xから街Yの値の和を求めるクエリになる。区間に対しての加算と区間和を求めるものなので遅延セグメント…

NJPC2017 H - 白黒ツリー

問題ページ H - 白黒ツリー 解法 頂点に関する制約条件を扱うのは大変なので辺のコストの条件に置き換える。両端の頂点の色が違う辺のコストは0、両端の頂点の色が同じ辺のコストは1とする。こうするとクエリ2について頂点uとvの2頂点間の距離が0かどうかの…