ferinの競プロ帳

競プロについてのメモ

Codeforces

codeforces #212 div2 D. Fools and Foolproof Roads

問題ページ Problem - D - Codeforces 概要 n頂点m辺の重み付き無向グラフが与えられる。このグラフに辺を張る操作をp回行うことで連結成分数がq個になるようにしたい。 辺を張るときは 同じ連結成分内の頂点なら1000 違う連結成分の頂点ならばmin(10^9, 連…

codeforces #212 div2 C. Insertion Sort

問題ページ Problem - C - Codeforces 概要 n要素の順列が与えられる。この順列に挿入ソートを行う。 この順列のどこか2要素をswapすることで挿入ソートでの交換回数を最小化しろ。 考えたこと ようするに転倒数を最小化すればいい i,j (i

codeforces #469 div2-C div1-A Zebras

問題ページ Problem - C - Codeforces 考えたこと 0と1の数からつくる01列の数特定できない?みたいになるけどできない 色々試してると前から貪欲に取ればいい気持ちになる 前から貪欲するのになぜかO(n^2)の方法しか思いつかない 括弧列みたいに+1/-1で累積…

codeforces #469 div2-D div1-B A Leapfrog in the Array

問題ページ Problem - D - Codeforces 本番中は誤読で時間溶かして終了 解法 操作を逆順にして考える n=5のとき以下のようになる 15243 1 2435 1 2 354 1 2 3 45 1 2 3 4 5 もし最終状態で存在する位置から初期状態の位置を復元できれば答えが求められる 移…

codeforces #433 div2 D. Jury Meeting

問題ページ Problem - D - Codeforces 考えたこと 頂点iに住んでいる人が2往復以上したほうがいいことはない 日付について区間[l,l+k]で議論をすると考える lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する 各…

codeforces #433 div2 C. Planning

問題ページ Problem - C - Codeforces 考えたこと 順列を全部試すのが無理なのはそれはそう 制約がだいぶでかいのでdpはつらそう 隣同士をswapするとコストがどう変化するかを考える i,i+1をswapするとコストが +c[i]-c[i+1] 変化する sortするような感じで…

codeforces #361 div2 D. Friends and Subsequences

問題ページ Problem - D - Codeforces sparseTableのverifyとして解いた。 解法 区間の左端lを固定して考えてみる 区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増…

codeforces #428 div2 D

問題ページ Problem - D - Codeforces 考えたこと 部分列を全列挙とかそういう方向は不可能そうなので各要素が含まれる部分列の回数とかそういう方向で考える gcdがiとなるような部分列について考える (部分列の長さの和)*i がこんな部分列のスコアになる m…

codeforces #428 div2 C. Journey

問題ページ Problem - C - Codeforces 考えたこと s8pcで見た D - Driving on a Tree 1頂点から求めればいいだけなのでもっと簡単 頂点1を根とした木について考える 止まる頂点は葉以外ありえない 葉までの距離とその葉にたどりつく確率を求めれば期待値が求…

codeforces #428 div2 B. Game of the Rows

問題ページ Problem - B - Codeforces 考えたこと 二人席が2n個、四人席がn個あると考えればよさそう ぴったり座れるときに座らない方がいいことはなさそう 二人席と四人席のどちらを先に埋めるべきか 四人席*1より二人席*2の方があとあとぴったり埋められる…

Codeforces Round #438 F. Yet Another Minimization Problem

問題ページ Problem - F - Codeforces 解法 dp[i][j] = (i個目の部分列でj番目までをカバーしたときの最小コスト) としたDPを考える。DPの漸化式は dp[i][j] = min_{k

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas

問題ページ Problem - E - Codeforces 解法 dp[i][j] = (i番目のゴンドラでj人目までを乗せたときの最小値) としたDPを考える。漸化式はdp[i][j] = min_{k

Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry

問題ページ Problem - C - Codeforces 解法 n本目の木を切ったあとはチャージし放題なのでコスト0で全ての木を切れる。したがってn本目の木を切るのに必要なコストを求めればよい。また、j本目の木を切った後にj本目より前の木を切ったとしてもチャージに使…

Codeforces Round #185 (Div. 1) B. Cats Transport

問題ページ Problem - B - Codeforces 解法 猫が止まる時間や丘までの距離など色々あって扱いにくいのでまずは処理しやすいように言い換える。丘に到達してから猫が待つ時間は猫と飼育員が丘0を出発する時間の差に等しい。したがって各猫が丘0を出発する時間…

Codeforces Round #462 (Div. 2) D. A Determined Cleanup

問題ページ Problem - D - Codeforces 考えたこと ax2+bx+c を x+k で割るみたいなので何個か実験すると何か規則がありそう コンテスト中はこの計算をミスってて別の規則を生み出してた(は?) 終わったあとに冷静になって計算すると a_1 + a_2x + a_3x^2 +…

Codeforces Round #462 (Div. 2) C. A Twisty Movement

問題ページ Problem - C - Codeforces 考えたこと 非減少列の判定が連続でなくてもいいことに気付かずに時間を溶かす 反転するのは1→2に移るところ~2→1に移るところ以外考えなくてよさそう [0,l) [l,r] (r,n-1] に分けると[l,r]に1から2に移るところがある…

Codeforces Round #462 (Div. 2) B. A Prosperous Lot

問題ページ Problem - B - Codeforces 考えたこと loopが2個の8を18個並べた36個が上限に見える ループが2個の8とループが1個の4,6,9あたりを使って適当に並べればよさそう leading zeroにだけ気をつけて出すと通る AよりBの方が簡単ですが… #include <bits/stdc++.h> using</bits/stdc++.h>…

Codeforces Round #462 (Div. 2) A. A Compatible Pair

問題ページ Problem - A - Codeforces 考えたこと ソートして大きい方と小さい方だけ考えればよさそうな気がしたので投げるとpretest通る 順位表を見てると+10とかしてる人がいたので見返すとだめなパターンがある 場合分け面倒そうなのでO(nm)の全探索を書…

2015 ICL, Finals, Div. 1 J. Ceizenpok’s formula (nCk mod m の求め方)

問題ページ Problem - J - Codeforces 概要 nCk mod m を求める。 1 <= n <= 10^18, 0 <= k <= n, 2 <= m <= 1000000 考えたこと JAG夏合宿で見た問題 パット見nCk mod m求めるいつものやつだ!と思って制約を見たら真顔になった n, kが大きすぎるのでn, kま…

Codeforces Round #446 (Div. 2) C. Pride

問題ページ Problem - C - Codeforces 概要 長さnの数列aが与えられる。以下の操作を繰り返して数列のすべての要素を1にする最小の操作回数を求めろ。 操作: 数列aから隣接した2要素x,yを選び、その一方をgcd(x, y)と置き換える。 解法 まず、数列中に1が1つ…

Codeforces Round #439 (Div. 2) C. The Intriguing Obsession

問題ページ Problem - C - Codeforces 概要 赤い島がa個、青い島がb個、紫の島がc個ある。これらの島に橋をかける。橋の長さを1としたとき、同じ色の島で最短距離が3未満になるような島のペアが存在しないようにしたい。このとき、橋をかける方法が何通りあ…

Codeforces Round #440 Div. 2 C. Maximum splitting

問題ページ Problem - C - Codeforces 概要 q個(1<=q<=10^5)個のクエリが与えられる。各クエリでは整数n(1<=n<=10^9)が与えられる。整数nを合成数の和として表したとき、最大の合成数の個数を各クエリで答えろ。 考えたこと できるだけ小さい合成数をつかっ…

Codeforces Round #443 (Div. 1) A. Short Program

問題ページ Problem - 878A - Codeforces 概要 n個(n <= 10^5)のbit操作が書かれたプログラムが与えられる。0から1023までの数がプログラムに入力される。このとき、5個以下のbit操作で同じ操作となるプログラムを出力しろ。 解法 bit操作と言われたので2進…

Codeforces Round #444 (Div. 2) C. Solution for Cube

問題ページ Problem - 887C - Codeforces 概要 2×2×2の立方体のルービックキューブが入力で与えられる。一回回転することで色が揃えられるなら"YES"、揃わなければ"NO"を出力する。 解法 回転のパターンは6パターンで反転で2倍で12パターン存在する。これを…

Codeforces Round #431 (Div. 2) D. Rooter's Song

問題ページ codeforces.com 解法 まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全…

Codeforces Round #431 (Div. 2) C. From Y to Y

問題ページ codeforces.com 考えたこと 構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。 まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら…

Codeforces Round #431 (Div. 2) B. Tell Your World

問題ページ Problem - B - Codeforces 考えたこと 頂点を二つに分類してそれぞれの頂点群が直線上に乗っていて各直線が平行であるかを判定すればよさそう。 まず、頂点1とiを2頂点として選ぶ。この2頂点を通る直線を一本目として考える。この直線上にない頂…

Codeforces Round #431 (Div. 2) A. Odds and Ends

問題ページ Problem - A - Codeforces 考えたこと 問題を読むと普通に思い浮かばない。奇数が連続してるところで切れる(奇数個の要素になるところでしか切れないので嘘)のでその数を数えればいいという謎の思考をする。 終了30分前にhackされる。ちゃんと…

Codeforces Round #429 (Div. 2) 考察

コンテスト中に考えてたことをまとめてみることにした。解法解説とはちょっとちがうかも? 覚えてる範囲なので時間はずれてるかも? ~00:03 Aを読むと、各文字の出現頻度を数えてKと比べればよさそう。ささっと実装したらpretest通った~00:10 Bの読解が難…

Codeforces Round #429 (Div. 2) C. Leha and Function

問題ページ Problem - C - Codeforces 概要 関数 F(n, k)を次のように定める。 集合{1,2,…,n}からk要素を選んだ部分集合を全て列挙する。各部分集合の値をその部分集合の最小の要素の値とするとき、この値を平均をF(n, k)とする。 \sum F(a[i], b[i]) が最大…