ferinの競プロ帳

競プロについてのメモ

AtCoder

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]であるような路線のみである。したがって終点ソートしておき尺取法の要領で対…

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進数の形…

NJPC2017 H - 白黒ツリー

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

SoundHound Programming Contest 2018 Masters Tournament 本戦 B - Neutralize

問題ページ B - Neutralize 解法 DPをする。dp[i] = (区間[0,i]の最大値) とする。遷移について考えると max(dp[j]) (0<=j<=i-k) dp[i-1] + b[i] 0 (k-1<=i) の3通りになる。上から順に区間[j,i]を0にする、i番目の薬について0にせず足す、区間[0,i]全体を0…

ABC100 A - Happy Birthday!

問題ページ A: Happy Birthday! - AtCoder Beginner Contest 100 | AtCoder 解法 a <= 8 && b <= 8 なら条件を満たしているのでYay!、違うなら:(を出力する。 abs(a-b) <= 1 ならとか考えてたら2分かかってしまった。 ソースコード #include <bits/stdc++.h> using namespac</bits/stdc++.h>…

ABC100 B - Ringo's Favorite Numbers

問題ページ B: Ringo's Favorite Numbers - AtCoder Beginner Contest 100 | AtCoder 考えたこと ちょうど0回割り切れるって何だと思ってサンプルを見たら1回も割りきれないことっぽい nの後ろに'0'を2d個つければいいでしょと思って投げる 落ちてて何事かと…

ABC100 C - \*3 or /2

問題ページ C: *3 or /2 - AtCoder Beginner Contest 100 | AtCoder 考えたこと 全ての要素に対して2で割るか3倍するのどちらかをするのかと思う 全てのiに対して3倍するって何のことだと思って数分が経過する 操作1回につき各要素について2で割るか3倍する…

ABC100 D - Patisserie ABC

問題ページ D: Patisserie ABC - AtCoder Beginner Contest 100 | AtCoder 考えたこと 与えられる値が全て正だったらx[i]+y[i]+z[i]が大きい方から取ればいいだけ 最大化するのは絶対値で負がある それぞれ正負を試せばいいのでは? 正負を固定すればソート…

AGC023 B - Find Symmetries

問題ページ B - Find Symmetries 考えたこと とりあえずよい盤面を書いてみる 斜めにずらしたとしてもよい盤面であるのは絶対に変わらない したがってB=iとしたときによい盤面であれば斜めにずらしてもよい盤面 O(N^3)なので書くとサンプルが通らない 対称な…

AGC023 A - Zero-Sum Ranges

問題ページ A - Zero-Sum Ranges 考えたこと 問題を読むと200点に見えないので真面目に考える とりあえず累積和を取ってみる i番目を左端とする区間で部分和が0になる区間はa[i]=a[j]となる したがってiより右でa[i]と等しいものの数を数える mapで現れた頻…

ARC096 F - Sweet Alchemy

問題ページ F - Sweet Alchemy 解法 問題の整理 d[i] = c[i] - c[p[i]] とするとドーナツをつくれる個数の条件である c[p[i]] <= c[i] <= c[p[i]] + D を 0 <= d[i] <= D と言い換えることができる。ただし根に関してはdに制限はなく 0 <= d[0] となる。 頂…

ARC096 D - Static Sushi

問題ページ D - Static Sushi 考えたこと 何か既視感を感じる どうせ引き返すのは高々1回 時計回り or 反時計回りに一方向に回るだけならO(N)で簡単に求まる dp1[i] = ([0,i]で得られる最大のカロリー、時計回り) dp2[i] = ([i,n-1]で得られる最大のカロリー…

ARC096 C - Half and Half

問題ページ C - Half and Half 考えたこと 頑張って数学O(1)もありそうだけど絶対つらい 制約を見ると10^5なのでO(max(X,Y))できる ABピザを2i枚使ったとするとAピザ、Bピザの枚数は一意に定まる 全探索をする ソースコード #define __USE_MINGW_ANSI_STDIO …

ARC035 C - アットコーダー王国の交通事情

問題ページ C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder 考えたこと Sを求めるには全点対の最短距離が必要 ワーシャルフロイドをしたい 辺を追加するクエリの度にワーシャルフロイドしてO(N^3)かけていたらO(N^3K)でまず通ら…

ARC094 D - Worst Case

問題ページ D - Worst Case 考えたこと よくわからないのでとりあえず実験する A<=Bとか仮定しておくと便利そう 一回目、二回目に小さい順位を取った人が条件を満たすようにしたい A=8,B=9 みたいなのが来たら下のように構成できて14個 1,71 71,1 2,35 35,2 …

ARC095 E - Symmetric Grid

問題ページ E - Symmetric Grid 考えたこと 行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない 行と列独立に考えたくなる 行を交換する操作について考える ある行を二つ取り出してきたときにその二つの行の組み合わせで点…

ARC095 D - Binomial Coefficients

問題ページ D - Binomial Coefficients 考えたこと C(x,y)はxが大きければ大きいほどよさそう x = max(a) で固定 O(n)でC(a[n-1],a[i])を全部求めればいい気持ちになるがa<=10^9で無理 よくよく考えるとC(x,y)のyはx/2に近い方がいい パスカルの三角形を考え…

ARC095 C - Many Medians

問題ページ C - Many Medians 考えたこと 中央値を取りうるのはa[n/2-1]かa[n/2]の二択 n/2番目以降ならa[n/2-1]、それ以外ならa[n/2] ソートすればいいのになぜか座圧を書く 座圧を書いたあとsampleを見て気づいてソートに書き直す 出すと通る 無駄に時間か…